Robust Mean Estimation Without Moments for Symmetric Distributions
Authors: Gleb Novikov
David Steurer
Stefan Tiegel
Venue: NeurIPS 2023 poster (2023)
Keywords: Robust Mean Estimation
Unbounded First Moment
Symmetric Distributions (Spherical
Elliptical
Product)
Filtering Algorithm
Huber Loss
TL;DR: We give polynomial-time and in some cases nearly optimal algorithms for robustly estimating the location parameter of symmetric distributions.

Abstract: We study the problem of robustly estimating the mean or location parameter without moment assumptions.
Known computationally efficient algorithms rely on strong distributional assumptions, such as sub-Gaussianity, or (certifiably) bounded moments.
Moreover, the guarantees that they achieve in the heavy-tailed setting are weaker than those for sub-Gaussian distributions with known covariance.
In this work, we show that such a tradeoff, between error guarantees and heavy-tails, is not necessary for symmetric distributions.
We show that for a large class of symmetric distributions, the same error as in the Gaussian setting can be achieved efficiently.
The distributions we study include products of arbitrary symmetric one-dimensional distributions, such as product Cauchy distributions, as well as elliptical distributions, 
a vast generalization of the Gaussian distribution.

For product distributions and elliptical distributions with known scatter (covariance) matrix, we show that given an $\varepsilon$-corrupted sample, we can with probability at least $1-\delta$ estimate its location up to error $O(\varepsilon \sqrt{\log(1/\varepsilon)})$ using $\tfrac{d\log(d) + \log(1/\delta)}{\varepsilon^2 \log(1/\varepsilon)}$ samples.
This result matches the best-known guarantees for the Gaussian distribution and known SQ lower bounds (up to the $\log(d)$ factor).
For elliptical distributions with unknown scatter (covariance) matrix, we propose a sequence of efficient algorithms that approaches this optimal error.
Specifically, for every $k \in \mathbb{N}$, we design an estimator using time and 
samples $\tilde{O}({d^k})$ achieving error $O(\varepsilon^{1-\frac{1}{2k}})$.
This matches the error and running time guarantees when assuming certifiably bounded moments of order up to $k$.
For unknown covariance, such error bounds of $o(\sqrt{\varepsilon})$ are not even known for (general) sub-Gaussian distributions.

Our algorithms are based on a generalization of the well-known filtering technique [DK22].
More specifically, we show how this machinery can be combined with Huber-loss-based 
techniques to work with projections of the noise that behave more nicely than the initial noise.
Moreover, we show how sum-of-squares proofs can be used to obtain algorithmic guarantees even for distributions without a first moment.
We believe that this approach may find other applications in future works.

Robust Mean Estimation Without Moments for Symmetric Distributions
Gleb Novikov
David Steurer
Department of Computer Science ETH Zurich
Department of Computer Science ETH Zurich
Stefan Tiegel
Department of Computer Science ETH Zurich
Abstract
We study the problem of robustly estimating the mean or location parameter without moment assumptions. Known computationally efficient algorithms rely strong distributional assumptions, such as sub-Gaussianity, or (certifiably) bounded moments. Moreover, the guarantees that they achieve in the heavy-tailed setting are weaker than those for sub-Gaussiaa distributions with known covariance. In this work, show that such tradeofT, between error guarantees and heavy-tails, is not necessary for symmetric distributions. We show that for large class of symmetric distributions, the same error in the Gaussian setting can be achieved efficiently. The distributions we study include products of arbitrary symmetric one- mee-dimnnioonll distributions, such as product Cauchy distributions, as well elliptical distributions, vast generalization of the Gaussian distribution.
For product distributions and elliptical distributions with known scatter (covariance) matrix, we show that given an e-corrupted sample, we can with probability at least
- estimate its location up to error Ole /To((11/))) using dlog(d) +log(1/8) sam- log(1/e) ples. This result matches the best-known guarantees for the Gaussian distribution and known SQ lower bounds (up to the log(d) factor). For elliptical distributions with unknown scatter (covariance) matrix, we propose sequence of efficient algorithms that approaches this optimal error. Specifically, for every 1 E N, we design an estimator using time and samples Ō(d*) achieving error O(s2~ This matches the error and running time guarantees when assuming certifiably bounded moments of order up to k. For unknown covariance, such error bounds of oE) are not even known for (general) nub-Gaussian distributions.
Our algorithms are based on generalization of the well-known filtering technique [DK22]. More specifically,
show how this machinery can be combined with Huber-loss-basee techniques to work with projections of the noise that behave more nicely than the initial noise. Moreover, used to obtain algorithmic guarantees even for distributions without a first moment. We believe that this approach may find other applications in future works.
show how sum-of-squares proofs can be
Introduction
Robust statistics [Hubll RHRSI1] is central field in statistics with the goal of designing algorithms for statistical problems that are robust to small amount outliers, for example caused by measure- ment errors corrupted data. We model this follows: Samples are generated from an unknown
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

distribution D and then an E-fraction of them is arbitrarily corrupted by an adversary with full knowledge of the underlying model and our algorithm. We only have access the corrupted samples. In this work we focus on the canonical task of estimating the mean of D. Traditionally, estimators robust to such corruptions have been computationally inefficient, requiring time exponential in the ambient dimension [Ber06], while computationally efficient estimators have incurred error scaling with the ambient dimension thus rendering them unsuitable for today's s high-dimensional statistical tasks. Recently however, flurry of efficient estimators emerged achieving guarantees without this prohibitive dependence on the dimension and with error rates approaching those of computationally
inefficient ones [DKK* + 19. LRVI6 CSV17 17 DKK 17
HLI8 18 KSS18 DK22].
textbook example of this development is when D is the multi-variat Gaussian distribution (or Lub-Gaussian distributions with known covariance). In this setting, efficient algorithms can estimate the mean to within error O /log 1/e)), (lo((///))) i.e., nearly linear in E [DKK 19, DKK+17 KMZ22]. The statiscally optimal error rate is (E) [CGRI8]. That is, efficient algorithms are optimal up to the additional factor of Vlog(L/E). Further, it is conjectured that this factor is inherent for efficient algorithms, i.c., that there is cimpputttional-staristtteee gap. This is evidenced by known lower bounds for statistical query algorithms [DKS17]. However, there are two drawbacks with this textbook example: If the covariance matrix is unknown, it is not known how to efficiently achieve the same error for sub-Gaussian distributions, in fact, in full generality, it is not even known how to achieve error ol Ve) in this setting. This is because known algorithms rely heavily of Gaussian moments. Second, the assumption that the uncorrupted data belongs to a (sub)-Gaussian distribution is arguably very strong. A more natural setting when D is allowed to have heavier tails. In the setting that D has bounded second moments it is known how to achieve error O(v)) efficiently [KS19 LRVI6 CSVI7 DKK + 17). Interestingly, OVE)) seems to constitute a barrier for efficient algorithms. In particular, while error of EEE) is possible anformation-theoreticlll theoretically if we assume that higher-order moments are bounded, HLL9 show that bounded moments alone are likely not enough for efficient algorithms, and that additional assumptions are required. Currently, these manifest as either assuming that there is certificate, in sum-of- -unuures for the boundedness of the moments [HL88] KSS18 or assuming the covariance is the identity (or known) [DKP20] While these approaches indeed break the O(vE) barrier, they in many cases fall short of the (lg(()) error possible in the Gaussian setting. In particular, they only achieve error comparable to the Gaussian case, when using Ollog(//E) many moments. Unfortunately, it is necessary to use this many moments, even when assuming they are certifiably bounded [KSS18), Thus, the tails of these distributions are already much lighter than, say, in the bounded covariance case. Therefore, a natural question is:
the algebraic structure
Do there exist classes of heavy-tailed distributions for which we can (efficiently) achieve the same robust error as for the Gaussian
distribution?
In this work, we answer this question by giving algorithms that use a (quasi-)polynomiaa number of samples (in the dimension and 1/e) and time polynomial in the number of samples for the broad class of symmetric product and elliptical distributions. Moreover, in many cases, we can achieve this using (nearly) the same amount of samples as for the Gaussian distribution, recovering, e.g., the optimal dependence on the failure probability. We remark that the distributions we consider might have arbitrarily heavy tails and we do not make any assumptions related to -quurrss
Product and Elliptical Distributions Symmetry is a natural assumption in statistics with many applications to, e-g., mathematical finance and risk management [Lin75] OR83 Cha83]. In this work, we consider the following two types of symmetric distributions that are of particular interest [el70 CHS&1 Fan18]: First, product distributions of symmetric -iedemmeniioaal distributions and spherically symmetric distributions. These correspond to a generalization of the standard Gaussian distribution. Examples are product Cauchy distributions and the multi-variate Student t-distribution with identity scatter matrix. Second, elliptical distributions. These correspond to a generalization of Gaussians with arbitrary (unknown) covariance matrix. Examples include the multi- variii- Student t- t-distribution, symmetric multivariate stable distributions and multivariate Laplace distributions. For both classes, it is iooommtiionthhoretiiall
possible to obtain robust error O(e) [CGR 18 PBR20), i.e., matching that of a Gaussian. These approaches are not known to run in faster than exponential time and prior work (PR220 asked whether a similar error can be achieved efficiently. We respond to this question, by designing algorithms that nearly, in some cases exactly, match this error in
2

---

polynomial (in the number of samples) time, if the number of samples is polynomial (in the cases of symmetric product or spherically symmetric distribution) or guasi-polynomial (in the case of elliptical distributions) in the dimension and I/e.
1.1 Problem Set-Ups and Results
Next, we give formal definitions of the corruption model and distributions considered and state our results. We use the following standard model for corruptions often referred as the strong contaminiation model.
Definition 1.1. Let Xi...., X be samples from a distribution D and let >> 0. We say that
Zi..... Zn, are an s-corruption of X1,... Xn. if they agree on least an (1 - -) e)-fraction of the points. The remaining e-fraction can be arbitrary and in particular, can be corrupted by an adversary with full knowledge of the model, our algorithm, and all problem parameters.
We consider the following two classes of distributions.
Definition 1.2 (Semi-Product Distributions). Let p > 0. We say a distribution D over R is an p-semi-product distribution, if for ~ 'D it holds that
1. For all j E [d]. the distribution of ny is symmetric about 0,
2. For all j E [d]. IP (n/l= & > 100-
3. The random vectors (sign( (yy ) and (n,,)) are independent, and the random variables sign (n)) ...,....,,iin sign (Ta) are mutually independent.
Some remarks about the definition are in order. First, notice that the Gaussian distribution N p² I) is (())-semi-produce Similarly, every symmetric product or spherically symmetric distribution that has covariance bounded by p² Ida is O(p) ((p)-semi-prooe semi-prduue... In particular, the coordinates πi need not be independent. However, the definition allows for much heavier tails, the only requirement is that at least 1/100-fraction of the probability mass lies in interval of length p around q") In particular, it captures all spherically symmetric distributions, e.g. multi-variate /-distributions with identity scatter matrix, and all symmetric product distributions, e-g. the product Cauchy distribution. Notice that in the non-robust setting the first two properties are enough to accurately estimate ja" from samples yx" + 77;-.... μ=" The via adding symmetrie mean zero noise with tiny variance each coordinate and computing the entry-wise median. We expect that some additional assumption is necessary for efficient algorithms in the robust setting. We show that Property above is sufficient. A different sufficient condition would be assuming that the distribution is elliptical, which we discuss next.
The second one is the class of elliptical distributions [Ke770, CHS&I Fan generalization of spherically symmetric distribution, which in particular can have more complex dependency structures.
Definition 1.3. A distribution D over Rd elliptical, if for n ~ D the following holds: Let U be uniformly distributed over the d-dimensional unit sphere. There exists positive random variable R, independent of U, and a positive semi-definite matrix Σ, such that
n / and TP R
v 2d
>
We call Σ the scatter matrix of the distribution (sometimes also referred to as the dispersion matrix). In particular, the Gaussian distribution (0, Σ) with arbitrary elliptical. Further, we can choose its covariance matrix as the scatter matrix. Indeed, we can decompose X ~ NO, Σ) as X / where R is distributed as the square root of x2 dddistribution with d degrees of freedom and U is independent of and distributed uniformly over the unit sphere. Then by Markov's Inequality, holds that PP < 22d) = P 2 & 2d) > 1. Elliptical distributions with seatter matrix identity correspond to spherically symmetric distributions, a special case of ceni-product distributions. Note that that elliptical distributions do not capture product distributions except for the Gaussian case e.g., the product Cauchy distribution is not elliptical.
'This can even further be relaxed to any a > 0 fraction. The sample complexity and error then scale naturally with See the appendices for more details.
3

---

Extending the above two defintions, we say that a distribution D is p-semi-product (resp. elliptical) with location μz I if samples of 'D take the form μ + 17. where μ E I deterministic and r is p-semi-product (resp. elliptical). Note that the location takes the place of the mean, as this might not exist for distributions of the above form.
Results Our main result for semi- product distributions is the following: Note that we can reduce the case of elliptical distributions with known scatter matrix to the ([1)-semi-prodeee case, hence the theorems below also apply to this setting. We also remark that the algorithm only receives the corrupted samples as input. In particular, P need not be known (and can be estimated from the corrupted samples). See the appendices for proof.
Theorem 1.4. Let μ² E ERd, ,, > O and D be a p-semi-product distribution with location jC" Let
C> 0 be large enough absolute constant and assume that & 1/C and 3 C. e (1///)
(log(d))log(1//) (lg(1//))
Then, there exists an algorithm that, given an e-corrupted sample from D, runs in time n (11) and outputs Ji E R& such that with probability at least 1 it holds that
dllo(d)) log(1/5) + (lol((11))) [
1| l 10 -1 <
n
Our sample complexity is nearly optimal in the dependence of the error on E and d and optimal in the dependence the failure probability 5, all up constant factors. Recall that N(,, p² Ia) is a pee---smppoouuus distribution and hence lower bounds for this setting apply. The statistically optimal error in this setting is S(p E) [CGR18 and can be achieved using > d++log(1/8 samples.
Note that we match this error up to the Vlog(1/e) term, using only slightly more samples (d vs d log d). It is conjectured that the larger error is necessary for efficient algorithms, as it is necessary for all efficient SQ algorithms [DKS17] It an interesting open question to remove the additional factor of log d in our sample complexity. Further, our algorithm nearly matches results known for the standard Gaussian distribution (up to the log(d) factor error and sample complexity) [DKK*19 19 DKK+17 KMZ22). We expect our algorithm to be practical, since it only uses one- dimensional smooth convex optimization (O(nd) times), the top eigenvector computation (0(n) times) and arithmetic operations.
Interestingly, we show how to achieve error scaling only with O(p E) using quasi-polynomialyy many samples:
Theorem 1.5. Let 1r" E TRd TRd > and 'D be a p-semi-product distribution with location j²" Let C 0 be large enough absolute constant and assume that & 1/C and C d @Clog(L/E), Then, there exists algorithm that, given e-corrupted sample from D, runs in time n (11) and outputs ja E Rdd such that with probability at least 1 it holds that
1 - n 1011 (
[
[V d 1og(1/0) + +0))
n
In order to state our results for elliptical distributions, we need to introduce the notion of the effective rank of matrix Σ. This is defined as r(E)= := Tr E/|E|| and captures the intrinsic dimensionality of the data. Note that it is always at most d, but can also be significantly smaller. We remark that we do not assume that the seatter matrix is known to the algorithm.
Theorem 1.6. Let C > 0 be large enough absolute constant. Let k N,E,8 0. E Rd such that & & 1/C and assume D is an elliptical distribution with location p² and scatter matrix satisfying r(E)= > C k log 2 Also, let n > C (r(E)/k) /k)* log(d/6). There an algorithm that, given an E-corrupted sample from D, runs in time n o1) (1)) (II)) and with probability at least 1 -
outputs á E R2 satisfying
((()) log(d/6) + vk-
A - n0 111
VIEII
n
AA slightly weaker condition suffices, see the appendices for all details. Note that as long as < Olog((/e)) & Ollog d). this assumption is mild and in particular is always satisfied if the condition number of is 0(1) (as d + oc).

---

Note that in the special case when D = (N, Σ), the information-theorriically optimal enror is ( |-]] =) and can be achieved using n > r(2)+ =(2))+og(1/0) samples [CGRI8, MZ23]. We give a sequence of algorithms (nearly) approaching this error using an increasing number of samples and time. In fact, for k- = (llog(1/E))) ((y)oo()/)) log(d/6) samples and time d². Similar to the bounded moment setting [KSS18 HL18 the parameter k can be thought of as a way to trade between sample/time complexity and accuracy guar- antees. Also note that already for 2 we achieve error O / |E|l) for elliptical distributions with unknown covariance/scatter matrix in polynomial time and sample complexity, while even for (general) sub-Gaussian distributions with unknown covariance it is not known if it is possible to achieve error o(vê- /EI in polynomial time and sample complexity. addition, if r(x) much smaller than d, for example, r(E) < dd.1, then we achieve error ( VTEI with a sub-linear number of samples (d2.)) in time d0(1).
we achieve error O /log/o)(L/s)
vIED using at most
g²
Previous Algorithms and Possible Extensions Previously, to the best of our knowledge, only exponential time computable estimators were known, for both emii-product and elliptical distributions.
The results [CGRIS PBR20 imply that there exist estimators that achieve error O(y d+1/)(118) +
(assuming |Σ||| < (()) for elliptical distributions). Both algorithms rely on brute foree techniques for which it is unclear how to make them efficient.
A natural question is if we can achieve (nearly) optimal error in polynomial time (analagous to the semi-product case). Indeed, for non-spherical Gaussian distributions, it known how to do this [DKK*19 17K+ These algorithms crucially rely on robustly estimating the covariance matrix first. Similarly for elliptical distributions, it seems necessary to first robustly estimate the scatter matrix and then apply our results for the semi-product case. However, current covariance estimation algorithms rely heavily on the algebraic relations between the Gaussian moments, and is not known how to achieve this for other distributions where moments do not have these specific relations. Thus, we expect this to be an interesting but challenging task.
A different direction we believe is interesting to explore is the following: We gave algorithmic results matching in many cases what is known for the Gaussian distribution. the non-robust setting, there is in principle hope to go beyond this: There are known estimators that are asymptotically normal with variance scaling with the Fisher information of the distribution [Sto75]. So there is error" on distributions with small Fisher information. However, these
hope for better-than-Gausiie results are purely asymptotic and there are (symmetric) distributions for which we cannot hope to achieve even finite sample results scaling with the Fisher information (see, e.g., the discussions in [LP223)). To get around this issue, the recent work of [LP233 introduced related notion, called "smoothed Fisher Information" and achieved finite-saple (non-robust) error guarantees scaling with the smoothed Fisher Information in the one-dimensional case, also for symmetric distributions. It would be interesting see, if similar guarantees can be achieved in the robust and high-dimensional setting, too.
We further believe that similar guarantees can be achieved based on E f1-minimization techniques (instead of Huber-loss) under slightly different assumptions. In particular, even in the non-robust setting, we need to require small amount of density at (or sufficiently) close to the location, else any point in the region around the location with zero density, would be an & f1-minimizer. In the case of semi- cuni-prrduct distributions, this is without of loss of generality, since we could add Gaussian noise of the appropriate variance to each coordinate. For elliptical distribution, this approach does not work, since the resulting distribution might no longer be elliptical.
1.2 Related Work
We only list the works most closely related to this work, we refer to (D22 for survey on the area. Most of the literature on efficient algorithms for robust mean estimation has focussed on the setting when at least some of the moments are bounded. In what follows we focus mainly on how the error guarantees depend on s and put other parameters, such as the dependence on the failure probability aside. [DKK + 19 DKK+ 17 KMZ22 show how to efficiently estimate the mean of Gaussian distribution, sub- GausGan with dlentity-covariance up error O ((=//ooge log(1/))). Assuming that
the distribution has covariance bounded by identity, [CSV17 DKK [XK]] 17 DKP20 show how to achieve
5

---

error O(VE). Similarly, for a E [0, 1], [CTB/22 shows how to achieve error ((e7/(++)) when in every direction the + a moments are bounded. Note that in constrast to this, our algorithm can handle distributions without a first moment and achieves error ((e//oog(11)) 1/e)). An interesting question is whether assuming bounded higher-order moments can lead to improved error guarantees. Interestingly. 1L19 shows that this alone is likely to be not enough in order to go beyond error VE. So far, there have been two ways of additing additional assumptions: First, assuming that D has k-th moments bounded by og in every direction, and assuming that it is certifiable sum-of-squares, is possible to achieve error ((a Second, if the k-th moments are bounded by ou. not necessarily certifiably in sum-of-squares, and the covariance matrix is a multiple of the identity (or known), [DKP20) achieves error O O(axe1-1/22))
using (k()) samples and time [L.18 KSS18 [ST2]]
Other Results On Symmetric Noise Distributions and the Filtering Techniques Huber-loss minimization has been used to design computationally efficient estimators for variety of problems:
Linear regression in the heavy-tailed/symmetrri setting [TS014 20, SZF20 aNS21 dLN
as well as the robust setting [IL.20]. Other works developped algorithms for PCA under symmetric
noise [CLMWIT] 21
dNNS23.
The filtering technique [DKK* + 19 DKK* + 17 (or versions thereof) have been successfully applied
to robust and heavy-tailed (when the covariance exists) mean estimation DHL19 DKP20 HLZ20
DK22 DKLP22 as well as prepprocsssing step in robust regression PII1.0
2
Techniques
We will first describe the general theme of our techniques. These ideas will yield algorithms achieving (nearly) optimal guarantees using quasi-polynomen can already achieve error of /E) using only polynomially many samples. At the end of this section we show how to improve this to nearly linearly many (in the dimension) samples for semi-product distributions.
many samples. Note however, that using these,
One-Dimensional Robust Estimation via Huber-Loss Minimization Current algorithms for robust mean estimation are only known to work for distributions with bounded moments, In many cases this is assumption reasonable, and in many cases it is also necessary [KSSI8] CTBJ221 However, there are many other distributions that do not necessarily have any moments at all, but which one would expect to behave nicely. Current approaches are inapplicable in these settings. Of particular interest is the class of symmetric distributions, which might not even have first moment in this case we want to estimate the location parameter of the distribution, which always exists and coincides with the mean in case it exists. In non-robust statistics (when there are no corruptions), symmetric distributions in some sense behave as nicely as the Gaussian distribution: The minimizer of the entry- wise Huber-loss function achieves the same guarantees for such distributions as the sample mean in the Gaussian case. The entry-wise Huber-loss is the function LH : Rd + R
defined as L (v) == ンド 4 (uz). where Φ: R - IR is a Huber penally: 4(x) = =x²/2. if |x| 1 and (xx) = |x| 1/2 otherwise. 4 is convex, and has many appealing properties. in particular with respect to symmetric distributions, since its derivative is a bounded odd Lipschitz function: x(x) = (z) = xx, if |x]| < 1, and d(r) = sign (I) otherwise.
Since the Gaussian distribution is symmetric itself, the Huber-loss estimator has the same guarantees as the sample mean in this setting. Beyond that, the Huber-loss estimator enjoys some robustness guarantees that the sample mean does not: Let us consider the one-dimensional case, where the Huber-loss behaves similarly to the median but has additional properties that will be useful to us, e.g.. is differentiable everywhere. In this setting, the sample mean has unbounded error even if there only single corrupted sample, while the Huber-loss achieves the information theoretically optimal error O (E) when an arbitrary e-fraction of the samples is corrupted. Moreover, these guarantees extend to arbitrary one-dimensional symmetric distributions that satisfy mild scaling assumptions. Unfortunately, this does not directly yield good robust estimator for the digh-diimnsional setting. we naively apply the one dimeemmnsi estimator entry-wise we can only guarantee an error bound of O(vVd), which is far away from the O(e) error that is statistically possible for the Gaussian distribution and symmetric distributions. Moreover, it is also inferior to error rates obtained by efficient estimators that use assumptions about bounded moments: Such estimators achieve error

---

that does not depend on d. In this work we show that there exist more sophisticated estimators based on the Huber-los that achieve cianensioonindeeedeen error, often matching what is possible for the Gaussian distribution, for estimating the location of symmetric distributions even in the high-dimensional robust setting.
Proofs of identifiability and the filtering technique Before describing how we use the Huber- loss in the high-dimensional setting, it will instructive to recall how the classical approach for distributions with bounded moments works - for simplicity, focus bounded second moments and sketch how this extends to higher-order moments. Later, we will see how to modify these ideas, using the Huber-loss, to work also in the symmetric setting without moment assumptions. In particular the version for Gaussian-like error for semi-product distribution requires several new technical ideas compared to the Gaussian setting.
At the heart lie identifiability proofs which can be made algorithmic using either -uuuof-squares [KSS18] HLI8) or the filtering technique DDKK 19 DKK + 17 [HL19). For bounded covariance distributions these take the following form: If two distributions D, and D2 with means μn, respec- tively (42. and covariance matrices Σ1 3 Idg. respectively Σ₂ < Ida, are e-close in statistical distance, then ||ا - Pell ll & (VE). In what follows, for simplicity of the discussion, we will sometimes switch between empirical and true distributions. In robust mean estimation, empirical distribution over the corrupted samples we observe, while D2 is the empirical distribution of the uncorrupted w samples. Hence, by assumption, Σ₂ I Ida and wish to estimate 1/2. The above statement of identifiability asserts that as long as Σ1 I Ida, the empirical mean of the corrupted samples, i.e., M1, is O(Ve)-close to μ22- Of course, Σ1 I Ida might not hold, since the outliers could potentially introduce a large eigenvalue in the empirical covariance matrix. However, since we know that these large eigenvalues must have been introduced by outliers, this gives rise win-win analysis: We check if ΣΙ 3 Ida holds. If it does, 141 is ((Ve)-(Coos to f12 already, if not, we compute its top eigenvector and remove samples that have large correlation with this eigenvector. It turns out that this procedure will always remove more corrupted samples than uncorrupted ones. Thus, we can iterate this procedure and are guaranteed that it terminates after (en) iterations. After its termination, we are left with distribution Dj, with mean μ41 that is Ole)-close in total variation distance to D₁ and D2, and has small covariance Σ/ - Ida, hence ||,| wel & O (VE).
assume that D₃ is the
Of course, for arbitrary symmetric distributions the covariance might not exist. So neither the above proof of identifiability nor the filtering technique apply to this setting. However, one of our main observations is that we can obtain a similar statement of identifiability also in this case. In addition, we will later show how adjust the filtering technique to work with identifiability proof this requires non-trivial modifications of the original approach. First, observe that the identifiability statement in the bounded moment setting, can be phrased as follows: For j E {1, 2). the mean μa of a distribution D, corresponds to the minimizer of the quadratic loss:
H1 = arg min E ly aa|² agRd D~D,
Hence, if D1. with covariance Σj 3 Idg, and D2 with covariance Dn - Idg. are E-close in statistical distance, then the minimizers, μ1 and μ22 of the quadratic loss are O( -E)-ole to each other. A crucial observation is that, if distribution D is symmetric, then its location is the entry-wise Huber-loss m
# = arg min E CH (y a)
aERd w-D
Hence, we would like to obtain similar statement about minimizers of the Huber-loss for two E-close distributions Dj and D2. This will be useful since we will need to learn the location μ/2 of symmetric distribution D2 from D1.
Abstract proof of identifiability In order to formalize the above, consider the following abstract setting: Let L be some loss function that differentiable, (11)-stongly convex and smooth (i.e. its gradient V L is 1-Lipschitz). Let D2 and D2 be two distributions that are e-close in the statistical distance, Then, for j E {1,2] the minimizers sy := arg min Ey~D, C (y a) satisfy
We use entry-wise Huber-loss for semi semi-product distributions. For elliptical distributions we use another loss funetion, that also related to the Huber penalty. AAssuming that each entry of y y has nonzero probability mass in the interval [-1, 1].
7

---

By-D, (V - ( u,)² < 1 for all unit vectors u, then 1I ا < O(VE). Indeed, by strong convexity and the defiiition of fi.
1 (11m )22l²)
<
E
L -m11
E
L P2)
E W-D,
(VL ( (iz))
ynDi
V-Di
<
(VL (v2) in -iz)
y~D,
Notice that there is coupling w of D1 and D2 such that IP P(y, w2) (91 # y2) & e. Since
Ey-DD VL (y - (2) = O. we obtain using the
Schwarz Inequality
Ω (11x1 P2ll &
E (3n (92) mw
( f22) VL (32 (22) P1 - (22)
E (yn vas
[un
(VL (1/1 - j12) - (y2 - -v²2) , jūn - -1z)
E (g).
(y1 - - VL ji2)) i1 -p²2)
Since VL is 1-Lipschitz, using the bounds on max]|u|| BynD (VC - (gy) u)? yields
E
(VL (y1 (22) - (v2 (22) /1 -12)²
(21.22) wo
E VVL (y) (i2) - (L - i1) + VL (y11 --)) - -VL - -22) - -
Dr
E LVL (y)- - -22) - VL - ii),, fm - -22)²² + +11ma - nnal?))
<0 || (10111 i=2l=* + |1m - -Aall²)
Hence, || juzll² & O(VE || - /22 + V8. I| - (021)) If E small enough (smaller than some constant that depends on the strong convexity parameter), we obtain that 1| --2ll < O(VE).
Similar to the bounded moment setting, we can generalize this observation to the case when for some integer l: > and some m22k > O, max F Fy,,D, (VL (y- - (5)) u) 2k < m In this case we can use Hölder's 's inequality to obtain the bound || ححت < O g² cl-1/(2k)). Note that in order combine higher-order moment bounds with the filtering technique, we need an efficient procedure to certify these bounds. Thus, previous works only applied to distributions for which such moment certificates, in -f--urrsss,, exist. We remark that in the symmetric setting we are able to obtain the necessary certificates for filtering without making any sum-of- -quures related assumption on the distribution.
Filtering in the symmetric setting We will show how to adopt the filtering technique to make the above proof of identifiability algorithmic for symmetric distributions. Indeed, let D2 be symmetric distribution with location μ= Assume we can choose a loss function L such that م 1 and 2U)) VC (y -Aa) = Idg. Then, if Dj is an e-corruption of D2, we can iteratively compute Ey--D, (y VC - An) and check its top eigenvalue. If it is smaller than 1, we know that jú must be O(VE)-close to j u=,, if not, we can remove points which are aligned with the top eigenvector. Similar to the classical filtering setting, we can argue that this removes more corrupted points than uncorrupted points. Thus, after at most (EE) iterations, we must have that ğ is indeed -(VE)- to μ², A similar argument works for higher-order moments.
Ey-D, VL (y
It remains to verify the assumptions we used on the loss function L and its interaction with our distribution. First, we required that is smooth and strongly convex, which very restric- tive. Fortunately, we can relax the second assumption: For our argument it is enough if L is locally strongly convex around the minimizer (and globally smooth). Second, we assumed that Ey-D, VL (y - (02) ( - Atz) < Ida. VL (d2) can be seen as some transformation of the distribution, and our condition requires that the covariance of the transformed distribution is bounded. In general, this might not be satisfied even if the transformations are well-behaved (e.g., bounded
'In this discussion we assume that the operators E and V commute. In the analyses of the algorithms we use empirical means, and in this case they commute by linearity of the gradient.
8

---

and Lipschitz). However, we show that for appropriate L. it is indeed satisfied for elliptical and semi-product distributions. For the sake of exposition, we focus here only on elliptical distributions. For such distributions, we use the loss function Lε(") == 22 ④b (Ilel /r) for some >> 0. It is not hard to see that it globally smooth and locally strongly convex (in some neighborhood of the minimizer). Further, V (L) is a projection of onto the ball of radius r (with center at zero). The covariance of such a projection is bounded by the covariance of the projection onto the sphere of radius r. Fortunately, spherical projections of elliptical distributions are well-behaved. In particular, they only depend on the scatter matrix Σ, and hence we can without loss of generality assume that the initial elliptical distribution was Gaussian. For which we can obtain bound on the covariance of VLg (y- p2).
Similarly, we show that under mild assumptions on the scatter matrix (that in particular are satisfied for scatter matrices with condition number O(1)) we can certify tight bounds on the moments of V L (y- (12) in sum-of-squares, which leads to polynomial-tina algorithms that obtain error (VE). We remark that prior to this work, in the unknown covariance case, robust mean estimation with error (VE) was only possible under the assumption that higher-order moments of D2 are certifiably bounded in sum-of-squares. We show that error o (vE) is possible for arbitrary elliptical distributions that might not even have a first moment. Moreover, we show that by exploiting O (log(1/E)) many bounded moments of the transformed distributions, we achieve the near optimal error of ( /log(1/e)) using quasi-polynomiall many samples and time polynomial in the input.
The above approach also works for semi-product distributions by choosing L to be the entry- wise Huber-loss. This works both for the setting when VL (y - -22) has bounded covariance and certifiably bounded higher-order moments. We remark that in this case we can achieve the information theoretically optimal error (E)) with quasi-polynome number of samples in polynomial time (in the number of samples) this again follows by exploiting ((log(/=)) many moments.
2.1 Nearly optimal error for semi-product distributions using polynomially many samples
Note that even in the standard Gaussian case, using the standard filtering approach yields (nearly) optimal algorithms only when using quasi-polynn polynomilly many samples. Note that this seems some- what inherent to the approach since it only uses low-degree moment information. To reduce this to polynomially many samples, we can use a stronger identifiability statement that exists for the standard Gaussian distribution. In particular, let D2 N( Id.)) and D, be an e-corruption of D, with mean μ1 and covariance Σi. Then, it holds that DKK 19 DKK 17] (see also (L19))
| uell < O (EV/lo((1/E++ + Ve (| - Idall =log(1/=)))
Thus, can hope to achieve error O (log/)(()/) by checking if [|Σ Idall O(eVloggL)) and iteratively removing points aligned with the top eigenvector of Σ₁ Ida. Indeed, a procedure very similar to this works (see e.g. (L19).. However, it is crucial that we only remove points among the top e-fraction of points correlated with the top eigenvector, since otherwise we cannot ensure that we remove more corrupted than uncorrupted points. The proof of the above uses stability conditions of the Gaussian distribution (cf. (DK22]). That is, the proof uses that for samples ni ....... Th N(u,, Ida) with n sufficiently large, it holds that for all subsets T of size (1 10s) ) we have
n" < (e(lloog((/s) VE
and
1 IT'
Σ n Inn iET
Ida < O(s log(1/e))
We show that the above approach can be adapted to the semi- product distribution with location μa" and Σí = Ey,D, VL p= pT)(V[(y 1 ))" T. where L is the entry-wise Huber-loss. For simplicity assume that Σ6 = 7 Idg for some known y (our approach extends to more general diagonal matrices and unknown 7 as well we show how to estimate all relevant parameters from the corrupted sample). Then, if D, an e-corruption of Dz. we show that for ýu := arg min By,DD L. (y a) it holds that
setting. Indeed, let D2 be
Al - 101l & (EVlog(l/)) + V (1|2f - 7 Idall + a =loo((/E))) 00
9

---

where Σf is defined analogously to Dg. Second, we show that for the filtering approach to work, is enough that the transformed distribution, i.e., V FLy 1²) for y ~ D2. satisfies the stability condition. This indeed follows since for our choice of L (the entry-wise Huber-loss), VL(y , is sub-Gausiian.
However, since we do not work with the quadratic loss anymore, there are several technical obstacles. For the quadratic loss, the gradient is the identity function, and this fact extensively used in the analysis of the Gaussian setting. For the Huber-loss gradient, different arguments are needed. To exemplify this, consider the following example- note that we do not expect the reader to see at which point in the analysis this step is necessary, it should merely illustrate the types of problems that arise. Let Sy denote the set of uncorrupted samples, T _ [n]] be a set of size at least (1 E)m, and (TT) be the minimizer of C over samples in T. In the analysis, terms of the following nature arise
E (a(TT) v.) (C(((T) - v7) BETNS,
(TSSs)
and we need to show that this term is bounded from below, in Loewner order, by (y O(e log (1/e))) (uniformly for all T size at least (1 - n). case of the quadratic loss, this follows easily from the stability conditions by adding and subtracting ji Sg).
When L is the entry-wise Huber-loss, argument, we assume for simplicity that the entries of 17 are mutually independent. We first show that Á - (T) μ² has entries of magnitude O Then we show that for arbitrary but fixed (that is, non-random) with entries of small magnitude, the distribution of VL nn) is sub- uub-Gaussian. We use this fact to show that with overwhelming probability
sophisticated argument is required. To describe
Cov Σ VL(A (L - -n))= = (0 (OL() Tn Sg tErrS,
Then we use the fact that A has small entries to show that Cov (VL(A-1)) (7 (()) Id.. Finally, we use an g-net over all possible A to get the desired lower bound uniformly for all A, including Å. This last g-net argument is where we incur the (possibly) sub-optimal O (d log d) term (instead of the optimal O (d)) in our sample complexity. Finally, if the entries of n are not independent, we need to use this argument conditioned on the absolute values of the entries of r7.
Summarizing, we have shown how to adjust the well-known filtering technique and incorporate the Huber-loss, design robust algorithms for symmetric distributions, often matching what is known for the Gaussian distribution in
time.
Acknowledgments and Disclosure of Funding
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 815464).
References
[Bec09] Ikhlef Bechar, A bernstein-rype inequality for stochastic processes of quadratic forms of gaussian variables, arXiv preprint arXiv:0909.3595 (2009).
[Ber06] Thorsten Bernholt, Robust estimators are hard to compute, Tech, report, Technical report, 2006.
[CGR18] Mengjic Chen, Chao Gao, and Zhao Ren, Robust covariance and scatter matrix esti- mation under huber's contanination model, The Annals of Statistics 46 (2018), no. 1932-1960.
Note that the deviation of f (A ((A-7")) be large. But we can still show the lower bound of the form - Ō(s)) Cov (f (A - )), where Ö(s) does not contain the terms that scale with E (A .7"). This is enough for our argument.
.7")T from mean scales with Ef (A 17"), which
10

---

[Cha83] Gary Chamberlain, A characterization of the distributions that imply mean-variane utility functions, Journal of Economic Theory 29 (1983), no. 1, 185-201.
[CHS81] Stamatis Cambanis, Steel Huang, and Gordon Simons, On the theory of elliptically contoured distributions, Journal of Multivariate Analysis 11 (1981), 3, 368-385.
[CLMW1I] Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright, Robust principal compo- nent analysis?, J. ACM 58 (201 1), no. 3, 11:1-11:37.
[CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant, Learning from untrusted data, STOC, ACM, 2017, pp. 47-60.
[CTBJ22] Yeshwanth Cherapanamjeri, Nilesh Tripuraneni, Peter Bartlett, and Michael Jordan, Optimal mean estimation without a variance, Conference on Learning Theory, PMLR, 2022, pp. 356-357.
[DHL199 Yihe Dong, Samuel Hopkins, and Jerry Li, Quantum entropy scoring for fast robust mean estimation and improved outlier detection, Advances in Neural Information Processing Systems 32 (2019).
[DK22] Ilias Diakonikolas and Daniel Kane, Algorithmic high-dimensional robust statistics, http://www. iliasdi akonikolas orgo tegg/rrs-book påf 2022.
[DKK*17] 17] Ilaas Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart, Being robust (in high dimensions) can be practical, International Conference on Machine Learning, PMLR, 2017, pp. 999-1008.
[DKK*19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart, Robust estimators high-dimensions without the computational intractability, SIAM Journal on Computing 48 (2019), no. 2, 142-864.
[DKLP22] Ilias Diakonikolas, Daniel Kane, Jasper Lee, and Ankit Pensia, Oullier-robust sparse mean estimation for heavy-tailed distributions, Advances in Neural Information Pro- cessing Systems 35 (2022), 3164-5177
[DKP20] Ilias Diakonikolas, Daniel Kane, and Ankit Pensia, Outlier robust mean estimation with subgaussian rates via stability, Advances in Neural Information Processing Systems 33 (2020), 1830-1840.
[DKS17] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart, Statistical query lower bounds for robust estimation of nigh-dimensional gaussians and gaussian mixtures, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 73-84.
[DKS19] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart, Efficient algorithms and lower bounds for robust linear regression, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2019, pp. 2745-2754.
[dIN+21] Tommaso d' d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, and Stefan Tiegel, Consistent estimation for pca and sparse regression with oblivious outliers, Advances in Neural Information Processing Systems 34 (2021), 25427-25438.
[dNNS23] Tommaso d' Orsi, Rajai Nasser, Gleb Novikov, and David Steurer, Higher degree sum- of-squares relaxations robust against oblivious outliers, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2023, pp. 3513-3550.
[dNS21] Tommaso d' Orsi,, Gleb Novikov, and David Steurer, Consistent regression when oblivi- ous outliers overwhelm, International Conference Machine Learning, PMLR, 2021, pp. 2297-2306.
[DTV16] Alexander Dürre, David E. Tyler, and Daniel Vogel, On the eigenvalues of the spatial sign covariance matrix more than two dimensions, Statistics & Probability Letters 111 (2016), no. C, 80-85.

---

[Fan18] Kai Wang Fang, Symmetric multivariate and related distributions, Chapman and Hall/CRC, 2018.
[Fra04] Gabriel Frahm, Generalized elliptical distributions: theory and upplications, Ph.D. thesis, Universität zu Köln, 2004.
[GLP23] Shivam Gupta, Jasper CH Lee, and Eric Price, Finite-sample symmetric mean estimation with fisher information rate, The Thirty Sixth Annual Conference on Learning Theory, PMLR, 2023, pp. 4777-4830.
[HL18] Samuel B Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs, Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, 2018, pp. 1021-1034.
[HL19]
How hard is robust mean estimation?, Conference Learning Theory, PMLR, 2019, pp. 1649-1682.
[HI.720] Sam Hopkins, Jerry Li, and Fred Zhang, Robust and heavy-tailed mean estimation made simple, via regret minimization, Advances in Neural Information Processing Systems 33 (2020), 11902-11912.
[Hubll] Peter J Huber, Robust statistics, International encyclopedia of statistical science, Springer, 2011, pp. 1248-1251.
[c1770] Douglas Kelker, Distribution theory of spherical distributions and a location-scale parameter generalization, Sankhyā: The Indian Journal of Statistics, Series (1970), 419 430.
[KMZ22] Pravesh K Kothari, Peter Manohar, and Brian Hu Zhang, Polynomial-time sum-of- squares can robustly estimate mean and covariance of gaussians optimally, International Conference on Algorithmic Learning Theory, PMLR, 2022, pp. 638-667. 667.
[KS17a] Pravesh K. Kothari and David Steurer, Outlier-robust moment-estimation via sum-of- squares, CoRR abs/1711.1158/ (2017).
[KS17b]
Outlier-robust moment via sum-of-squares, CoRR abs/1711.11581
(2017).
[KSS18] Pravesh K Kothari, Jacob Steinhardt, and David Steurer, Robust moment estimation and improved clustering via sum of squares, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1035-1046.
[Li19] Jerry Li, Robustness in machine learning, lecture notes, httpp::://eerrryll.giitttt htrrrbusstmllfflllla html 2019, Lecture 5.
[Lin75] John Lintner, The valuation of risk assets and the selection of risky investments in stock portfolios and capital budgets, Stochastic optimization models in finance, Elsevier, 1975, pp. 131-155.
[LRV16] Kevin Lai, Anup B Rao, and Santosh Vempala, Agnostic estimation of mean and covariance, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, pp. 665-674.
[MSS16] Tengyu Ma, Jonathan Shi, and David Steurer, Polynomial cimeomial-time tensor decompositions with sum-of- num-offsquares. squares, FOCS, IEEE Computer Society, 2016. pp. 438 446.
[MZ23] Arshak Minasyan and Nikita Zhivotovskiy, Statistically optimal robust mean and co- variance estimation for anisotropic gaussians, arXiv preprint Stt:2230100902.. (2023).
[OR83] Joel Owen and Ramon Rabinovitch, On the class of elliptical distributions and their applications the theory of portfolio choice, The Journal of Finance 38 (1983), no. 745-752.
12

---

[PBR20] Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar, A robust univariate mean estimator is all you need, International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 4034-4044.
[PJL20] Ankit Pensia, Varun Jog, and Po-Ling Loh, Robust regression with covariate filtering: Heavy tails and adversarial contamination, arXiv preprint arXiv:2009.12976 (2020).
[RHRSII] Peter Rousseeuw, Frank R Hampel, Elvezio M Ronchetti, and Werner Stahel, Robust statistics: the approach based influence functions, John Wiley & Sons, 2011.
[ST21] David Steurer and Stefan Tiegel, Sos degree reduction with applications to clustering and robust moment estimation. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2021, pp. 374-393.
[Sto75] Charles Stone, Adaptive maximum likelihood estimators of a location parameter, The annals of Statistics (1975), 267-284.
[SZF20] Qiang Sun, Wen-Xin Xin Zhou, and Jianqing Fan, Adaptive huber regression, Journal of the American Statistical Association 115 (2020), no. 529, 254-265.
[TJSO14] Efthymios Tsakonas, Joakim Jaldén, Nicholas D Sidiropoulos, and Bjöm Ottersten, Convergence of the huber regression m-estimate in the presence of dense oulliers, IEEE Signal Processing Letters 21 (2014), no. 10, 1211-1214.
[Tro15] Joel A. Tropp, An introduction to matrix concentration inequalities, Foundations and Trends in Machine Learning (2015), no. 1-2, 1-230.
[Wai19] Martin J. Wainwright, High-dimensional statistics: A non-asymptotic viewpoint, Cam- bridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2019.
13

---

A Overview of Appendices
We will provide general framework underlying the proofs of Theorem 1.5 and 1.6 in Appendices C to We will instantiate it to prove (a slight generalization of) Theorem 1.5 in Appendix H and to prove Theorem 1.6 in Appendix G We will prove Theorem 1.4 in Appendiies H H|and Appendix H] contains the proof of identifiability and Appendixx containss the adaptation of the filtering algorithm.
As alluded to in the introduction, we will consider the following (slight) generalization of (p)-semi- product distributions (Definition 1.2) which allows for even less probability mass around the location. Setting TOG recovers Definition 1.2.
Definition A.1 (Semi-Product Distributions (generalized form)). Let p. a > We say distribution distribution, if for n ~ ' holds that
DD over R is an (as,
1. For all j E [d], the distribution of ny is symmetric about 0,
2. For all j E [d], IP (mnl= < p) aa. a,
3. The random vectors (sign( (n ))= and (m,,))= are independent, and the random variables sign (mn (na) are mutually independent.
We will prove the following two (slight) generaliztations of Theorems 1.4 and 1.5. Setting recovers Theorems 1.4 and 1.5, respectively.
106
Theorem A.2. Let μ E,, > and D be a (a, p--ssemi-produee distribution with location μ². Let C' > O be a large enough absolute constant and assume that A/c & a/C and n > C. +lgoog))+lgg(/// (1n((188) Then, there exists an algorithm that, given an e-corrupted sample from and a. a²z² log(1/e)
runs in time ((1) and outputs jt Bd such that with probability at least 1 it holds that
l lIa- 111 & =0 (0.
dllo(()) + +log(1/5) a'n
+ & a3 (log(1/E)
Theorem A.3. Let μr" E ,, 0 and 'D be a (a,, p)l-smmi-roduuce distribution with location μ², Let C > 0 be a large enough absolute constant and assume that & a/CC and n 2 o dCooo( Then, there exists an algorithum that, given an e-corrupted sample from 'D and a, runs in time n ((1) and outputs fa E Idd such that with probability at least 8 it holds that
C.
=0 < p [V
log(1/8) an
1)
We remark that if, the algorithm receives as input, the error guarantee improves to
d (og(1/)
p n² < p-
an
Note that for the setting of a = 1/100 discussed in the introduction, both guarantees are the same (up to constant factors). Further, p is given as input, is not necessary to receive a as input. We emphasize, that p need not be known, and can be estimated from the corrupted samples (given a).
We also remark, that upper bound on the fraction of corruptions is qualitatively tight, since can be at most roughly a: Consider a mixture distribution that with probability 1 - a outputs a sample from N(r", Ida) for x² arbitrarily large and with probability outputs sample from N(u",Ida)) This is (a,
Yet, if an adversary changes the N(p", Ida) component
to Ni IdId)), we cannot hope to achieve error better than o² d+log(1/6) which can be arbitrarily large. We did not attempt to optimize the range of allowed for our algorithms.
B Preliminaries
Notation We use bold-font for random variables. We use regular (non-bold-font) for random variables that potentially have been adversarially corrupted. Further, we use Z and S to suppress absolute constants which do not depend on any other problem parameters. For μ. we denote by supp(u) its support.
14

---

Sum-of-Squaree Proofs and Pseudo-Expectations In this section, we will introduce sum-of- squares proofs and their convex duals, so-called pseudo-distributionn
Let p: IR= + IR be a polynomial in formal variables X = (X1,..., x2) We say the inequality sum of squares in X1, Xn, Further, if every polynomial in this decomposition has degree at most t, we say that the sum-of-squaree proof has degree-t t and write p T
p(X) > has a sum-of-squares proof (short SoS proof) if we can write p(X)
LX
> O. We write A 1 p 2 p' if A A/ p p- > 0
and A XX p p' if A composition rule holds: If
p & p' and A
X
t
P
> p'. It is not hard to verify that the following X > p", then it also holds that 1" p 2 p", where
p 2 p' and f
X
p'
t" max{t,t')
Next, we introduce so-called deeudo-distributionn the convex duals of sum-of- proofs: For d E Nz1, degree-d pseudo-distribution
sripely-suppored function μa: IR - E such that Enesupplay [(x) 1 and Esupppty (x) 2 for all polynomials of degree at most d/2. pseudo-distribution z is defined as the linear operator mapping a degree-d polynomial f Euf == Emespptio f()) We say that pseudo-distiribution E, satisfies a set of inequalities {41 b 0,... 9m 2 0} at degree r, if for all S S [ma]] and h sum- of-squares polynomial such that deg (h- [lses) & r it holds that
The pxeulo-expectation corresponding
Eych- ] > 0.
We relate pseudo-distributions and sum-of sqqurees proof's using the following facts.
Fact B.1. Let μ be a degree-d pseudo-distribube distribution that satisfies A and suppose that A l7 p 2 O. Let h be an arbitrary sum-of-squee
polynomial, ie h + L & d we have F. p 2 O. In particular, we have E,p 2 0 as long t & d. If only approximately satisfies A it holds that E,P > -nllhll2 for n = 2 n00 Further, if there no degree-d sum-of-ssuare proof that A T p 3 0, then for there exists a degree-d pseudo- distribbitti Ey satisfying A and E > O such that E,P < O.
An essential fact is that sscudo-distribution. approximately satisfying a system of polynomial inequalities can be found efficiently as long as the constraints have bit-complexity at most (m + 00),
Fact B.2. Given any feasible system of polynomial constraints A {qi > O,..., Qm > 03 over In whose bit-complexity satisfies the constraints mentioned above and = 2-)
oid)
we can in time
(n + ()d( find a degree-d pseudo-distributinn that satisfies A up to error n).
C Proof of Identifiability based on Transformed Moments
In this section, we give a formal proof of the statement of identifiability based on transformed moments that we sketched in the Techniques section. We will give the proof assuming an abstract set of assumptions and verify that they indeed hold for semi-produce and elliptical distributions in Appendices F and G
We use the same notation as in Appendix H. with the only difference being that we now use an abstract loss function: Let F: R - IK and denote by f = F its gradient. Further assume that F and f are such that f is 1-Lipschitz. For w E R. with non negative entries, we define " Idd R as
(²) = Σ F.F (μ 14-2) y1) ())
i=1
It follows that v En wil (μ w:). Let 2k N22 and define ju()) minpers L (n)
as well as
m2x
max wES4-1
(s())), 2)
and
mi
max VES4-1
wi ( (f vi) 22
For technical reason also assume that A is explicitly bounded meaning it contains constraint of the form | & B for some large number B. Usually we can even take this to be at least polynomial our variables. We remark that for the problems we are considering this can be added without changing our proofs. 'The positivity and normalization constraint can be satisfied exactly however.
15

---

We will prove the following theorem.
Theorem C.1. Let a E (0, 1) and let k be a positive integer and W2s. Suppose that ex de < 0.01 and
allAa t - 1 112
& -0 (4²), 11= - 11"))
Then
100 11 Th 1 E
ト ト f (m:)
+ # (mig + m2x)
a
This theorem easily follows from the following lemma. Lemma C.2. Let k be a positive integer and W2s. Then
n (1)
(VL" (1²), u) & 5. ||a||
(m
+ 0-- de .(ii + 1822 + |lull)
1=1
where u = j((w)= - p.
We first give the proof of Theorem C.I
Proof of Theorem C.I
Let j(w) R¹, Using Lemma C.2 and gl- d < 0.01 a, cancelling the common factor of |u|| and rearranging now yields
(m)) (1 n (1=ErOm))
100
|u/|
+e- # (m + m2x))
Next, we prove Lemma C.2
Proof of Lemma C.2
Again, let u = ju(w) k², We can decompose L L (1²)), u) as
(VL" (n²), u)
wi (5 [11² -y:), ,
1=1
(f (f** u) + Σ
1
w. (f vs) ff (x= -vi), (i E So}
1=1
For the first sum,
Σ wi (f (n² v.), = Σ wi (f (n u) &
Σ
f (n))
|| Σ (w: 11) ($ (Tt).
By Hölder's Inequality,
1-st
(w: +) (f(())
<
Σ #1
# (f (n²),u}"
< 4 d
m2
||u|].
For the second sum, we bound using Hölder's Inequality
*
n
1 {i E S.} w. (f (n" vi) f (4² ,,), u) Eel- -
Σ w; - (f (μ" -y1) (n"
yy u)
24
1- #
Σ wi (1=" yi) - (10 v.) - f (a wi) + f (f- - yi) u) 26
16

---

22
n
<E-- 2
Σ ws
u)
-1- 2
Σ wi (f (Ø yo) u)26
Σ
wy (f (4" - y.) - (f vi) u4 u2)28
We bound the three terms in the square bracket one by one. The first term can be bounded as follows
wi (f (m7 u) 24
1 (f u)
m2 [/] 2k
The second one is at most m |u|| by definition of m For the third, we use that f is 1-Lipschitz to bound
at
Σ wy (f(#" vi) - (Ø (0-),,,, 22)
<
Σ 1=1
w;
Ilf (n² -yi) (Ā- will ||z||
< ||/1
It follows that
E (iEE wi (J (n² yy) {p" -,)) u) < Se'-2u || (m + 12x + ||ul])
Putting all the above together, we obtain the desired bound.
D Filtering Algorithm for Bounded Clipped Covariance
In this section, we show that the filtering algorithm for robust mean estimation under moment constraints (cf. for example [Li99] DK22) can be adapted also yield an efficient algorithm for robustly estimating the location parameter of symmetric distributions. For now, we focus on the case that & = 2. we discuss the extension to higher moments in mn/ppendix Again, we will focus on the abstract setting and show that we can apply these results to semi-product and elliptical distributions. We will closely follow the exposition in Li19 DK22]
Recall that we denote (w) = Ei= W;F (μ yi).
Assumption D.1 (Goodness Condition). Let F: Rd 4² E R
-R.f= VF be such that is I-Lipschitz. Let 0 < a,0 0 < a < and yi...., Vn. E Rd. Let a distribution over IR and mi,.... .., , be s.i.les from D. We say that the goodness condition holds, if
1. aflji" 1=1 2 < 10 (VL (1²"), n² )r))
2. 1 o (m) T0 o.
3. i. = max
(f (f Eo.
Under this condition
show the following theorem.
Theorem D.2. Let μ²¹ Rd 0 < 0,0 < 1,E 0, and ........ n" be i.i.d.samples from some distribution D over Rd. Assume that ve < 1000 Let yi....,y, Yn be an E-corruption of 1 + Vn ....,, μ² + nh Assume Asssmmtton D.I (the goodness condition) holds, then Algorithm D.3 given ....... ... Un and terminates after most 2en iterations and computes such that
[HE
VE V.....
1 50
Moreover each iteration be implemented in time 0(1) (())
17

---

To describe the algorithm, let C > be some universal constant and for I w E W. let
p(w) min
L (11)
HERd
My (w) Σ
wif (f - Vs) f (ft y1)
We will use the following Filtering Algorithm:
Algorithm D.3 (Filtering Algorithm), Input: e-corrupted sample "1..... Un and a >> Output: Location estimate jt
Let w(
n K
Compute f((0) min -n (n) and 1i Ey (wolO)).
Let t = 0.
|=
while
100 do
Compute (*) the top eigenvector of 2
For E [n]. compute 7.(1) (u(1), (p - y1)) )
For E [n]. set w (+++) = (1 Tanax w
(1)
where Tmax maxiee(n Ti.
Compute p(++1) piR fulltt) (4) and EXt1) E, (w(++1)).
+
Output p(0))
The proof of Theorem D.2 is very similar to the one in L19 whose proof we will give at the end of this section
We will use the following lemma
Lemma D.4. Assume that Theorem D.2
|
>
100 a and
w
(t)
w (1)
72
n
ieS
Then
Σ
(++1)
wi (e+1))
w
#ES,
SESb
With this in hand, we will prove Theorem D).
Proof of Theorem D.2 First note, that every iteration clearly be implented to run in time o0 (11), First, we will show that the algorithm terminates after at most [2en] iterations. We will prove by contradiction. Suppose that the algorithm does not terminate after T = [2en] iterations. Note that the number of zero entries of (+) increases by at least in every iteration. Hence, after T iterations we have set at least entries of w to zero whose index lies in Sy. By assumption that the algorithm didn't terminate and Lemma D.4 holds that
Sbb
(T)
(T))
w
w
<
EE.
n
n
iES
SES,
which is contradiction.
Next, we prove the correctness of the algorithm. Let T be the index of the last iteration of the algorithm before termination. Note that by our invariant
w
(T)
=
w (T)
< 25.
LE S
RES
NES,
18

---

Since also 0 & w(T) it follows that
1, follows that w()) W2e. By Theorem C.I and since | n
100
1 f (nfi)
+ VE
11 - 1011 &
0
Lastly, we will prove Lemma D.4
Proof of Lemma D.4 For simplicity, let w = (1()) and w' = w((+1), Note, that it is enough to show
that
Σ
w
10 w.
iSS
iESp
Further, recall that w! = (1 show that
Wis so for all E
[n]. w/
w/ T-W. Hence is enough to
Tanax
Σ
TWW's <
Tells.
KES
iES
Since Sg and So partition [nx] and
Σ W Σ wi (u(t), S -w)) (vl0) 2260) (v(t)) = =|>000
we can prove Eies, Teuly < Eies, Tww; by showing that
|>
Σ Tw,; 2
To this end, note that
Σ w/ (u(0), ff (210) - :11)
Tawls =
iES,
iES,
2
(0(0), If (m--wi)) -vi)
2
(0(), .f (R -y1) -1)- f (1¹ - bi) -vi)
+
n iE(x)
|
iES,
The first term at most 20 For the second term we observe that since ʃ is 1-Lipschitz for all i [n] it holds that
(00)), f (pt0 w.) fp= (w---v))" -i)) & 1 (B - v.)
(4" (w---)) mill
< |0000 w0(
Hence, by Theorem C.I.
+ Ve 2000 )2 (11)
1002 Σ Tal & 202 + ||( 3011² < 20 +
smn)) 1=1
a²
2
VeS,
where we used & S a² and || Σ. / (n $ ao.
E Filtering Algorithm for Bounded Higher-Order Clipped Moments
In this section, we show how adapt the filtering algorithm to incorporate higher-orded moments of the transformed noise. We follow closely the exposition in [D222 Chapter 6.5). In particular, consider the following definition similar the by now standard notion of ceritfially bounded moments or certifiable subgaussianity [SS188 HL.18 Let f: Rd -> IRd be some function.
Definition E. Let k. E and a > O. We say distribution D over Rd has (2k, -)-certifiablly g-bounded f f-moments if there is degree-E SoS proof (cf. Appendix B), in formal variables v, that
E (f (n) v) 2h < (a [[b|]) 26 DD
19

---

We again define goodness condition analogous to Assumption D.I Specifically, we assume
Assumption E.2 (righer-Order Goodness Condition). Let F: R - R. = VF be such that is 1 I-Lipschitz. Let μ= E R 0 < a, 0 < < 1, E N and yI..... Un R Let D be distribution over IR" and ,....., Th n i...d.smples from D. We say that the higher-onter goodness condition holds, if
1. 0-IA" 2 10 V (4") , ;
2. 1 E. f (m 100 9,
3. the uniform distribution over the set {mi..... , has (2k, -ecetiiiiay o-bounded f- moments. In other words,
(s(m)) < (a -lol))
Specifically, we will show
Theorem E.3. Let μº E R 0,000,00000
N, and wi..... Mi be i.i.d.samples from
some distribution D over Rdd. Assume that e' & 1000 Let yı,..., Un be an e-corruption of yi =p + :......bU Vn = 1i Mi. Assume Assumption E.2 higher-order goodness condition) holds, then Algorithm E.4, given , Yn and o, terminates after at most 22n + iterations and computes such that
( a
c cl-st Z
a
Moreover each iteration can be implemented in time n 0(1) dle)
Additionally the notation introduced in Appendix D consider the following polynomial in formal variables
(v)
Σ S f(n 22)
In what follows we will write pdd as just p())
Algorithm E.4 (Filtering Algorithm). Input: e-corrupted sample yi..... Un and O. Output: Location estimate f.
Let (0)
Compute fl()) min Li (n).
Let t = 0.
while there is no degree-l SoS proof (in variables v) that ((9(6) < (100 a ||ol))2k do
Find degree-l
that satisfies the constraint ||i|2 1 such
that Ep' (v) (99 0
For E [n]. compute 7( = (w. (f(0) - y1)) 2k
For E [n]. set w (1+1) (1 Tinax w
where Tmax = max4e[n] To.
Compute ((++1) = min peRd fulll1))
(11).
+
Output p())
The proof of Theorem E.3 is very similar to the one of Theorem D.2
Again, we will use the following
lemma whose proof will give the end of this section
20

---

Lemma E.5, Assume that
Σ
Σ
(8)
wi
7
SES
and (v) & (100-o o- ||uul() does not have degree- SoS proof. Then also
Σ
((+1)
(++1)
w
:ES n
72
VES.
With this in hand, we will prove Theorem E.3
Proof of Theorem E.3 First, note that by the facts in Appendix B we can compute the pseudo- expectation in each iteration in time n (1))) and hence, every iteration can be implemented to run in this time. Exactly as in the proof Theoree D.2 we conclude that the algorithm terminates after I < 2an + iterations and that w" E W2ee.
Recall that
Σ to (f (ft 34),
22
DES
wESe-1
By Theorem C.I it follows that
gl-1/(26).
(may" + 1i
a 1=
a
Note that since the uniform distribution over {ni ( mh has (2k, certiiiiay a-bounded f- moments, it holds that m2x & a. Since the algorithm terminates after T iterations holds that fww" < 100a which completes the proof.
Next, we will prove Lemma E.5
Proof of Lemma E.S Again, for simplicity, let w(() and w/ w(++1) As in the proof of Lemma D.4, is enough to show that
Σ ES
TeWls
Further,
W Σ B J (n -= BB'(v) > (99 /
1=1
Using Fact K.
we continue to bound
T
Σ
w.F
(u, (2 -y)))
i
< 4th
E (v. (n)))
Σ E v (0,
(200) - v.) -v.) - (1- )11) 2h
n
S
kE(m)
ieS,
The first term at most
2h For the second term, notice that by Fact K.2
2k
v.
- v.)
(μ² v1)
2k
||0 |s (Rt0 y/ (4² 344)
24
< ||
(200
14"
2k
Hence, the second term most || - 10 12
2k By Theorem C.I follows that
| Em (nti) cl-1/(2k). (my" + m22
| - m²1 < 100
21

---

Recall that 22 < a. Since
22
Σ Wi (f (ft Ye), 2) 2k
max -434-1
max
wE34-1
8 11-28 ạσ
and
E / (nt)ll
<
100 0 we get
a
1090
Σ
TwW; < 0.2. 1.222Ep'(v)) Ep)(v) + 0.1 (99.0) o) < BBy(v))2
F Product Distributions
In this section we prove that (a, -esemi-prrod distributions satisfy Assumption D.I with o = (p) and with F' equals to the entry-wise Huber loss function with parameter 2p:
F(x)
P2p (1z)
j=1
1 dd .log (d/8), then with probability 1 1 as long as n 2 d+-lg((18)) Moreover, if in addition n 2 az a
Assumption E.2 is also satisfied. We can use this prove Theorem A.3 as follows: Let ....... n
follow an (a. (o]-semi-produe distribution. We will see in Lemma F.3 that for any n, it holds with
118) Hence, by Theorem E.3 (or probability at least 1 8 that || ("=1((m)) < p...
Algorithm D.3 for = 1) it follows that as long as n Z A 1) our estimator achieves error
1 a
24log for dh log(d/o) (or n
o ( EH 8 fm))
E
=0 p.
d + log(1/5) ann
Note that similarly to Theorem 1.6, for < k < O[log[1/e] we get a sequence algorithms interpolating between error Ve and E (using roughly d samples).
Letting &o = O(log(1/=)) proves Theorem A.3
Note that f = F is indeed I-Lipschitz since the derivative of the Huber loss is Lipschitz. In the next to lemmas we prove the first assumption from Assumptitii D.I
Lemma F.1 Let w E Wh for S a. Suppose that n 2 log(d)/a. Then with probability
1 - exp (-Ω ((m)) for all u E IRd such that [|u]|max & p.
- (n² + u) - - (xxxx²) - - (1²) 1) > a
||ul|22
4
Proof. Let j E [d] and Gi = / - Vi-
a
C (ng + uz) - cy (nz) (CT) (Pz) Uy Σ wi (Giz + u,) - (Gig) u, u, +
Let M be the set of uncorrupted samples such that Kyyl = Inyl < h/2. Note that for i E M,
(Gi + uz) = 2Kis + u and + (Suj + uz)) 1 2 Hence
Σ wi ( (Sag + u2) (Cty) uy @ (Sty)] MM
Σ
u.uy.
And by convexity,
Σ w. 1 (llc: + u|l) - T (I1)l)) (5 u)) > 0. M
22

---

Since E W2e,
W
< 2
12
1EM
Hence
M 28.
Σ SEM
Wi
n
By a Chernoff bound,
0.9a
a/2
with probability 1 - --epp(-on (-an). The result follows from union bound over all j E [d].
Lemma F.2. Let w E W2s for S a, and suppose that 2 log(d)/a². Then with probability 1 cxp (-2 (a?n).
(VL" (4²) , - > 7 f1a 1=1
Proof. Fix j E and let u, = 14 ()(w)). Let ui and be such that
|u/1 & p: kr(w)= Uí + t u/j
u.
follows that = max (1, [uy]]. Clearly, Ps (w) is the (unique) minimizer of cy. Let ftz = , + ufj- by convexity of Dy it holds that 2 (p/) & Ly (mj). Since lu')l & p it follows by Lemma F.l that cy (u)) Cy (R()) > 2 (nz) + (ET) (nz) (-u²))
a ā (u/)
with probability at least exp (-S (an)). Rearranging yields
|u/1 $ (ET) (xz)
We next examine
(CT) (nz) =
Σ wi ((vi), -11)
==
Σ wis (mi)) +
Σ wi [6 (wv)) - -w3) - - (wi),
ie5o
By Hoeffding's inequality,
Σ w. (mis)
< Σe o (ni))
+ 2pp < 2pT/ / + 4pe
with probability at least - exp(-r2
The second term can be bounded as follows:
Σ
( (1g (u:),) - (13--((0) -vx1) < 4pe,
W:
VES.
where we used that for all 2r R it holds that (x(x) everything together we obtain
p(v))l 2p and Eies, wi 2e. Putting
2r
4pE
|u/1 & a
with probability 1 exp(-r2 For /v 10, |uśز < p. Hence, t since otherwise
|4ا1 = 1: (w) - M3 = =
=t.lu/ |u/s1 < |uyl-
It follows that u/y uy and thus (ā)(w) 11] p.
23

---

By Lemma F.1
- (p²) L (p) > L (1¹) + (VL (x"), , -2) + |11
Hence
(VL" (4²), 1) > a 4 |1||2
In the following lemma we show that Assumption 2 of Assumption D.1 is satisfied for = (p)
with probability 8 as long as n 2 d++og(1/6).
a²
Lemma F.3. With probability at least 1 1- 8.
d log (1/6)
f
(mh)
E 10pp
m
n
Proof. Let u E R.d be some fixed vector. Since sign (1) is independent of abs (1)), random variables Uig = U2 Masl independent of sign (1)) By Hoeffding 's inequality
1
(n:) 1
sign (ny) زig & 2p ||u|| T/Vn
with probability at least exp(--²/22 /2). Let N1122 be 1/2-net of size 6 in the Euclidean unit d-dimensional ball. Then
n (mz) ,
1
Σ (mi) ,u) v
sup [u]]<]
(mi)
< sup |/l|
sup
7
nENi,21/2
Hence by union bound,
x Σ i=1
n 1
2 2In(6) d log (1/8)
f (m)
sup
f (m))
2 sup w/N1/a
n Σ f (m fm:)
< <4p/
|
n
n
In the following lemma show that Assumption 3 of Assumption D. with probability 1 8 as long as n 2 d + log(1/8).
is satisfied for (p)
Lemma F.. Let 8 E (0, 1) and suppose that n > + log (1/8). Then
Σ (m)
<0(
n
with probability at least 1
Proof. Let E Rdd be fixed vector. Since the random vector sign (17) is independent of abs (1)) the random vector abs (f (1)) with entries uy |n(i) is independent of sign (1). Since the entries of sign (17) are iid Rademacher, for every positive integer k.
sup E (ʃ (1) u) 24 < sup T. (sign (17) abs (S (17) u)**
[|]]|<1
[|]]@1
< sup
E (sign (1)) u)
||
< (2p) 2h
sup E (sign (n), u) 24
||
< (2p) 24
Hence (n) is 2p-subgaussian and the result follows from concentration of empirical covariance for subgaussian distributions (see Theorem 6.5 in (W).

---

In the following lemma we show that Assumption 3 of Assumption E.2 is satisfied for o = O(p) with probability
6 as long as n Z d log (d/6).
Lemma F.S. Let k be a positive integer and suppose that 10 d logg (d/8). Then with probability
at least 1 - ö, uniform distribution over the set { No has (2k, -ke-cttif 4p-bounded f-moments.
Proof. First we show that the random vector 1 has (2k, 2k) 2k)--certfiabbl 2p-bounded f-moments. Let's call multi-index 3 even if every element in 3 appears even number of times. Note that / is even iff 3 = 2,3" for multi-index 3' of size k. Denote by & the set of all even multi-indice of size 2k. Let , Va be variables, and consider the polynomial IE (f (m) 2) 2k It follows that
v E ( (1) 2)26 2k
E
(sign (11) abs (ʃ (7)) e)
abs (ʃ (n))
E
E
sign (n) (abs (f (1)) o o))² abs (f (n))
BEE
E
Σ
(abs (f (m)) 8)
SEE
(2p) 2
BEE
(2p) 2k
0 2,'
| mm
(2p) 2h
||0
Hence 77 has (2k, 21)) certifiablle 2p-bounded f f-moments. Since Vo E Rd, [I (x)]l & 2pvdd the result follows LemmaL J.4]
G Elliptical Distributions
In this section we use a different normalization than the one described the introduction. Concretely, we assume that TrCE) and that for some p >> and (0, 1). R < pvd > a. For a = 1/2. this is the same model as in the Introduction, since we can multiply 112 by s= / Tr (Σ) and divide R by Hence the new parameter P written in terms of the parameters defined in the Introduction is equal v2/s = / Trr)/dd Note that p ||E|| in new notation is equal to v2 ||E|| in the notation used in the introduction. Note that the effective rank, r(E) |Σ parametrizations.
is the same in both
We assume that is known. In the case of unknown @ and > 9(1). we can estimate using the corrupted samples and obtain the same guarantees as for known p (up to a constant factor). We describe how to achiev this in Appendixx G.T
We prove that elliptical distributions satisfy Assumption D.1 and with, a = Opv and F:
2d + IR defined as
F(x) + 20pva a (1|=1)
with probability 1- as long as n 2 then Assumption E.2 is also satisfied with O(p k / ETD)
r(E)) log(d/6)
Moreover, if in addition n > d (()) k -lgg (d/8).
a
Going back to the parametrization of the introduction and letting a = 1, this means the following: For n P r(E) log(d/8) elliptical distributions satisfy Assumption D.1 with a ((V[[E)) Further, if 2
a
1 (1 of
k log (d/5), they satisfy Assumption E.2 with O(/k|| [|]] Further, for .i..... m
following an elliptical distribution with the above parameters, we will in Lemma G.4lshow that for
> log(1/5) it holds with probability at least 1 5 that || Σ. f(nill & O(y (r(2))
25

---

Hence, by Theorem E.3 (or Theorem D.2 for k = 1) our estimator achieves error
o ( f (m))
+ - # o =0 (VIETl- r( r(=) log(d/6)
+ vks - #
This gives the proof of Theorem 1.6.
Note that / VF sends to (20pva T=Т and hence is indeed 1-Lipschitz since it is the projection of onto the b--ball of radius 20pvd. d. In the next three lemmas prove the first assumption vromAAssumpiinn D.I
Lemma G.1. Suppose that > 100. Then
RE 12
< h/2
0.8a.
where h = 20
Proof. Let 9 N(0, 1)) be a d-dimensional Gaussian vector such that g 9= R2 where R' is independent of R and has distribution of the norm of Gaussian vector 2pd)p)) Note that Tr gEgg*) 4p²d. Applying Fact J.6 with t 2, we get
|لو|| > 10pVa] < exp( < 0.15.
Since
P R'' > pvd 0.99,
we get
|لل|| < 10pvd, R' > pvd 0.8.
Since R is independent of g and R', we get
P RE RE u
10v2
> P
RY 1/2 u < | |191| < 10pvd
12
P
R
x R',
||l||
< 10pvd]
P
R
pvd R' > pvd.11g1 |191| < 10pvd
0.8a.
Lemma G.2. Let w E W2e for E S a. Then with probability exp (- (am)) for all u E IR such that ||u|| & pvd.
a LD + u) - -0 (4²) VVL (4²), u) >
||u||2
4
Proof.
Let Ci = 14-110 yi-
- (μ² + uu L (μ²) (L" (p"),
Σ wa [f (IIc: ull) f ((1:l)) (G:) ,
Let M be the set of uncorrupted samples such that ||ail |lmil < h/2. Note that for i E M. f (1ls, + u/l) = 1 I& + ull and o (IIGil) = 1 2 Hence
Σ wy If (llC+ wIl) - (11c.1)) - (f (c.) (s)).)) iEM
Σ JEM
wy ||
2
And by convexity,
Σ wa If (llc: + u|l) ((1s)l) (f (Si), m²) > 0.
M
26

---

Since E W2e,
W;
< 2
12
Hence
M
Σ S
Wi
28.
n
By Lemma G.1 and Chernoff bound,
[ 0.60 E a/2
with probability - exp (-an).
Lemma G.3. Let w E W2s for S a, and suppose that n 2 log(d)/a². Then with probability 1 - cxp (-0 (a?n)).
VLL (1²), 1²= p2") > 11 1=112
Proof.
Let u= 10¹ - -(w). Let u' and / be such that
||''ll < pvd, jdw) μ¹ +t.u'.
It follows that t = max (1, [|u]]]. Clearly, ((w) is the (unique) minimizer of L Let ji' 1 + u' by convexity of L it holds that L ("') & L (μ²). Since || & pvd it follows by Lemma G.2 that
C (x^) > L (A') e L (μ (VL" (u*), u) - ||ul
with probability at least - exp (- S2 (an)). Rearranging yields
4 α
||''ll
|VL (n²)
We next examine
L (1²)
Σ wif ((vi) - -1²)
Σ wof (m.) + Σ
If (()) -²) f(x)))( -x))
SE
By vector Bernstein inequality Fact J.2
Σ
wi (md)
Σ (m:)
< 200pvd. (T/Vi+ + 72/n) + 400pp/d
with probability at least - exp( - 72/2).
The second term can be bounded as follows:
Σ
wi [S (1r- (v:)) I (1r- - -u:))) < 40cpvd,
IES
where we used that for all 2, E IR it holds that 1f(x) f(y)l < 20pvd and Eies, wi & 25. Putting everything together we obtain
|u''l & 200 pVd PVd
(T/V + 40
with probability 1- exp(-r2/2) /2) For 10/n/10000 |u' < p. Hence, since otherwise
|u|| [[(ww) 4 =t ||/ |
27

---

It follows that u' = u and thus llā(w) - 1e < pvd.
By Lemma G.2
- (p') > L (2) > L" (4²) + /V (1*), -2) + 4
12
Hence
VVL (1²) u} > a z ||u|
In the following lemma show that Assumption 2 of Assumption D.1 is satisfied for O(p ||>]])
with probability 8 as long as n 2 dloo(d/8))
a²
Lemma G.4. Ler 8 (0, 1) and suppose that i log (1/6). Then with probability at least 8.
Σ (m))
< <0
dlog (d/6)
PV
Proof. The lemma is a direct consequence of vector Bernstein inequality Fact J.2
In the following lemma show that Assumption 3 of Assumption D.1 is satisfied for (p) with probability 5 as long as n Z dl dloo(d/6).
Lemma G.5. Let 5 10 and suppose that n 2 r(E)) log (d/5). Then
n Σ (m)
< < (EII)
with probability at least 1 - 5.
Proof. Let (n)
!! n و (n), where 20pvd. Note that ||s (n)ll IIf (1))l- By
Fact J.5 and since by our parametrization Tr Σ d, it follows that
sup (f (m), u)² < sup (s (1) u)² (20p)² |Σ ||
||
Let t= >>|E|
(()) log(d/8)
2 ||| It follows by Fact J.3 that
Σ / (n))
n2
(()))
< <
| +1) < (E)
with probability at least where also used that = -3|1=11 +(D. log(d/0)
p² p31|2>11 when
76
applying Fact J.3
In the following lemma show that Assumption 3 of Assumption E.2 is satisfied for O(p | with probability 1 - 5 as long as n 2 r(E)* log (d/)).
Lemma G.6. Let k be positive integer and suppose that n > 10 r(E)* log (d/6) and
Tr (E
|
10 Fogg
Then with probability at least 8, 8, uniform distribution over the set {m..... nn has (2k, 2k)- certifiable
(p [E|]
-bounded -moments.
Proof. By Lemma K.4 has (2k, -eetttibee O ( (p [ bounded f-moments. Since Va e
Rd [I (x)] & 20pvd d the result follows from Lemma J.4
28

---

G.1 Unknown
If p is not known and if 0.01 (or arbitrary constant), we can first divide the samples into subsamples of size at least n' = [n/2], and use the first half to learn and the second half for mean estimation.
To do this, let us take the first n' samples and again divide them into two subsamples of size at least n" [nn and subtract the second half from the first half (if n' is odd, let us ignore the last sample). Then we get n" (e-corrupted) iid copies E.. of an elliptically distributed vector with location 0 and the scatter matrix > as the original distribution. Moreover, R for this distribution satisfies P R & 2pvd > a². Let us compute and sort the norms of the samples, and let us take the maximal value b among the smallest a² /2 norms. If & 0.01a, then by Chernoff bound with probability least 1 - exp(- b & 2pv/d and P [ b b) a² a²/4.
Now, we take the second n' samples, divide them into two subsamples size least n" = [n'/2], /2], and add the second half to the first half (if n' is odd, let us ignore the last sample). Since the initial noise distribution symmetric about zero, we get (e-corrupted) iid samples 2/u + .i....;2 .2 + Gr", where Ç; have the same distribution as &. described above. Hence we can use h 20b in our proofs and get the same guarantees as if we used h 20pvd (up constant factor O(1/a)).
H Proof of Identifiability for Near-Optimal Error
In this section, we will prove the statement identifiability underlying Theorem 1.4. We first introduce some notation. We similar notation in [Li19]. Let D be p) distribution with location n² Rdd, Let yi..... Vn be saiples from D and let .,,.... U/ be an & corruption thereof. Further, let Sg (i yi = yt be the set uncorrupted indices and S, = [m] \ Sy be the set of corrupted ones. Let
W = {w E R" |0
< & - <e).
where 1 is the all-ones vector and the inequalities between vectors are entry-wise. Throughout the note we assume that & Note, that otherwise faithfully recovering μ is impossible: For each coordinate, with high probability there is only an θ (a)-fraction of the samples where the noise is small. If = 2 the adversary could corrupt precisely this fraction and crase all information about this coordinate.
Further, for h > O, let FA: Rd - R be defined as x + Fz) = E/= Pn(z)), where by is the Huber loss
1 h (|=)
if ||| h, otherwise.
(1)
h),
and denote by f = V its gradient. Note that in our case f is the derivative of the Huberloss applied entry-wise. The derivative of the Huber loss is Φ: R + R.
if |t < h, otherwise.
h sign((),
For w E IR" with non-negative entries, we define " Rd R as
(1) = Σ 1=1
w. (n 9:))
follows that V (m) Ei= wil f (μ - yi). We let
A arg min C (n))
HERd
and - ET w ff TT
Similar in Appendix G. by looking at differences of pairs of samples, we can assume that we have access to the (e-corrupted) samples from the noise distribution, by replacing a by a² in the definition of the semi-product distribution. This allows us to compute the following relevant
29

---

parameters: Note that EnpD ffn")f(n") is diagonal. We can estimate each diagonal entry of up to factor (1 + O(E + (11g(1/))/m) with probability 1/6 by using I-dimensional robust mean estimation. We will assume that EyDD ['(n") (mn") is known, the error ((e) does not affect our results, since our enror bounds will be larger than this. Similarly, when is known, can also compute p as in Appendix G.1
Identifiability Our aim will be to prove the following theorem
Theorem H.1. Let w E We. 8 E (0, 1), and assume that S a/100, = and 2 dlog(()
(og(1/6). In the above let
Then with probability at least 8 holds that
(V (
l1 - 1'll =0
+ log(1/6)
a3/2 Ve Ve(lyy Ef (n() f(r)) +elg((//)) -
a²n
In our proof, we will use the following properties analagous stability-conditions used before in the literature (cf. for example (DK22))
Lemma H.2. Suppose that the conditions of Theorem H.1 hold. Then with probability at least 1 - the following events hold
1. E wif (nf)(m)ll & & (EVlog(//E)
d+log(1/5)
2. Eies, wis (()") -ES( T < <0(elog()) elogg1//6) +
d+log(1/6)
3. Eies, wif (n - 4t) f f(a - - yi)
Ef Ef(n')((n)
0 E log((//))/a
dlog d+ dolog(1/0/
Ida-
n2
Proof. By
Lemma F.4 f(1)") is O(1)-sub-Gaussian Hence the first two inequalities follow from
Fact
Let us prove the third one. First, let A E [-10s/a, 10 be an arbitrary fixed (non-random) vector. Let A [myl [n].j j [d]. Consider the random matrix
M(i) f (n + A) (n + A) E (nt A) A [ (n) + +A) AJT
Since for 1,j E [d] such that * j. sign (7a5) and sngn(na) are independent given A,
E [M) A] 0. Note that for j E [d]. (i)gs A] is equal to
f ((m))) - f (m7)) [ ( + f (nn), [t [ +1,) - (mm)) A
E
Since f is 1-Lipschitz and is bounded by 2.
E J (int),) (r ((m)), + 4,) - -(nt),) A <]|4,1 < 20e/a.
Hence we get
[MM A] = E ( A] O (e/o:) Ida
To E (m) (m,) A). Since the entries of sign (17" are mutually indepen-
Denote D
dent given A, the entries of f [n) + A) are also mutually independent given A. Since the entries bounded by O(1), by Lemma J.8 for all 8 E (0, 1).
d log (1) A
P Σ 1=1
w (n: + A) (n +A) = O a
+ =og((1//)) +
Ida
> 1 5/10,
n
30

---

where w/ (EEs)- Taking expectations from both sides, we get
+ log (1)
Σ w (n: + + (n + +A)= = D -
& + +logo/11/)) +
Ido > 1-8/10.
Let Ng be an e' nett in 1-10=/a, 1-110//,,0//aaa 10E/a]# of size most bounded by 1,
(Fa)
Since f is 1-Lipschitz and is
|| (ni w./ (n. A) - - + +2' + +1' max
< 2 A
A'llmas max
SInce the spectral norm can only by at most v factor larger than the infinity norm, by taking ev0/(100a) and using union bound, we get that with probability 8/10, for 1-1e/a 10 (including fi")),
w (n + + ( +D) 2 D-O
_
dlog log (1) dloog + log (1)
Ida.
Note that D is a diagonal matrix, and its diagonal entries are
D3 - Σ / (mly)
Since f(n}) are ((L)-sub-Gaussiinn with probability least 8/10. log (d/o) n
D P (D-B(('')()") <o
Hence we get the desired bound.
Proof of Theorem / By Lemma j 1 2 (VL" (n*),,1" f.m)) Hence, it is enough
to bound (V (1 ",K" )." Let f 1r Observe that using the Sauchy-Schwall Inequality,
follows that
(VL" (1²") (u")), u) Σ
We (S //= - -0:)-y),,0 :4)
1=1
Σ
Wi (f (μ² - ,i), Σ
wi (f (40 - vi) - (μ- - ,2))
ieSo
wi (n² - wi)1 |w/|| + ve.
Σ wi (S (n" y)i) (1r- -y²) uu)
NES
Note that by the first point of Lemma H.2 it holds that (+10g(1/8) ). For the second term, we can bound
|
wif (μ- wi'll < <O(E, /lo((//))
Σ wi (f (nr- - vi) - f4r .2)²
wi (f( - -.), u/²
(f - -1), u)) + Σ
wi (f (μ² y)) - v)), uu)
-
iESs
EES
RES,
Term A
Term B
Term C
Term A most O (log(11)) + V /++log(1/8)
|| by combining the second point of To bound Term C, we use that is 1-Lipschitz to observe
Lemma H.2 with Fact J.7
Σ ws (f (n* 4ı) f "1 vs),u,'
31

---

|ull Σ VES
we Iff (x yo) f (A" - -
& |ul]
Σ
we
11 1= & |||||"
remains to bound Term B. To this end, we use the third point Lemma H.2 and obtain
Σ iESs
wi (f (fth - 41) u)² Σ wi (ā - -2:) y))) u)²
Σ wi (f (ftt - vi) u)
iES
< { | (0elo))))))))))0000000()00
d log d + log (1)
||al
n
Putting the above bounds together, we have shown that
(VL"(1"",,)) < ||u|| o E (Vlog(1/E]
- (E)( (og(d))+ (o/(1 + e||u|| + Ve -
Va
(Note that also use ve (1)) + A4log(1/6)
& eogool1))) d+bog(1/8)) Since
"
(VL" (x*), u) > / ||ll and e S rearranging and dividing by ||u|| yields that
||u]| <0 < (Vlog(d) + log(1/8)
+ 2 V ([ -.(r) + log((1/E)
1
a²n
I Filtering Algorithm for Near-Optimal Error
In this section, we will use the proof of identifiability from Appendix H to obtain an algorithm which efficiently recovers p² up to (nearly) optimal error. In particular, we show that
Theorem L.1. Let
be a large enough absolute constant. Let E, a be such that V8 < c. +log(d)+ There Let D be (a, p)ooruuttt distribution with location μe¹ E Rd. Let 2 C a log(1/e)
exists an algorithm running im time n (1(), such that given an e-corrupted sample of D of size and R with probability at least
outputs ja satisfying
1| All ( (
dlog(d) + log(1/0) +
E (V/og/1/E)
a'n
a
The algorithm we propose is based on the by-now-standard filtering approach. We closely follow the exposition in Li19]. To describe the algorithm, let > 0 be some universal constant and for Rdd w E W. let
i (w) = min L (μ))
E, (w) = Σ
wif (f - vz) (p) ( vi)
HERd
==1
Note that since we assume p to be known, can without loss of generality assume that p by scaling. Our algorithm the following.
We remark that in the case of unknown but known a, we can first estimate from the corrupted samples similar Appendix G.I, at the cost of worse dependence
32

---

Algorithm 1.2 (Filtering Algorithm). Input: e-corrupted sample yI,..., Un and p:7 > 0. Output:
Location estimate jt.
Let ( 1 1
Compute f((0) min -= (4) and 20/ 23, (wo10)).
Let / = 0.
while |زا/ Ef (f(n")
(1/)/// do
Compute (+)) the top eigenvector of 2 - -Bf(
For E [n]. compute T. (vl0, (a(t) v1))²
Sort the 7æ. Assume that 71 ... Tn.
Let N be the smallest index such that ΣNEN w/!) > 2e and let Tmax
max Ts.
For & & N, set w (t)
= w
( and for N i set
(++1) wi wi
Compute f((+1) pind fullth) (1) and Σ E((+1) E, (w(t+1)).
-1+
Output p(0).
We will use the following lemma whose proof we will give at the end of this section Lemma I.3. Assume that |
E
|| (x)))
Ce log(1 (oog(1/)///l /e and
Σ
w!!
x.S
Then
Σ
(2+1) W
wi (1+1))
iES,
SESh
With this in hand, we will prove Theorem
Proof of Theorem 1.1 First note, that every iteration can clearly be implented to run in time n o()) (o)) We will show that the algorithm terminates after at most [2en] iterations. Assume towards contradiction that the algorithm does terminate after T [2en] iterations. Note that the number entries of ((() that are equal to increases by least I in every iteration. Hence, after T iterations we have set at least en entries w to zero whose index lies in Sy. By assumption that the
algorithm didn't terminate and Lemma I.3 holds that
w (T)
Sb
w
E
XES
SES,
which is a contradiction.
Next, we prove the correctness of the algorithm. Let T be the index of the last iteration of the algorithm before termination. Note that by our invariant
w
(T)
Σ
Σー
W.
2
w (T)
< 28.
SE
RES
VES.
Since also 0 & (T)
< 1 it follows that (T) E W2 By Theorem H.l and since ||
n'
( C' lolog(//))/a it follows that
7 - n' < 0 dlog(d) + log(1/8)
+ ev /log(1/E)
a
33

---

Lastly, we will prove Lemma 1.3
Proof Lemma 1.3 On high level, we will show that each iteration of the filtering algorithm removes relatively more weight from corrupted samples than from uncorrupted ones. For simplicity, let = w()) and w' = ((++1) Also, let fi = = , = (x(t) and = u(!), Note, that it is enough to show that
Σ Wi w! <
Σ
wi w/.
BES
iES.
Let be the smallest index such that EigN Wi E and denote by {I,.... ,.. Further, recall that w/ (1 (1- _he wi if E T and w w; otherwise. Thus, for i E T, it holds that
wi w/ Tama T,Wh, while for i & T it holds that wt w 0. Hence, the above condition is equivalent to
Σ
Σ
WiT, <
W
RES,N7
iESHTT
will show that the above indeed true in two steps. We will show that
1. Eies,r WHG, & (s (#log(1/e) #
|x By-EE (E-E((m)) ((r))
2. Eies,nT WiT, > a -E
This implies our claim since by assumption ІE - Es (E(" > Ce log((1 (1/g///)//²/ > Cs log(1/e) and S is sufficiently small.
Upper Bounding the Contribution of Sy nT of T3 and since f is I-Lipschitz it follows that
Recall that n >>
dlog(d) (ogg( a0 log(1/e)
(1/4)
Thus, by definition
Σ
WiTs Σ
wr(f(A v²).u)
NE
RES,NT
0
Σ
wi(f(H 0)),0)2 +
Σ
wi wilf(it yi) - f(x -y))) vf), u)²
iES,NT
iES,nT
0
Elog(1/E) +
Σ willā 1e111"
KES,nT
1 [ [=|||11 Σ, (E + (
0
e clog(1/E)+ +
q
22
0 8 log(1/e) +
|r, - (
o3
where in the second inequality we used the last property of Fact J.7 and in the third inequality we used used Theorem H.1
Lower Bounding the Contribution of SnnT Our strategy will be to first show that the contribution of all points in Sg, also those not necessarily in T. must be large and then show that the contribution of points in St T is in fact small. Together they will yield our claim. Note that by defimition of v, it holds that
Σ WTF. = T. ES (8)=B(())(()))) o+E
ES ( 3
E
34

---

y :- Bf (7" ).o)).)))) o).. Note that O(1). By the second point in Lemma H.2 inequality and Theorem H.I
Cauchy-Schree
U4TS Σ iES,
Σ SE$
(f((f (())
Σ SES
w/ (f(m* 0/).0}2-9
+ Σ
wilf(f (it yi) - f(1"" yi),
iES,
+ + Σ
wilf wilf(H" - yi), v) (1f(A -y)) - (f(1" yid 2²))
iESg
0 log((/E) + 11 - -11 + vx 11 - 12ll)
e² #log(1/8)
50
8 log(1 ((e))
|> - E (n (1)") 7||
a
a²
Σ - E Ef f (m (nn) E log((1/)) 11 - 101l
0 a
a
Hence, since Σ, Ef (n") (n") is at least sufficiently large multiple of e clog(1/))/a² and S/ is sufficiently small constant, it follows that the first two terms are at most 0.0001 و Ef ff(n") The second term at most
(V
a E - E (
We claim that this is at most 0.0001 Σ, - E f (n² (n ||
as well. Indeed, it were larger, we would have that [> E f (11") f (17) 7 - contradiiiii Thus, we get that
Σ win > 0.99 Σ, - (f EE
remains upper bound the contribution of indices in Sb \ Note that
Σ
Σ SES
Σ
WiT:
WITI
WiTs
RESunT
iESAT
We claim that the scores for &f T cannot be too large. Indeed, since Eier W/ > 2s and Eieser W; & S it follows that Eies nT 2 e. Thus, since we assume the тą are sorted in decreasing order follows that for i & T it holds that
Σ
WiTe & O (oog( (log(1/))
Ti
Eies,no nn Wi VES,NT
It follows that
E² a3 |= ( (Elog(1/e)
Σ WiT, & O \T
Putting everything together we have shown that
Σ w > | -
RESTOT
as desired.
Finally, it is easy to see that if we can only compute an estimation é of v such that
iT (x, - E ( ( i = -B + +
the proof still works, so we can use the Oce)-elose estimation Σ of E (17) (n*) and compute the top cigenvector of y Σ.
35

---

Concentration Bounds
Throughout this section will the following versions of the Matrix Bernstein Inequality. A proof of slightly more general version can be found in [Tro15, Corollary 6.2.1].
Fact J.1. Let L, B > M Idddd be a symmetric random matrix and MI...., Mn i.i.d. copies of M. Suppose that |M] & L. Further, assume that E M &
B. Then the estimator M
Di=1 M; satisfies for all >
P P 1M-EEMI 2
2d exp
2B
2Lt
Fact J.2. Let .i.... En be iid d-dimensional random vectors such that ||=1|| & L with probability
1. Then
t2n
P E ū- Eull
> & 2d exp
2L2 2Lt
Fact J.3. Let L 0, E Rdd be random vector and vi,...., Un i.idd copies u. Suppose that Then the estimator Σ = 1 = a.x satisfies for all >
||a||| &
t
P
[[
E t)
E 2d exp
22
|2 2Lt
We will use this to prove that sampling preserves bounded f-moments.
Lemma J.4. Let k n. d N21, a, 0, 8 1). Let be distribution with (2k, E)-certifaable
o-bounded f-moments, and mh..... 7m Wi..d. Suppose that > 10 d loog (d/6) and that Vx E 1R Ilf (=)]l pvd..
Then with probability at least 1- 8, uniform distribution over the set {m...... 7n has (2k, E certifiable (o o)-bunnded f-moments. In other words, with probability at least 8,
E (USK)
Σ
(* (s(N)88) wo < <(oo + p) -|ol(
If Mm...... ........pp To follow an elliptical distribution with scatter matrix E. and = O O(Vk|/E))) we only 10 Further, the uniform distribution has 20 2orbbuunedd f-moments.
need Z [(2) yk log( log(d/0)
Proof. Let T3 = E f()) ok (f(n)
TT Note that {n} having (2k, ce-cttiifiable o-bounded f- moments is equivalent the fact that the following SoS proof exists
1 (L) Tho (a ||a]])2k
Denote Th = 1 f(m)
f(n))
(o T. Notice that by Fact K.3
E (DON) T = (1.8) [Th + +T. Tix ok ||u||26 (o2h
Th Txll)
Hence, it is enough to bound ||T - Thll. Our strategy will be to use Fact J.1
To this end, let This implies that
M f(n) 80 (f())()) T and for E [m]. let M; = f(n)) jo (f (8))
T3 = EM and Ta- Ee M. Note that since the entries of f are bounded by h in magnitude it follows that for each
|M. = (1(()))1 < a*a
Further,
2 = =1f
f(n) 8* (f( 1 2ka -(n) (f
Since | [ @h @5()) ||
< 2k it holds that
E 1
< 2* th
(s(n) @h (s(1)SN) 1 < (po))2k d*
Here use the parametrization from Appendix G
where IF 2 d
36

---

By Fact J.1
10p dt log (d/o)
10p2h
log (d/0)
IP P -T]]
+ 0²
<
(1.1)
n
7
Hence with probability at least - 8,
E (v TRO < ||l|| 2k (02h + p2h + - < ||0| (o - 2
p)2k
To see the improved sample complexity for elliptical distributions, note that since r(Σ) Tr( and O(p)))]]))) it follows that
[2]
R.k. 02k
(r(I)
&
p2h 1th (E)
Thus, if n 2
(
(12)
)k log(d/0) then
Th Tall in Eq. (J.1) is at most 22 with probability at least
1- 6.
Fact J.S. DDVII T+().
Let n be elliptically distributed vector with location and scatter matrix E.
Let 8 (1)
n. Then
|nnl
Es (1) (1) (n) || < ||
Fact J.6. BBe09
Let x
N(0, E). Then for all
P ||01| < Tr(E) - || < exp(-t)
and
|| Tr(E) 1E |Σ||| & exp(-I).
Fact J.7.
(DK22) Let Ei,..., &n be independent zero mean 1-sub-Gaussian d-dimensional Let 5 E (0,1), and suppose that n > d + log(1/0). Let W
vectors.
[w E Rd
0 < wi & 1/n, Ein [w; 1/nl < E}. Then, with probability 6, for every w E We.
@VTog(11/)) + d log(1/8) Σ w <0 <0(5viog))
n
and
EEE <o |
E
1 n
Σ
(log(1/))+ (llglg((1))))
d log (1/0)
Similarly, with probability - 8 it holds that for every T [n] with [T) & and every W. it holds that
Σ wiG.E < ( (llo(11/)++ RET
+ d + log(1/)
Lemma J.8. Lete, 8 (0,1) 1) suppose that > d (logg/)) Let :i......... ... be independent zero mean L-sub-Gaussiae d-dimensional vectors, and let a1,..., E Rd be fixed (non-random) vectors such that ||as]| & 100evd/a for some a E (0,1), 1). Suppose in addition that [|E:ll & 10 with probability Let W. = [w E gd 1 w; & 1/n, En [w 1/nl < E). Then, with probability
1 - for every W.
n
+efa+ EEE T -o 0 (log(1/)))+//a1
d dlog (d) + (o/(1
Σ wa (5: + a:) (5: + a;)
n
n
1=1
Proof. Note that
n
n
wi (E: a;) (E: + a.))
Σ
w. E.E
wi (5:a3 + aieT + a.a)))
37

---

Let us bound u =E' i=1 Wi (E:a + +oE + a,a; u for all unit vectors u E R Note that since W. a polytope, is enough to bound this value only for w that its vertices, that the indicators of sets of size at least (1 E) n, normalized by 1 1/n. Let S C [n] be an arbitrary fixed (non-random) set, and let u E 12 be an arbitrary fixed (non-random) unit vector. Then
u Σ (E:03) + a.E. + a;a)) ) u # Σ 2(5,, u) (a,, u) + (as, u)²
IES
:ES
By Hoeffding's inequality, with probability at least - 6,
Σ 2(x u) (a:, u) + (aa,, u)² > -0 (IAsu]] Vlog (1/0)) ||Asul|* -0 (log(1/6))
where As R S|xd is the matrix with at for S. By union bound over all sets of size at least (1 - E) with probability 6, for every set S of size at least (1 5) n.
Σ ESS
26, u) u) (a, u)² -0 (en (1/6) + log(1/))
Let N be (0.01/dl)-ne in the d-dimensional unit ball of size I (300d) Then by union bound over N, we get that with with probability 8, for every set of size at least (1 E) n, and for every N.
2 u) u) + (a., u)² > -0 (en log (L/e) dlog(d) + log(1/8))
:ES
Now, if some unit u is (0.01/d) dcclse to u' E N, we get
1 Σ
26, u) (as, u) 3 Σ
2(i,, (ai, v¹) - (max||<:ll r. ||u u'll)
iE
iES
& log((//)) +s/a+ dlogg (d) + log 1/6)
-0
Using the concentration En= w; E.E from
Fact J.7 we get the desired bound.
K Sum-of-Squares Toolkit
The following fact can be found in [KS17a Lemma A.2]
Fact K.1. For all & E No1 holds that
X.Y
(X (X +Y
< 22 (x + Y2K)
The next fact shows that sum-of-squares captures the Cauchy-Schwer Inequality, a proof can be found in ( Lemma A.I] Fact K.2. For all n E N31 it holds that
X.Y Σxx,
Σ
<
x?
Σ
Y
Fact K.3. Let M E Raxx be a symmetric matrix and be an n-vector formal variables. Then holds that
1X (X, & I
Proof. We can rewrite the inequality as T M| I M) X > 0. Since |M] -I, M is positive semi-definite, follows that there exists a matrix R xxn such that ||M]] In M LLT Heence,
T (IIMI I M) x = |
which is sum of squares in X.
38

---

Lemma K.4. Let k be a positive integer, and let 1 be elliptical d-dimensional vector with location 0 and scatter matrix E that satisfies
T2)
10 oogllogd
Let F: + Rd be a projection onto the Euclidean ball of radius R centered at O.
Then has (2k, ceee-fiiee g-bounded f-moments, where
k e
q = 1-2R
TT
Proof. Let Vi...., Uy variables and consider the polynomial E (f (17) 2) Let s (n)
1 " =
R f (m). Since spherical projection of elliptical distributions depends only on (see Theorem [f
35 in Fra04] ), (v)) has the same distribution as (w), where w ~ N (0, E). Hence
(f (n) 8) 2k
(s (m)) u) 2k
2k
2k
22k
2
R2hh
1
w/ 2> TxE)
||
W
+ R.2k
1 [1|0
||w||
w
2
k:
Tr (E)
(n0, 11) 26 + R2h
1
|||
11/1122
By Fact J.6
||wm| < Tr (E) 2k
Hence
2R²
F 2k
E
(f (7)
2k
E (w, 0) + (R/d) |||||2
Tr (EE)
Since is (2k, 2k)-certy I-subgaussian (see Lemma 5.1 in KST7b)), and since |r > 1 1/d,
(212*11221
22 |
h ||
E (J)
1) 24 <2
2h
Tr(())
39


Reviews:
[{"review_id": "SWxAMqtwGA", "reviewer": "Reviewer_6FtY", "summary": "This work studies robust mean estimation for symmetric distributions. There may possibly no moments (not even the first moment, hence the term location instead of mean), so previous efficient algorithms that rely on strong distributional assumptions may not work on the heavy-tailed setting. \n\nThe main result is that similar statistical guarantees as the Gaussian setting can be obtained for $\\rho$-semi-product distributions, where a semi-product distribution is a set of distributions that covers slightly more than that of product distributions. For instance, semi-product distributions include elliptical distributions, which is not a product distribution. For the case of known covariance matrix (or scatter matrix for elliptical), the guarantee obtained nearly matches best-known guarantees for Gaussians. For the unknown case, they obtain an error guarantee of $O(\\epsilon^{1-\\frac{1}{2k}})$ using $\\tilde{O}(d^k)$ samples.\n\nThe key approach is to generalize the filtering idea for robust mean estimation with a Huber loss instead of a quadratic loss in order to be able to handle distributions without second moments. Once the Huber loss is properly incorporated into the filtering technique, the necessary certificate for filtering can be obtained algorithmically without using sum-of-squares proofs for symmetric distributions.", "questions": "- For the main theorems, there is an upper bound on $\\epsilon$. What is the breakdown point here? If C < 1/2, what is the reason the proposed approach breaks down?\n- In Theorem 1.6, the intuitive definition of $k$ is unclear. Some exposition on $k$ would be helpful.", "limitations": "No limtation addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- This work studies a setting which (partially*) generalizes previous works to handle heavy-tailed distributions in which first or second moments may not exist. Here, they incorporate Huber loss into the common filtering technique that has been used in much of the recent robust learning literature. This in itself is novel. Furthermore, by exploiting symmetry, the filtering technique is made more algorithmically feasible without relying SoS approaches.\n- Through studying heavy-tailed symmetric distributions, such as elliptical distributions, in the case of unknown covariance, the paper obtains error bounds of $o(\\sqrt{\\epsilon})$ that were not known for general subgaussian distributions. \n- The main result obtains strong guarantees that nearly match that of Gaussians.\n\n*refer to Weakness 1", "weaknesses": "1. Only a minor weakness: though the abstact motivates the work by stating that previous efficient estimation algorithms assume strong distributional conditions, the symmetry distributional assumption seems also possibly strong. While it is able to incorporate heavy-tail distributions, it also limits itself in generality (as ever-slightly altered Gaussians are not symmetric but have strong concentrations to exploit).\n2. While I enjoyed the content of the paper, he main body seems abruptly cut off without a conclusion or final algorithmic overview. The presesntation would be greatly improved with a final algorithmic description along with a retrospective conclusion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe thank you for your feedback. We are happy that you enjoyed reading the content of our paper. We agree that including a succinct description of our algorithm, e.g., as an algorithms box, as well as a conclusion to the end of the paper would improve the presentation. We will add this.\n\n### Breakdown Point\n\nThe breakdown point of our algorithm depends on how much probability mass is located near the location parameter. To illustrated this, let us consider semi-product distributions (Definition 1.2). We claim that the fraction of corruptions cannot exceed $1/100$. Specifically, consider the mixture distribution $(1-\\tfrac 1 {100}) N(\\mu,\\sigma^2) + \\tfrac 1 {100} N(\\mu,1)$, for $\\sigma^2$ very large (like $2^n$ or larger). Note that this distribution satisfies the assumptions of Definition 1.2 with $\\rho = \\Theta(1)$. Then by replacing all samples from $N(\\mu,1)$ with new independent samples from $N(\\mu,\\sigma^2)$, the input distribution becomes $N(\\mu,\\sigma^2)$. In this case, even the information-theoretic error scales with $\\sigma$ and hence, can be unbounded.\n\n\n\n\nWe remark that in the appendix, we consider a more fine-grained version of of Definition 1.2 (Definition A.1). In particular, it states that a distribution is $(\\alpha, \\rho)$-semi-product if, Definition 1.2 holds, but with the second item replaced by $\\mathbb{P}(\\lvert \\boldsymbol \\eta_j\\rvert \\leq \\rho) \\geq \\alpha$. In this case, the above discussion shows that the fraction of corruptions cannot exceed $\\alpha$. For example, in this setting, the analysis of our polynomial time algorithm (Theorem A.1, generalizing Theorem 1.4) requires $\\varepsilon \\leq \\alpha^3 / C$ for some large enough constant $C$. We did not attempt to optimize this dependence on $\\alpha$.\n\n### On the Role of $k$ in Theorem 1.6\n\n$k$ can be seen as a parameter which allows a tradeoff between (a) number and samples \nand running time and (b) accuracy guarantees. It is analogous to the number of moments used in the bounded-moment setting, and these guarantees are similar to the guarantees of the SoS-based filtering algorithm for distributions with certifiably bounded $2k$-th moment. We will clarify it in the final version of the paper."}, {"review_id": "za7xwRpWhO", "reviewer": "Reviewer_371F", "summary": "This paper studies the robust mean estimation problem without any moment assumptions. Instead, they consider a class of symmetric distributions, that is, semi-product and elliptical distributions. They develop a method based on Huber loss and the classic filtering technique that can achieve the same error rate as if the underlining distributions are sub-Gaussian. Their sample complexities are nearly optimal (with additional log factors).", "questions": "Please see the weakness part.", "limitations": "Please see the weakness part.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The idea to use Huber loss and develop a similar result for the classic filtering method is very smart. I think this idea can be generalized to other settings and can be of independent interest.\n\n- The paper is well-structured. The techniques part clearly provides the motivation and is very readable.", "weaknesses": "- The title is a little bit overclaimed. This paper studies the robust mean estimation problem without moments, but with the constraint that the distribution should be symmetric. I think it would be better to reflect this constraint in the title. \n\n- The notation style is not consistent. Based on my understanding, the authors use bold font for random variables. However, in some cases, like line 95, some symbols are not in bold font. \n\n- A quick question: I can understand that Huber loss has many fantastic properties. Compared with l2-loss, it is more robust against outliers; compared with l1-loss, it is differentiable everywhere. However, l1-loss is only not differentiable at 0. Hence, my question is can we replace the Huber loss with l1-loss? If not, can you briefly mention what is the difficulty?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your feedback. Regarding the title of our submission: Reflecting that we exploit symmetry already in the title is a good idea. For example, a candidate for the title could be \"Robust Mean Estimation Without Moments for Symmetric Distributions\".\n\n### Notation\n\nWe will also make sure to check that our notation is consistent, thank you for point this out. We would like to remark that we use regular (non-bold) font for random variables, some of which have been adversarially corrupted. E.g., in line 95, in Definition 1.1. $Z_1, \\ldots, Z_n$, refer to an adversarial corruption of some iid (purely random) sample $\\boldsymbol X_1, \\ldots, \\boldsymbol X_n$. We find this distinction between adversarially corrupted and purely random (uncorrupted) samples particularly useful in our proofs of identifiability. We do acknowledge that  we did not specify this  and will add clarification to the paper. \n\n### $\\ell_1$- instead of Huber loss\n\nAn approach based on the $\\ell_1$-loss should also work, but it requires slightly different assumptions than ours. Concretely, in the semi-product case, one needs to assume that the density is $\\Omega(1/\\rho)$ at the location. For product distributions we can achieve this by adding Gaussian noise of standard deviation $\\Theta(\\rho)$ to each entry. For elliptical distributions similar density assumption is also required, however, the approach with adding Gaussian noise to each entry does not work: The resulting distribution might not be elliptical anymore.\n\nTo illustrate why the condition on the density is necessary, consider the one-dimensional mean estimation problem for the distribution that is uniform over the (discrete) set $\\{\\mu-1, \\mu + 1\\}$. Every $x\\in [\\mu -1,\\mu + 1]$ minimizes the $\\ell_1$-loss, to find the correct value we need an \"averaging\". The Huber loss does this automatically. If we have $\\Omega(1)$ density at $\\mu$, then the $\\ell_1$ loss minimizer is close to $\\mu$."}, {"review_id": "CqbxW8QV7z", "reviewer": "Reviewer_QF3Z", "summary": "This paper considers sample complexity of (robust) mean estimation possibly without moments. Two typical examples are product distributions and elliptical distributions. The main technical contribution of this paper is to adapt the filtering techniques to the setting with less restrict moment assumptions. ", "questions": "I have several questions and comments.\n\n(1) In most \"useful\" applications, some moment assumptions may be needed. For instance, as the authors mentioned, covariance structure may be helpful. Also I may suggest to use \"location\" parameter instead of \"mean\". One case is the product Cauchy but it does not have a mean.\n\n(2) p.1, line 16: It may be better to say SQ refers to statistical query (if I don't miss it).\n\n(3) p.3, Def 1.2: If I understand correctly, the variables $(|\\eta_j|)_{j = 1}^d$ can be dependent. If so, this is worth commenting since it is (apparently may be slightly) stronger than the usual sense of product measure. \n\n(4) Theorems 1.4-1.6: In all theorems, it is stated that the time complexity is \"polynomial\", i.e. $n^{\\mathcal{O}(1)}$. However, it is not clear whether it is $n$ or $n^{100}$ (this makes difference in high dimensions). I understand that exact or a bound may be difficult. But  I hope the authors may clarify this. ", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The results of the paper are interesting and new; while the idea may not be. The basic argument relies on filtering, which was previously proposed by [DKK+17] and [DKK+19]. The authors of the paper make a good observation on how the idea of filtering (and coupling) can be used with less restrictive moment assumptions (but it finally replaced by some concentration). The paper is well written, and I enjoyed every minute reading it. ", "weaknesses": "As mentioned, the main concern is that the authors replace the moment conditions with \"concentration\", i.e. $P(|\\eta| \\le \\rho) > \\frac{1}{100}$ and $P(R \\le \\sqrt{2d}) \\ge \\frac{1}{100}$. Moreover, from technique viewpoint, the main components, filtering and coupling (identifiability), are not novel. The time complexity is not explicit (though polynomial). Also I think the paper is lack of (synthetic or real) experiments.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe thank you for your feedback and are happy that you enjoyed reading our paper.\n\n### Probability Mass Around the Location Parameter vs. Concentration\n\nWhile the condition that some mass is present around the location parameter, e.g., that $\\mathbb{P}(\\lvert \\eta \\rvert \\leq \\rho) \\geq 1/100$, may suggest that some  concentration phenomena are occurring, we would like to remark that in our setting that need not be the case. In particular, the kind of concentration results needed to apply known filtering results from the bounded moment setting, *cannot* be deduced from our assumptions. As a consequence, we need new algorithmic ideas (see also the next section).\n\nAs an example: In the bounded-moment setting, it is necessary the the empirical moments of the uncorrupted samples concentrate around their empirical counterpart. In our setting, such concentration may not even occur for the location (let alone for larger powers): Consider the standard Cauchy distribution. This satisfies our definition with $\\rho = O(1)$, but averaging $n$ such independent variables, again results in a standard Cauchy distribution. Hence, it is unclear how to use the filtering approach for the bounded moment setting to obtain any non-trivial guarantees. We show that by carefully integrating the Huber loss into this approach, non-trivial and in some cases nearly optimal guarantees can be obtained.\n\n\n\n### Novel Filtering and Identifiability Using the Huber loss\n\nAs you correctly pointed out, the filtering paradigm is not new and has previously been used, e.g., for robust mean estimation under bounded moment assumptions. The same holds for the proof of identifiability based on moment assumptions (further, based on the square loss). Our work builds on these ideas and shows how to extend them to the setting where no moments exist, but a symmetry condition holds. In particular, we would like to emphasize, that to the best of our knowledge, the combination of these ideas with loss functions different from quadratic loss is novel to our submission. As explained in the previous section, these new ideas are necessary to achieve non-trivial guarantees under our assumptions. Using this combination, we can (among others) achieve the following:\n- Nearly achieve the same guarantees as for the standard Gaussian distribution for two natural symmetric generalizations of the standard Gaussian: Product and spherically symmetric distributions.\n- For elliptical distributions, achieve the guarantees as for certifiably sub-Gaussian distributions  (under a mild assumption on the effective rank).\n- Do this in the absence of any assumptions related to sum-of-squares on the underlying distribution.\n\nIn particular, previously the filtering paradigm, as well as other algorithms, failed to achieve error better than $o(\\sqrt{\\varepsilon})$ without assuming the distribution has *certifiably* bounded moments in sum-of-squares (the only exceptions are the Gaussian distribution and distributions with known covariance matrix).\n\n### Correlation and Location\n\nRegarding your first question: In the paper we mentioned that the class of elliptical distributions allows for more complex \"correlation structures\", which are useful in modelling, e.g., financial data. We used this term informally, to mean that the coordinates of the vectors might have complex dependencies, indicated by the scatter matrix. Note, that the covariance does not need to exist for this, nor do any other moments. We will rephrase, do make this more clear.\nSimilarly, we tried our best to distinguish between mean and location (cf. Theorem 1.4 and 1.5) but will thoroughly proof-read our submission again.\n\n\n### Other Comments\n\nWe would also like to address your other comments/questions:\n\nYes, Definition 1.2. allows for distributions with dependent coordinates, one example (mentioned in the paper) being spherically symmetric distribution. We will be happy to highlight this more.\n\nRegarding the running time and practicality: As noted in lines 146-148, we do expect our algorithm to be practical. Since it only uses one-dimensional smooth convex minimization for $O(nd)$ times and top-eigenvector computations $O(n)$ times. \n\nWe remark that for the filtering algorithm under bounded moment assumptions, there are versions achieving nearly linear running time for which the code is also available [DHL19]. These works use additional ideas beyond the standard filtering idea. We could imagine that similar techniques might work in our setting.\n\n\n### References\n\n[DHL19]: Yihe Dong, Samuel Hopkins, Jerry Li, \"Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection\""}, {"review_id": "rK1P0YV2bm", "reviewer": "Reviewer_DMaa", "summary": "This paper studies outlier-robust location estimation for symmetric(-like) distributions. For \"semi-product\" distributions, the authors show that one can achieve $O(\\epsilon \\sqrt{\\log 1/\\epsilon})$ asymptotic error with a polynomial number of samples (and time), and $O(\\epsilon)$ asymptotic error when given quasipolynomially many samples (and time poly in the sample set size). For elliptical distributions, the authors show that as long as the scatter matrix has $\\Omega(\\log d)$ effective rank (hiding $\\epsilon$-dependence here), then in quasipolynomial time we can yield asymptotic error $O(\\epsilon \\sqrt{\\log 1/\\epsilon})$. Crucially, for the last result, the scatter matrix is not known to the algorithm.", "questions": "More important:\n\n- Knowledge assumption on algorithm in Theorems 1.4 -- 1.6: one of the selling points from the introduction is that the algorithm doesn't need to know the covariance or scatter matrix. However, it was unclear to me whether this means the algorithm knows absolutely nothing about the scatter, or if it only knows very little (such as an upper bound). The theorems can be a lot more explicit in saying exactly what the algorithm needs to know (or explicitly say that it needs to know absolutely nothing about the scatter matrix). For example, does the algorithm in Theorem 1.4 need to know the parameter $\\rho$, which is essentially an upper bound to the covariance, at least in the Gaussian case? This distinction seems pretty important to me.\n\n- Result statement of Theorems 1.4 -- 1.5: the statements are of the form \"if $n$ is sufficiently large, then we get this almost-sub-Gaussian error rate plus the claimed asymptotic error\". However, it seems that the required $n$ lower bound is large enough that the almost-sub-Gaussian error is already dominated by the asymptotic error. Yet the prose following the theorems seem to sell how the theorem gets close to the sub-Gaussian rate (for Theorem 1.4, and for constant $\\delta$ and large $C$ for Theorem 1.5). Am I misunderstanding something?\n\n- Theorem 1.6: Line 170 claims that Theorem 1.6 is only slightly sub-optimal in the no-corruption part of the error. But that error is multiplicative in terms of the effective rank and $\\log d/\\delta$, which is much worse than the sub-Gaussian rate of *additive* error. This error is equal to the naive analysis of entry-wise median-of-means. In fact, entry-wise median-of-means does not actually need the $d$ in $\\log d/\\delta$ from the naive union bound, and can get error $\\sqrt{\\mathrm{Tr}(\\Sigma)\\log\\frac{1}{\\delta}/n}$, so the error in Theorem 1.6 is even worse than entry-wise median-of-means. Am I missing the point here?\n\n- It is unclear to me that even the sub-Gaussian rate is the correct error rate for the non-robust part of these theorems. For 1-d symmetric distributions, and without corruptions, it was shown by Stone (1975, Maximum Likelihood Estimators of a Location Parameter) that asymptotically one can achieve Fisher information rates, which can be much better than the variance-based sub-Gaussian rate.\n\n- The appendix was hard to follow. There are three appendices with filtering algorithms, but Appendix I was titled only \"Filtering Algorithm\". It also seemed a bit weird that Appendices H and I appeared last, even though they prove Theorem 1.4, which was introduced earlier than Theorems 1.5 and 1.6. In terms of the actual content, there doesn't seem to be much discussion on how the techniques in the appendices relate to each other. I could see that Appendix E generalizes Appendix D, but how does Appendix I (and relatedly, Appendix H) relate to Appendix E (and C)?\n\nLess important:\n\n- Notation is slightly confusing, with the bold and capital letters. There is no distinction between random scalars and random vectors (e.g. in defining elliptical distributions).\n\n- Page 3, it was claimed that the first 2 properties of semi-product distributions allow for accurate non-robust (i.i.d.) location estimation by using entry-wise median. This seems true only when $\\rho$ is small?\n\n- Footnote 1, does $\\alpha$ need to be known by the algorithm?\n\n- Footnote 2, there is an $O(\\log 1/e)$ which I assume is a typo? Is \"$e$\" supposed to be \"$\\epsilon$\"?\n\n- CTBJ22 reference: they show how to do mean estimation robustly when only $1+\\alpha$ moments exist, but (1) they do not handle the full adversarial corruption model because of sample-splitting issues and (2) they require an upper bound to the $1+\\alpha$ moment in every direction.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Prior works in (algorithmic) robust statistics get \"stuck\" at the $\\sqrt{\\epsilon}$ asymptotic error, when the covariance of the distribution is not known, even when the underlying distribution is guaranteed to have higher moments or might even be sub-Gaussian. This paper identifies semi-product distributions and elliptical distributions as special classes for which further progress can be made. The author(s) adapts the filtering framework, and proposes using variants of the Huber loss as score as opposed to the basic quadratic score in the filtering step. This allows the author(s) to beat the $\\sqrt{\\epsilon}$ error even when covariance/scatter matrices are unknown to the algorithm.", "weaknesses": "I find some parts of the writing clarity can be improved. In particular, I'm still a bit confused about how the guarantees of this work compare with prior works, re: knowledge assumptions on the algorithms. Some of the technical claims are also a bit over-sold (unless I misread or am misunderstanding). See the \"Questions\" section for more details.\n\nAnother weakness, for me, is the motivation: the practical relevance of semi-product and elliptical distributions seems to be rooted in mathematical finance. However, at least from the cited works, the relevance of these distributions appears to more or less be \"because we can write down theorems\". I hope the authors will consider adding a more self-contained discussion on why we should care about these distributions; I think it will make the paper more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for you feedback. We hope to address your concerns in this note. We believe your questions and this discussion form a valuable addition to our paper and we will add this.\n\n### Knowledge of Problem Parameters\n\nIn the setting of the introduction, e.g., Theorems 1.4-1.6, our algorithms do only require the corrupted samples as input. In particular, the parameter $\\rho$ for semi-product distributions does not need to be known to the algorithm. All relevant parameters can be estimated from the corrupted samples. The case of unknown $\\rho$ is described in Appendix G.1. Note that Appendix G.1 is written for elliptical distributions (it corresponds to the case of unknown trace of the scatter matrix in terms we used in the introduction), but the same argument applies to semi-product distributions (we can find a good upper bound on $\\rho$ by working separately with each entry, since distributions of the entries are one-dimensional symmetric, hence elliptical). In the setting of a Gaussian distribution with covariance matrix $\\rho^2 \\cdot I_d$, this implies that we do not need to know an upper bound on the covariance matrix.\n\nFor the more general setting of Definition A.1 (with $\\alpha$), either $\\alpha$ or $\\rho$ needs to be known, but not both. E.g., if we assume $\\alpha$ is known, we can estimate $\\rho$ from the input.\n\nWe agree that our writing with respect to this in some places is unfortunate and we will fix this and add a discussion to the main theorems.\n\n### Sub-Gaussian Error Rates and Sample-Complexity (Semi-Product Distributions)\n\nYou are correct, that since we have a lower bound on the number of samples, the non-robust error term in Theorems 1.4 and 1.5 is always dominated by the robust error. We wrote the error in this way to make the dependence on all problem parameters explicit. We acknowledge that this might be confusing and consider omitting it. \n\nWe agree that the discussions in lines 139-140 and 155-156 are indeed confusing. We remark that for Theorem 1.4 we achieve nearly optimal (up to a log factor) sample complexity (necessary to achieve error $\\varepsilon\\sqrt{\\log(1/\\varepsilon)}$, and Theorem 1.5 matches what is known for the Gaussian case -- achieving error $O(\\varepsilon)$ with quasi-polynomially many samples and in time polynomial in the number of samples.\n\n### Non-Robust Error of Theorem 1.6 (Elliptical Distributions with Unknown Scatter Matrix)\n\nWe agree that in the non-robust setting, when there are no corruptions, there exist simple algorithms achieving better error than the \"non-robust error\" of Theorem 1.6. The main challenge is to design algorithms which (nearly) match the error of the non-robust setting that are *also* robust against adversarial corruptions (note that the entry-wise median of means estimator suffers from error $\\Omega(\\varepsilon \\sqrt{d})$). This turns out to be a significant challenge.\n\nAs mentioned in the paper, specialised to Gaussian distributions with unknown covariance matrix, the optimal (robust) rate is $O(\\sqrt{\\lVert \\Sigma \\rVert} \\cdot (\\sqrt{\\tfrac {r(\\Sigma) + \\log(1/\\delta)} n} + \\varepsilon))$. An (inefficient) estimator achieving this was only recently found [MZ23]. To the best of our knowledge, there is no efficient estimator matching this rate (even ignoring log-factors in the \"robust error\"). We would like to clarify, that it is not known how to achieve this rate for general elliptical distributions with unknown scatter matrix, even inefficiently. Note that in [CGR18] the error scales with $d$ instead of the effective rank.\n\n\n## Sub-Gaussian Error Rate vs Fisher Information Rate\n\nFor simplicity, consider the 1-D setting. Let $I_D$ denote the Fisher information of a distribution $D$. It is correct that asymptotically, the \"right\" error rate for a given symmetric distribution $D$ scales with its Fisher information rate $I_D$. In particular, this asymptotic result could let us hope for an \"instance-optimal\" algorithm, i.e., when run on distribution $D$, its error scales with $I_D$ -- instead of $\\inf_{D \\in C} I_D$ for some class of distributions $C$. Note that for the classes of distributions we consider the infimum above corresponds to the sub-gaussian rate.\n\nUnfortunately, it seems unlikely that such instance-optimal results can be achieved in the finite sample regime, even non-robustly. Consider the following mixture distribution: $(1-\\gamma)N(0,1) + \\gamma \\delta_0$, where $\\delta_0$ is a Dirac Delta at 0. Then $I_D = \\infty$, but when the number of samples $n \\ll 1/\\gamma$, we only see samples from $N(0,1)$ and thus, the best rate we can hope for is $1/\\sqrt{n}$ -- instead of 0.\n\nThe example above is taken from the very recent work [GLP23]. They provided an algorithm (in one dimension) using finitely many samples, whose error scales with a quantity related to the Fisher Information but subject to the same constraint outlined above. It would be interesting to obtain similar results in the robust setting. We remark that their techniques rely on likelihood maximization and it is not clear how to make them robust.\n\n## Ordering of Appendices and Other Comments\n\nAppendices H and I prove Theorem 1.4, while Appendices D-G prove Theorems 1.5 & 1.6. We chose this ordering since the proofs in H & I are technically more complex and easier to understand if one has read D-G, although this is not necessary.\n\nWe will also address the minor comments raised by you and add additional motivation for our distributional assumptions.\n\n## References\n\n[CGR18]: Chen, Gao, Ren, \"Robust covariance and scatter matrix estimation under huber’s contamination model\"\n\n[MZ23]: Minasyan, Zhivotovskiy, \"Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians\"\n\n[GLP23]: Gupta, Lee, Price, \"Finite-Sample Symmetric Mean Estimation with Fisher Information Rate\""}]

Author rebuttal:

Meta-review: This paper advances the state-of-the-art for the fundamental problem of robust mean/location estimation in high dimensions. The authors provide efficient algorithms with dimension-independent error guarantees (in some cases close to best possible) for a range of distribution families without moment assumptions but with additional structural properties (namely, some kind of symmetry). While the algorithmic component heavily draws from prior work in algorithmic robust statistics, this is a solid contribution that is appropriate for publication at NeurIPS.
Decision: Accept (poster)