Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions
Authors: Ilias Diakonikolas
Daniel Kane
Jasper C.H. Lee
Ankit Pensia
Venue: NeurIPS 2022 Accept (2022)
Keywords: sparse estimation
robust statistics
heavy-tailed estimation

Abstract: We study the fundamental task of outlier-robust mean estimation  for heavy-tailed distributions in the presence of sparsity. Specifically, given a small number of corrupted samples from a high-dimensional heavy-tailed distribution whose mean $\mu$ is guaranteed to be sparse, the goal is to efficiently compute a hypothesis that accurately approximates $\mu$ with high probability. Prior work had obtained efficient algorithms for robust sparse mean estimation of light-tailed distributions. In this work, we give the first sample-efficient and polynomial-time robust sparse mean estimator for heavy-tailed distributions under mild moment assumptions. Our algorithm achieves the optimal asymptotic error using a number of samples scaling logarithmically with the ambient dimension. Importantly, the sample complexity of our method is optimal as a function of the failure probability $\tau$, having an {\em additive} $\log(1/\tau)$ dependence. Our algorithm leverages the stability-based approach from the algorithmic robust statistics literature, with crucial (and necessary) adaptations required in our setting. Our analysis may be of independent interest, involving the delicate design of a (non-spectral) decomposition for positive semi-definite matrices satisfying certain sparsity properties.

Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions
Ilias Diakonikolas University of Aisconsin-Madisne ilias@cs. wisc. edu
Daniel M. Kane University of California, San Diego dakane@cs, uesd.
Jasper C.H. Lee University of Wisconsin-Madises jasper lee@wisc. edu
Ankit Pensia University of Wisconsin-Madison ankitpBcs. wisc edu
Abstract
We study the fundamental task of outlier-robust mean estimation for heavy-tailed distributions in the presence of sparsity. Specifically, given a small number of corrupted samples from a high-dimensional heavy-tailed distribution whose mean μ is guaranteed to be sparse, the goal is to efficiently compute a hypothesis that accurately approximates μ with high probability. Prior work had obtained efficient algorithms for robust sparse mean estimation of light-tailed distributions. In this work, give the first sample-effciient and polynomial-tinn time robust sparse mean estimator for heavy-tailes distributions under mild moment assumptions. Our algorithm achieves the optimal asymptotic logarithmically with the ambient dimension. Importantly, the sample complexity method optimal function of the failure probability т, having additive log(1/r) dependence. Our algorithm leverages the stability- approach from the algorithmic robust statistics literature, with crucial (and necessary) adaptations required in our setting. Our analysis may be of independent interest, involving the delicate design of (non-spectral) decomposition for positive semi-definite matrices satisfying certain sparsity properties.
using number of samples scaling
Introduction
One of the most fundamental problem setups in statistics is as follows: given n i.i.d. samples drawn from unknown distribution P chosen arbitrarily from some known distribution family P, infer some particular property of from the data. This generic model captures a range of statistical problems of interest, for example, parameter estimation (such the mean and (co)anriance of P), as well as hypothesis testing. While long lines of work have given us a deep understanding on the statistical and computational possibilities and limits these problems, these results not always applicable in real-world settings due to (i) modelling issues, that the underlying distribution P might actually be the known family but only being close it, and (ii) the fact that the n samples supplied might be corrupted, for example by nefarious actors in high-stakes applications [ABH 72].
The field of robust statistics aims to design estimators and testers that can tolerate up to constant fraction corrupted samples, independent of the potentially high dimensionality of the data [Tuk600, HR09]. Classical works in the field have identified and resolved the statistical limits of problems in this setup, both in terms of constructing estimators and proving impossibility results [Yat85, DL88, DG92, HR09). However, the proposed estimators exponential time to compute either in the number of samples or the number of dimensions (HR09].
computationally efficient, often requiring
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A recent line of work, originating in the computer science community, has developed the subfield of algorithmic robust statistics, aiming to design estimators that not only attain tight statistical guarantees. but are also computable in polynomial time. This line of research has provided computationally and statistically efficient estimators in a variety of problem settings (e.g., mean estimation, covariance estimation, and linear regression) under different assumptions (e.g., the distribution might be assumed to be (sub-)Gaussian, or can be heavy tailed); see [DKI9] for a recent survey of results.
The focus of this paper is the robust mean estimation problem under sparsity constraints on the mean vector. Sparsity is an important structural constraint that is both relevant in practice, especially in the face of increasing dimensionality of modern data, and extensively studied for statistical estimation (see, e.g., the books [HTW15, EKI2, van] In the specific context of robust sparse mean estimation, prior works have studied the case where the underlying distribution has light- tails, e.g., sub-exponential tails (BDLS17, DKK+19b, CDG DKK + 22]. In particular, the case of a spherical Gaussian distribution is now rather well-understood both in terms of the optimal iiformation-thhoreee estimation error, as well as the conjectured computational sattttttiinnattttttiaalllll tradeoff' namely, that there is a gap between the statistical performance of computationally efficient and inefficient estimators [DKS17, BB20]. In this work, we initiate the investigation of robust sparse mean estimation for heavy-tailed distributions, under only mild moment assumptions. Our main result is the first computationally efficient robust mean estimator in the heavy-tailed setting which leverages sparsity to reduce sample complexity from depending polynomially to logarithmic dependence. Importantly, our algorithm also achieves the optimal dependence on the failure probability it tends to O; see the next two subsections for further discussion.
the dimensionality
1.1 Problem Setup
We first define the input contamination model before formally stating the statistical problem.
1/2) and distribution P on uncorrupted samples, an algorithm takes samples from P with e-contamination as follows: (i) The algorithm specifies the number n of samples it requires. (ii) n i.i.d. samples from P are drawn but not yet shown to the algorithm. (iii) An arbitrarily powerful adversary then inspects the entirety of the n i.i.d. samples, before deciding to replace any subset of [en] samples with arbitrarily corrupted points, and returning the modified set of n samples to the algorithm.
Definition 1.1 (Strong Contamination Model). Given a corruption parameter
Define the f2rm of a vector u, denoted by || as the f--norm of the largest & entries of a vector e in magnitude. The goal is to estimate the mean vector in this sparse norm.
0, failure probability T E (0, 1), and distribution family 'D over Rd. Suppose we have access to c-ontamiinated samples drawn from an unknown distribution P E 'D with mean μr. The problem is to compute estimate js such that [ - pll2, is upper bounded by error with probability at least - T over n samples. The goal is then give an estimator with the minimal sample complexity n (,k,,,,,77 Ō,
Problem 1. Fix a corruption parameter E 102), error parameter
The above problem is slightly more general than sparse mean estimation in the following sense. To estimate a k-sparse mean vector μ to error 6, suffices (see [CDG*. Lemma 3.2]) to: 1) get an estimate i with [ - Hll2, S 5/3, and 2) round ğ to the k entries with the largest magnitude, and zero out all the other entries. The result of our paper solves robust mean estimation in the f2,4 norm.
A key aspect of robust statistics is that, depending on the distribution family D we consider, the above problem is generally not solvable for all error parameters d >> 0. This work focuses on sparse mean estimation for heavy-tailed distributions, where a commonly used model for heavy-tailedness imposing only the mild assumption that the covariance is bounded by I, without any further tail assumptions (see Section 1.4 for more discussion). Even when d = 1 and even when there are infinitely many samples [DK19], it is known that in the heavy-tailed setting, the minimum ò achievable is in the order of Ve. This immediately implies the same lower bound of ((v)) for the minimum achievable 8 in Problem 1.
Before discussing the algorithmic results in this paper, we first state known information-thoon bounds the sample complexity that applies to all estimators, efficient not, for Problem on distributions with covariance bounded by 7, and for = @(Vr).
Fact 1.2 (Information -tehorrrttoothooreticcc theoretic sample complexity: computationally-inffficenn) In Problem 1, for the distribution family D2 which is the set of distributions with covariance Σ 3 1, for ô = ((Ve).
2

---

we have that nik, e, ē, x (klog(d/k) + log(1/T))/e. That is, all algoritims need these many samples and there exists
commpuaationallyiinfficcii estimator with this sample complexity. The upper bound is from [Dep20a, PBR20J, and the lower bound follows from [IMI9b]] even in the absence of outliers (see also Footnote in [DI.22a]) and even when we restrict to the distribution family DD Gaussion which is the set of the Gaussian distributions with identity covariance.
An interesting aspect of robust sparse mean estimation is that there is a conjectured statistical- computational tradeoff, namely that efficient algorithms require qualitatively larger sample complex- ity than inefficient algorithms. There is evidence (in the form of SQ lower bounds and reduction- hardness) that all efficient algorithms have a quadratically-won constant e, 6, T, and Caussian being identity-covariance Gaussians in Problem I, the sample complex- ity of all efficient algorithms is at least (2)?.. as opposed to (kk) in Fact 1.2. See [DKS17, BB20] for detailed discussion.
dependence on k, that even for
Both the informationnthhoreticc bound and the conjectured computational lower bound serve as benchmarks for our algorithm to match.
1.2 Our Result
We now state the results of this paper, before discussing in the next section our algorithmic approach and also the assumptions required in the results.
Our main result is a computationally efficiently robust mean estimator in the ε norm, with tradeoff, under the standard heavy- tailed assumption that the covariance Σ 3 I and the additional mild assumption that the 4th moment is bounded in all axis directions. In the following (and the rest of the paper), a >> 6 for a, b E R to mean there exists a sufficiently large constant c with a 2 cb.
performance matching the conjectured computationall-tatisst
use the notation
Theorem 1.3 (Our result: computationally efficient). Lei E (0,eo) for small constant Eo > O. Let P be a multivariate distribution over RR where the mean and covariance of P are μ and Σ respectively. Suppose Σ 3 I and further suppose that for all j E [d]. B[(X, 1--5-, 13,,,,, algorithm such that, on input (i) the corruption parameter c, (ūi) the failure probability T, (iii) the sparsity parameter k, and (iv) T, an c-corrupted set of n >> (k2 log d + (g((//))ffc i.idd samples from P. outputs j satisfying || - p1l2,k = O(vc) with probability 1 - poly(n, d) time.
= =1,)) = Then, there is an
Phrased in a slightly different language, when our estimator is given sufficiently large number of corrupted samples, it outputs an estimate ft satisfying ~ = ((v A- log + +C++ / /og(L/T) with probability 1 - т. We note also the guarantees of our algorithm remain the same under a weaker assumption on Σ: we need only || S 1 (lI ||x, defined in Definition 1.4) instead of spectral norm. Informally, the X' norm of square matrix A is convex relaxation of finding the maximum of e Av over k-sparse vectors v. See Theorem D.12 for the stronger version of the main result, which assumes only that | X I 1.
"
"
As outlined above, the dependence of our sample complexity result on k is tight with respect to the conjectured lower bound for efficient algorithms, and its dependence on T and are also tight with respect to the iooommtioonthhoreee lower bounds, even in the Gaussian case. In terms of the smallest achievable asymptotic error (even given infinitely many samples), we show in Lemma E. that, even after adding the mild axis-wise 4th moment assumption in Theorem 1.3, the asymptotic error remains lower bounded by ((Ve) when & is sufficiently large. The restriction k is very mild, and covers most parameter regimes of interest.
We also note that the sample complexity has a dependence on the failure probability that is log 1 1/T, and importantly, this an additive term in the complexity instead of multiplicative. This additive dependence was non-trivial to achieve even in the optimal rates for heavy-tailed mean estimation in the non-robust (and non-sparse) setting. See the [LM19a] survey for a more detailed discussion.
1.3 Our Approach
The algorithm we propose fits into the stability- filtering approach that was first proposed by [DKK-16 16) (also see the recent survey [DK19]). Using a filtering algorithm is a by-now-standan technique in algorithmic robust statistics, and the approach can be summarized as follows: 1) with high
3

---

probability over the sampling of the n uncorrupted samples, there exists large subset of uncorrupted samples (say, a 11-00 O(e) fraction) satisfying a "stability" condition with respect to the mean of the uncorrupted distribution, and 2) filtering algorithm taking as input a corrupted version of the stable samples will remove some of the samples, such that the sample mean of the remaining points is guaranteed to be close to the true mean, which can then be returned as the final estimate. The notion of "stability" depends crucially at the task at hand, and is defined below for the sparse estimation problem.
Stability- -Batedd Algorithm for Sparsity Informally speaking, we say a set S' is stable when the mean and the covariance of S do not deviate too much when we remove a few elements from S. For the context of sparse estimation, we would like to measure the deviation only along the k-sparse directions. However, it NP-hard to calculate the maximum of u Au over k-sparse unit vectors for an arbitrary matrix A (this is known as the sparse PCA problem [TP14]). Following [BDLS17], our definition of stability would involve a convex relaxation of the above optimization problem, using the following definition of the set Xg and the matrix norm || ||x.
Definition 1.4 (The set X4 and the norm || llxx)) )- The set X₂ is defined as the set of positive semi- definite matrices that have trace and f--rrrm at most is when flattened vector. The matrix norm || is then defined as supMex, |A M). where A M denotes the trace product tr(AT M).
Note that for any square matrix A, ||Al|x, is always upper bounded by its spectral norm. Furthermore, observe that for any square matrix A, the maximum of v AA over k-sparse unit vectors is upper bounded by ||A Ix,, and the latter can be calculated efficiently using convex program. We are now ready to define the stability condition.
Definition 1.5 (Stability Condition). For 0 < < 0.5 and e S 8, set S is (e, 6, k)-sbuble with respect to μ E Ed and a E R+ if it satisfies the following condition: for all subsets S' c S with |St 2 (1 - e), the following holds: (i) llas. pll2,x S σő, and (ii) [[5s - o²1 S oz882/ /e, where u. (1/\5'l) Engs' is the sample mean of S' and Es = (1/15') Exss: (x-))<x=-p)p) is the second moment of S'
Definition 1.5 is intended for distributions with covariance matrices at most 0² times identity. We will omit μ and a above when they are clear from context. Focusing on the Gaussian distribution with identity covariance, [BDLS17] gave computationalll--ffiiiee algorithm with k2 log d samples.'
By using the standard median-of-menn problem to the case when the corruption parameter is constant, say 0.01, and aim to achieve only constant estimator error in the f2 norm. For this regime, we state the guarantees of robust sparse mean estimation algorithm of [BDLS17] (developed for the Gaussian setting) as follows?:
pre-processing described in Section 2, we can reduce the
Fact 1.6. Let S be set in Rd such that there exists a set S' C S such that (i) |S'| 2 0.99||] and (ii) S' is an (0.01, O(1), stabba with respect to (unknown) i and (unknown) a. There is a poly([S),d) d)-time algorithu that takes input T, an 0.01-corrupiion of S, and returns mean estimate ja such that [ - 1112,, I ((o).
Given the prior algorithmic result, the remaining challenge is to show that, even in the setting of heavy-tailes data, a large subset of the uncorrupted samples satisfies the "stability" condition with high probability. In the dense setting, [DKP20, HLZ20] showed that O(d) samples suffice for stability, which is too large for our setting.
Truncation is Necessary for Stability Recall that our goal is to show that, if we sample k2 log d samples from a heavy-tailed distribution, then contains a large stable subset. For the light-tailed data (Gaussian), this shown in [BDLS17]. However, this statement is not true for general heavy-tailed distributions. Consider the standard setting for modelling heavy-tailed data, that the covariance E of the uncorrupted distribution is upper bounded by the identity. For simplicity, also assume that the sparsity parameter k., corruption parameter e and failure probability 7 are all constants. Thus, our goal is to show that, with high probability, there is large stable subset among log d samples. Yet, as we show in Example in Section 3, there exists a distribution where deterministically for any set of even (d) many uncorrupted samples, no large subset can be stable. This distribution is the one
1 'The additional factor of in their sample complexity (cf, Fact 1.2) is because the convex relaxation involving Xx norm can be loose. However, [DKS17, BB20] suggest that k22 samples are needed for efficient algorithms. See also [ZJS21] for related algorithm.

---

returning a vector of length vd from a randomly chosen axis direction, which has unit covariance. Essentially, the long length of d along directions as sparse the axis directions causes stability to fail to hold.
In order to circumvent this obstacle, we propose to "truncate" all the samples in &oo norm, before using a stability-based filtering robust mean estimation algorithm: compute an initial mean estimate, then clip each sample coordinate-wise to within radius of @(Vi)) of the initial mean estimate. This radius is chosen carefully to ensure that the mean of the original distribution and the clipped distribution is close in knnomm Ensuring that the clipped distribution also has small variance turns out to be non-trivial as we detail below.
Necessity of Bounded Higher Moments After truncation, no point is too far from the true mean, but truncation can potentially also rotate a point about the true mean, in the sense that for a sample, the direction of its difference from the true mean may change after such truncation. In general, this rotation effect can cause much of the mass of the distribution to rotate and concentrate towards certain directions, and significantly increase the variance in those directions. (See Appendix A.4 for more details.) In this work, we identify the mild condition that the 4th moment is bounded along each axis direction by some constant, on top of our assumption that Σ < 7, to be sufficient to show that truncation can only increase variance in directions that are non-sparse, in the sense that the resulting covariance will still have bounded Xr. norm (see Lemma 3.1). Thus, under these mild conditions, we can safely truncate our samples (which is necessary for stability to hold as outlined above), and modify our goal to show this truncated distribution contains a large stable set with high probability.
Stability of Truncated Samples with High Probability Even after truncation and after imposing an axis-wise 4th moment bound, it remains challenging to show that, with high probability, there is large subset of samples that are stable with respect to the true mean.
As we see in Section 5, the analysis reduces to showing that with high probability over the uncorrupted samples, for every matrix M E Xx, there exists a large subset of samples S whose empirical covariance Eg has small inner product with M, namely that M Es is bounded. In the non-sparse setting, the strategy used in [DI.22b] and [DKP20] is to first show a high probability event for all M vy for unit vectors v, and then to show that the event for all M we" deterministically implies that the event holds also for all M 2 0 with tr(M) = 1. This strategy is important because although the cover of PSD matrices would roughly be exponential in dZ, the cover of ve" is only exponential in d. Thus the first step holds with roughly d samples, and the second step crucially uses the spectral decomposition (SVD) of positive semi-definite (PSD) matrices. On the other hand, in our sparse setting, if we applied the usual SVD to the PSDD matrices M E Xx, the resulting decomposition will generally not yield sparse components, and thus not allowing us to leverage sparsity. Instead, inspired by some matrix norm results derived by Li [Li18], we carefully design (non-spectral) decomposition that does yield ---sparse components and can be covered with k2 log d samples, as well as a more delicate argument to complete the second step, namely that the event holding for all components M in the decomposition implies the event holding for all M E Xx. The intricacies of these arguments also allow us to get a sample complexity that ultimately yields an additive (instead of multiplicative) dependence on log 1/T, which as described in the previous section is crucial feature of our result, and in line with the non-robust non- spa-sp nub-Gaussian mean estimation setting.
1.4 Related Work
Algorithmic Robust Statistics The goal of algorithmic robust statistics is to obtain dimension- independent asymptotic error even in the presence of constant fraction of outliers in high dimensions in computationally efficient way. Since the dissemination of [DKK 16, LRV 16], which focused on high-dimensional robust mean estimation, the body of work in the field has grown rapidly. For example, prior work has obtained dimension-indepenne as linear regression [KKM18, DKS19] and convex optimization [PSBR20, DKK* DKK+19a). See the recent survey [DK19 19] for a more detailed description. Most relevant to us are the works for robust mean estimation that leverage the sparsity constraints and obtain improved sample complexity. The algorithms developed in [BDLS177 DKK+19b, CDG+, DKK 22] obtain optimal asymptotic error for light-tailed distributions such as Gaussians. However, these algorithms crucially rely on the light-tails and, as outlined in Section 1.3, provably do not work for heavy-tailed distributions.
guarantees for various problems such
5

---

Heavy-Tailed Estimation The recent decades also saw growing interest in studying statistics in heavy-tailed settings. Even for the basic question of univariate mean estimation without sample corrpption, the statistical limits are only recently resolved by line of work started by Catoni [Cat and ending with Lee and Valiant [L.V1] (see also [Min22] for an alternative estimator). There also much research effort on resolving the statistical limits of various nigh-dimensional estimation tasks for heavy-tailed distributions, for example, mean estimation in l2 norm [LMI9c] and in other norms [LM19b, DL22a], covariance estimation [MZ20], and stochastic convex optimization [BM22]. In absence of contamination, the goal is to obtain sample complexity as if the distribution were Gaussian. Roughly speaking, this corresoonds to additive dependence on the logarithm of failure probability in various estimation tasks (as we achieve also in this work). We refer the reader to the recent survey for more details [LMI9a]. This line of work focuses the statistical limits, and the estimators developed are generally computationally inefficient.
A closely-related body of research aims to obtain efficient algorithms for heavy-tailed distributions with optimal statistical performance, ideally matching the above guarantees. These works include high-dimensional (dense) mean estimation [Hop20, CFB19, DL22b, LLVZ20, DKP20, HLZ20, CTBJ22, LV22], linear regression [CHK 22, PJL20, Dep20b], and covariance estimation [CHK+20]. We note that many of these works are inspired by the algorithmic robust statistics literature, and can also tolerate a constant fraction of contaminated data.
To the best of our knowledge, none of these works studies sparse estimation under heavy-tailed distributions (even in absence of outliers), and our work is the first result with sample complexity that is additive in the logarithm of the failure probability.
2 Preliminaries
Notations Here we define the notations we use in the rest of the paper. For a (multi-)set S c Rd. we denote jas (1/1S1) Exes and Σs = (1/15)) Eres(x 1s) - [s) When the vector j notation is clear from context, we Es denote (1/1S)) Exes(
p.)
Let Uy denote the set of k-sparse unit vectors in Rd. For two vectors x and y. (x. v) denotes the dot product x: TTy, y. For vector x Rd,, we use ||=|||,, == suPestte (z, v) and | to denote maxy |zz]. For a matrix M, we use ||M]]] to denote Σi, [Ma, and || llo to denote the number of non-zero entries of M. For two matrices A and B, we use A o B to denote the trace inner product tr(AT B). Define Xx := {M M > tr(M)
1. || I k). For matrix A, we define ||A||xx, == SuPMEX, A M). For an E N, we use [n] to denote the set (1.....n).
Coordinate-wiss Median-of-Meant We use the coordinate-we wise median-of-meant algorithm to robustly obtain preliminary mean estimate, with guarantees captured by the following fact.
Fact 2.1. The coordinate-wise median-of-meant algorithm satisfies the following guarantee: given the corruption parameter e, failure probability т, and set T of many e-corrupted samples from distribution D with mean μ and axis-wise variance Ex=D((X, My ) S o² for all j [d], then with probability at least 1- over the sample set T, the output of the algorithm jo is such that - - S o0(ve+ /log(d/r))//n)
Median-of-Menn Pre-Processing Another standard technique we use in this paper is the median- of-means pre-processing, which is distinct technique from the coordinate- wise median-of-mean algorithm mentioned right above. Recall that in Theorem 1.3, the asymptotic error term is ve. which tends to 0 as the corruption parameter + 0. The following pre-pescsssing step allows us to reduce the problem from the - 0 case to a constant e case: Split the samples randomly into g equally-sized groups of size m n//g where g O(en), and replace each group by the sample mean of the group. The effects of this pre-proeed processcsssing is captured by the following Fact 2.2, which prove for completeness.
Pre-Processing) Suppose there is an efficient algorithm such that, on input E RE,, and 0. O.1-corrupeed set of n > k² log d + log(1/7) samples from distribution D with mean i and covariance with || [ [x, S o² and Ex=D((X, =1;)a1 = O( ) for each coordinate j [d], returns d such that [ Holl2, O(o) with probability at least 1
Fact 2.2 (Median-of-Ne

---

Then, there is an efficient algorithm such that, on input E (0, 0.1) and an e-corrupted set of n > (k² + +log(1/T))/ samples from a distribution with mean μ and covariance E, satisfying | I I satisfying Ex-D [=]]²]= O(1) for every coordinate E [dl, returns mean estimate ii such that / 2, S (v(c) with probability least T.
3 Truncation Pre-Processing
The general approach for using a stability-basee filtering algorithm, for algorithmic robust statistics, to show that given sufficiently many samples, there exists a large (say O()) fraction) subset of the samples that are stable with respect to the true mean μ. However, the following simple example shows that it is not possible for i.i.d. samples from a heavy-tailed distribution to satisfy the sparse stability in poly(log d) samples.
Example 1. For any number of moments t 2 2, there is a distribution X satisfying the following conditions: (i) The mean of X is and for every unit vector v, the thh moment direction is upper bounded by 1, that is, EEI,,, S forort 2 2, (ii) If is an arbitrary set n S o(d2/t) points from the support of X, then the S cannot be (e, O(VE), k)-stablee, for any > O, with respect to the mean of the distribution. As conollary, no subset of S can be stable either.
We show Example 1 in Appendix B.
Thus, we need to modify the algorithm we want to do robust sparse mean estimation using poly(k, log d) samples. Our approach is to perform initial truncation of the samples, before using a stability- based robust mean estimator. A balance needs to be struck, in order to truncate sufficiently for stability to hold (with high probability over the samples), but also to truncate mildly enough such that the mean (and covariance) of the truncated distribution does not shift too much.
For scalar a E R+ and a vector b E Rd, let ha,b IRd - Rd be the following thresholding function:
Mie if I b;l S a bi + a
Vi [d]. ha,b(1);
if x; b, 2 a if rr b S -a
bi -a a
Note that hx,)()) projects the point x the 6 ball of radius a around b.
As explained in the Introduction, truncation in general rotates a point about the true mean, and thus can in fact cause the covariance of the distribution to grow in certain directions. The following lemma captures the fact that, if we make the further mild assumption that the distribution has bounded 4th moment along all the axis directions, then will least be able to preserve the X₂ norm of the covariance matrix. The proof of Lemma 3.1 is also in Appendix B.
Lemma 3.1 (Truncation in foc.. Let be a distribution over Rd with mean μiP and covariance Ep, with |||| S a² for some o² > O. Let X ~ P and assume that for all j E [d], TB((X |r) S AA for some v 2 1. Let b E I2d be such that I|b - palloo S a/2 and a == 20 /k/e for some e E (0. Define Q to be the distribution Y := (X). Let the mean and covariance of Q be bt and Eq respectively. Then the following hold:
(1) | - Pollo Sove/k
(2) |pp -00--1lll2 5 Save
(3) |Ep Eqlix, S <30fev
(4) For all E [d]. E( (2)ii < 84
(5) |Y xol|x < 2a 4o vk/e almost surely.
In Lemma 3.1 above, represents the initial mean estimate, and ji will be obtained by Fact 2.
4 Algorithm and Analysis
The high-level algorithm we propose is stated follows.
7

---

Algorithm Robust Sparse Mean Estimation with High Probability
1. Input: An e-corrupted sample set Rd of size
2. Median-of-Meen
pre-processing: Group points into g groups, each of size n/g. where g = ((en), and take the sample mean of a group to be a new point
3. Compute initial coordinate-wise median-of-means estimate jú
4. Truncate all points to within Bo 2v 2/k),, namely, given a point x, we replace it with the point , (2)), where ha.5 is defined in Equation (1).
5. Run the stability-base -base robust sparse mean estimator from Fact 1.6 on the samples after the processing of Step 4.
We note that this algorithm is shift and scale invariant, based on the same invariance of the median- of-means pre-processing as well as the invariance of the robust sparse mean estimator from Fact 1.6.
We will now prove that Algorithm satisfies the guarantees of Theorem 1.3 and its stronger version, Theorem D.12. Our analysis uses Theorem D.11, which states that, with high probability, there exists a set consisting of most the truncated samples that stable with respect to some point close to the true mean in so norm. In Section 5, we outline the central part (Theorem 5.1) of the proof of this theorem. We have not optimized constants in our analysis.
Proof of Theorems 1.3 and 12 By Fact 2.2, it suffices show that, for every 0, Steps 3-5 in Algorithm 1 yields an ((r) estimation error in l2 norm when given corrupted samples from distribution with covariance bounded by R² and aiss 4th moment bounded by O(a*).
Theorem D. states that, with probability at least 1 T, the samples after the processing of Step 4 are such that there exists a 95% the samples that form a (0.1, 0(1), -t--baele subset with respect to some vector p' and a with || - plase I O(a ((o/v)). Fact 1.6 then guarantees that, on input such set of samples, the algorithm we invoke Step 5 of Algorithm I will return mean estimate such that || 1l s O()). Further, since | - pll O(a/Vk)), have that ||pl - μ4 2. I (()). and therefore we can conclude with the triangle inequality that the mean estimate j satisfies /| nl|2, O(a).
Stability After Removing Points: Additive dependence on log(1/T)
In this section, we sketch the main stability result in this paper. Recall, via the median-of-means pre-processing, that we only need to consider the constant contamination goal to show (Theorem D. l) that with high probability, after truncation according to the coordinate- wise median-of-mest preliminary estimate, there exists a large subset of uncontaminated samples that is (0(1), O(a), k) stable with respect to the true mean of the distribution where o = ||i|,,,
(e === @(1)). Thus, the
Theorem 1 below, an informal version of Theorem C.1 in Appendix C. captures the core of the argument. The key difference between Theorems 5.1 and D. is that the former is stability result concerning uncontaminated samples truncated according to some fixed vector close to the true mean. the other hand, the final stability result we require concerns samples truncated according to the coordinate-vee wise wise median-of ceddian-of-meane meams estimate, which itself depends on the samples and is not fixed. Appendix D shows the delicate argument going from Theorem 5.1 to Theorem D.11.
Theorem 5.1 (Informal version of Theorem C.1). Let S be a set of i.i.d. data points from distribution P over Rd. Let the mean of P be μ. and covariance E such that [|El|x, S o², and for all [d], [[X O(at). Suppose P is supported over the set {x: || plloc O(ovk)), n 12k22 log + log(1/T)), then, with probability 1 T, there exists a set S' S such that:
1. SS| 2 0.98n
2. S' is (0.01, 6, k)-stable with respect I and where 8 0(1)
For the rest of the section, sketch the proof of Theorem 5.1.

---

Proof sketch for Theorem 5.1. In the following proof sketch, we hide most multipiccative constants. The proof of Theorem C.1 Appendix C will make explicit the calculations for completeness. For the rest of the sketch, we will also assume μ 0 without loss of generality.
Instead of directly showing the existence of subset 5' C S (with high probability over the sam- ples S) that is stable, we will be working with weights/distriuutions over the set S of samples. Given a weight vector w and S = [nn) C R", denote En by Σ, w;2,a,"" Then, Proposition A.1 in Appendix A lets show the following simpler condition instead: let An,e
be the set of weights/disttibutiinss w such that w, I 1/(1 - c), then there exists a weighting w E An,0.0 such that E lxx I (o That is, for the following proof, we just need to prove that mitl.eA,,... _ = O(a²).
We proceed as follows:
min
|
min max M Σ weAn.0.01 MEX.
max min MEX, w.r.an..om
M Σ
wEA...0.r
where the last equality is straightforward application of the minimax theorem for a minimax optimization problem with independent convex domains and bilinear objective. It thus suffices to show the following: with probability
T,,
VM E Nu H E : Mx, > d² S 0.01|S|
(2)
and we can construct the weight wM as uniform distribution over the elements outside the above set. Define the following sets of sparse matrices, the first of which also appears in [Li18]:
A = { E Rdddd All S 12, || All S =1}
AR.P = { (A E A. PP- (x Az > o²) - small constant).
(3)
If >> h22 log + (L/T,, then a standard covering/ Dovering/CC-dimen VViddmnnnno bound (see Lemma B.2 for details) implies that the following event holds with probability T:
E Ae.p: E Ax > o²)|
H S 0.002 (S].
We will now show that the event in Equation (4) implies that the event in Equation (2) holds. Note that the constants hidden in the >> notation in Equations Equation (2) and Equation (4) are different, which is the slackness that makes the implication possible. As mentioned, we will make these
constants explicit in the formal proof in Appendix C.
Suppose, for the sake of contradiction, that the event in Equation (2) does not hold. Then there exists an M E Xg such that Hz E S I Mx; >> d²}l > 0.01|S]. We will show the existence of a matrix Q violating event Equation (4), via the probabilistic method, reach the desired contradiction.
To achieve this, we define decomposition of M X₁ into components in As.P. the sense of a distribution over matrices Q such that 1) [[[]] = M and 2) small constant multiple of Q belongs to AR,P with high constant probability. We will additionally show that this decomposition Q roughly preserves quadratic forms, in that if M violates Equation (2) then Q violates Equation (4) with non-trivial probability.
Fixing an M that violates Equation (2), consider the random matrix Q where each entry Q is inde- pendently set be Ma./Pi.j with probability Pt.j and 0 otherwise, where pi. min( 1, k M l/c) for large constant c > 0.
We will show that the following events hold simultaneously with non-zero probability, leading to a contradiction to event Equation (4): (i) Qfd E Ar,P for a large constant é' and (ii)
Hr E S x (Q/d')z, >> o2]l > 0.002 . |S]. Using different techniques, we will show that the first condition holds with probability at least 1 - 2 10-8 and the second condition holds with probability at least 4 x 10-6, thus implying that the events hold simultaneously with non-zero probability.
Condition (i), that Q/c' E Ar. with high constant probability. Showing that Q/c belongs to As is straightforward: by the construction of Q, it has small expected sparsity as well as small expected Frobenius norm. An application of Markov's inequality shows that Q/v E Ar with high constant probability (Lemma C.2).

---

The trickier part is to show that Q/d is also in At. namely that Fa-p(x' (Q/cc)) > o2) is upper bounded by the small constant. We consider the distribution of x QQ over the probability of independently drawing x ~ P and random Q, and show that x Qx small with high probability over this joint distribution (Lemma C.4), which requires using the axis wxis-wise 4th moment bounds on P as well as the fact that M E Xg.. Lemma C.3 implies that with high probability, we will draw Q satisfying P2-p(x) Qr >> o²) being bounded by small constant.
Condition (ii), that if M violates Equation (2) then Q violates Equation (4) with non-trivial probability We consider the random variable Z = Σg L., Qu, over the randommess of Q. The overall strategy is to lower bound [ to show that with at least small constant probability, Z 2 cn/22, where we use Z always is less than n. The expectation of Z is just the average over samples the probability that x Qzi > o². Since the fraction of 2,s with x; Mx; >> o² is at least a constant, to lower bound E E|Z], suffices for us to lower bound this probability for each such Z3. Fix any such x: for the remainder of the argument.
for a small
and use the Paley-Zygmunt inequality
Lower bounding the probability that x: Qx >> 0² is non-trivial, since, the support of the quadratic form can scale with k and given a lower bound on its expectation, it could be the case that it is 0 with high probability and has huge value with small probability.
We will argue that this does not happen by considering two cases, First, and the simpler setting, is when x Qz has small variance. In this case, we can use Chebyshev's 's inequality to lower bound the probability that x Qx >> o². Essentially, this is the case when x' Qr is "concentrated".
The second, and the more involved setting, is when x' Qr has large variance. Here, we would like to argue that x: Qx is sufficiently canti-concentrated" like a Gaussian, the sense that there is a constant probability mass above its mean. Noting that x: Qr Lie|d]jeed (1r) (z)) and the entries of Q are independent, this is sum of independent terms, and we can reasonably expect Gaussian-like behavior. Concretely, we will show this using the Berry-Essend theorem, which requires us to upper bound the third moment of x Qr. This upper bound crucially uses the facts that 1) the samples here are truncated, which implies that each (z) has bounded magnitude and 2) each Qi, is (scaled) Bernoulli which has exact and simple expressions for its second and third moments.
Summarizing, we argued that conditions (i) and (ii) hold simultancously with non-zero probability, thus showing the existence of Q violating Equation (4), reaching a contradiction assuming the existence of some M violating Equation (2). Therefore, Equation (4) implies Equation (2), which completes the argument for Theorem 5.1.
Acknowledgements
We thank the anonymous reviewers for helpful comments the paper. Ilias Diakonikolas was supported by NSF Medium Award CCF-2107079, NSF Award CCT-1652862 (CAREER), a Sloan Research Fellowship, and a DARPA Learning with Less Labels (LwLL) grant. Daniel Kane was supported by NSF Medium Award CCF-2107547, NSF Award CCF-1553288 (CAREER), and grant from CasperLabs. Jasper C.H. Lee was supported in part by the generous funding of Croucher Fellowship for Postdoctoral Research, NSF award DMS-2023239, NSF Medium Award CCF-2107079 and NSF AiTF Award CCF-2006206. Ankit Pensia supported by NSF grants NSF Award CCF- 1652862 (CAREER), DMS- and
Part of this work was done while Ilias Diakonikolas, Jasper C.H. Lee and Ankit Pensia were visitors at the Simons Institute for the Theory of Computing.
References
[ABH 72) D. F. Andrews, P. J. Bickel, F. R. Hampel, P. J. Huber, W. H. Rogers, and J. W. Tukey, Robust Estimates of Location: Survey and Advances. Princeton University Press, 1972.
[AV19] M. F. Ahsen and M. Vidyasagar. An approach to one-bit compressed sensing based on probably approximately correct learning theory. Journal of Machine Learning Research, 1(11):1123,2011
10

---

[BB20] M. Brennan and G. Bresler. Reducibility and statistical-coman computational gaps from secret leakage. In Proc. 33rd Annual Conference on Learning Theory (COLT), 2020.
[BDLS17] S. Balakrishnan, S. Du, J. Li, and A. Singh. Computationally efficient robust sparse estimation in high dimensions. In Proc. 30th Anmual Conference on Learning Theory, 2017.
[BM22] D. Bartl and Mendelson. On Monte-Carlo methods convex stochastic optimization. The Annals of Applied Probability, 32(4):3146 3198, 2022.
[Car12] O. Catoni. Challenging the empirical mean and empirical variance: A deviation study. Annales de l'Institul Henri Poincaré, Probabilités el Statistiques, 2012.
[CDG*] Cheng, I. Diakonikolas, R. Ge, S. Gupta, D. M. Kane, and M. Soltanolkotabi. Outlier-robust sparse estimation via non-convex optimization. In To appear in NeurIPS 2022.
[CFB19] Cherapanamjeri, N. Flammarion, and P. L. Bartlett. Fast mean estimation with sub- bub-gaussian rates. In Proc. 32nd Annual Conference Learning Theory (COLT), 2019.
[CHK+20] Y. Cherapamammerri, S. B. Hopkins, T. Kathuria, P. Raghavendra, and N. Tripuraneni. Algorithms for heavy-tailed statistics: Regression, covariance estimation, and beyond. Proc. 52nd Annual ACM Symposium on Theory of Computing (STOC), 2020.
[CTBJ22] Cherapanamjeri, N. Tripuraneni, P. L. Bartlett, and M. I. Jordan. Optimal Mean Estimation without Variance. In Proc. 35th Annual Conference Learning Theory (COLT), 2022.
[Dep20a] J. Depersin. Robust subgaussian estimation with VC-dimension. CoRR, abs/2004. 1174,, 2020.
[Dep20b] J. Depersin. A spectral algorithm for robust regression with subgaussian rates. CoRR, abs/2007.06072. 2020.
[DG92] D. Donoho and M. Gasko. Breakdown properties of location estimates based on halfspacc depth and projected outlyingness. Ann. Statist., 20(4):1803-182) 12 1992.
[DK1]] I. robust statistics. arXiv preprint (tt:::9911009911 2019.
Diakonikolas and D. M. Kane, Recent advances in algorithmic high-dimensional
[DKK 16] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators in high dimensions without the computational intractability. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS), 2016.
[DKK + 19a] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, J. Steinhardt, and A. Stewart. Sever: A robust meta-algorithm for stochastic optimization. In Proc. 36th International Conference on Machine Learning (ICMI.), 2019.
[DKK 19b] I. Diakonikolas, S. Karmalkar, D. Kane, E. Price, and A. Stewart. Outlier-robust high- dimensional sparse estimation via iterative filtering. In Advances in Neural Information Processing Systems, (NeurIPS), volume 32, 2019.
[DKK +2] I. Diakonikolas, D. M. Kane, S. Karmalkar, A. Pensia, and T. Pittas. Robust sparse mean estimation via sum of squares, In Proc. 35th Annual Conference on Learning Theory (COLT), 2022.
[DKP20] I. Diakonikolas, D. M. Kane, and A. Pensia. Outlier Robust Mean Estimation with Subgaussian Rates via Stability. Advances in Neural Information Processing Systems, (NeurIPS), volume 33, 2020.
[DKS17] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. In Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 73-84, 2017.

---

[DKS19] I. Diakonikolas, W. Kong, and A. Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proc. 30th Annual Symposium on Discrete Algorithms (SODA), 2019.
[DL88] D. L. Donoho and R. C. Liu. The "Automatic" Robustness of Minimum Distance Functionals. The Annals of Statistics, 16(2):552-535 586, 1988.
[DL22a] J. Depersin and G. Lecué. Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms. Probab. Theory Relat. Fields, 183:997- 1025, 2022.
[DL22b] J. Depersin and G. Lecué. Robust sub- Gabb-Gasssinn estimation of a mean vector in nearly linear time. The Annals of Statistics, 50(1):511-5366 February 2022.
[EK12] Y. C. Eldar and G. Kutyniok. Compressed sensing: theory and applications. Cambridge university press, 2012.
[GKT51] D. Gale, H. W. Kuhn, and A. W. Tucker. Linear programming and the theory of games. Activity analysis of production and allocation, 13:317-335, 1951.
[HLZ20] S. B. Hopkins, J. Li, and F. Zhang, Robust and Heavy-Tailer -ailed Mean Estimation Made Simple, via Regret Minimization. In Advances in Neural Information Processing Systems, (NeurPPS), volume 33, 2020.
[Hop20] S. B. Hopkins. Mean estimation with sub-Gaussian rates in polynomial time. Annals of Statistics, 1993))1999-,,,,,, 2020.
[HR09] P. J. Huber and M. Ronchetti. Robust statistics. Wiley New York, 2009.
[5T T. Hastie, R. Tibshirani, and M. Wainwright. Statistical Learning with Sparsity: The Lasso and Generalizations. Chapman & Hall/CRC, 2015.
[KKM18] A. Klivans, Kothari, and Meka. Efficient algorithms for outlier-robust regression.
In Proc. 31st Annual Conference on Learming Theory (COLT), 2018.
[Li18] J. Li. Principled Approaches Robust Machine Learning and Beyond. PhD thesis, Massachusetts Institute of Technology, 2018.
[LLV720] Z. Lei, K. Luh, P. Venkat, and F. Zhang. A fast spectral algorithm for mean estimation with sub- gaussian rates. Proc. 33rd Annual Conference on Learning Theory (COLT), 2020.
[LM19a] G. Lugosi and S. Mendelson. Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey. Foundations of Computational Mathematics, 1445 1190, 2019.
[LM19b] G. Lugosi and S. Mendelson. Near-optimal mean estimators with respect general norms. Probability Theory and Related Fields, 175(3-4):557-973 2019.
[LM19c] G. Lugosi and S. Mendelson. Sub-Gaussian estimators of the mean of random vector. The Annals of Statistics, 47(2):783-794, 2019.
[LRV16] K. A. Lai, A. B. Rao, and S. Vempala. Agnostic estimation of mean and covariance. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS), 2016.
[LV21] J. Lee and P. Valiant. Optimal Lub-Gaussian Mean Estimation in IR. Proc. 62nd IEEE Symposium Foundations of Computer Science (FOCS), 2021.
[LV22] J. C. H. Lee and P. Valiant. Optimal sub-gaussian mean estimation in very high dimensions. Proc. 13th Innovations in Theoretical Computer Science Conference (ITCS), 2022.
[Min22] S. Minsker. U-statistics of growing order and sub- sub-gaussian mean estimators with sharp constants. CoRR, abs/2202. 18842, 2022.
12

---

[MZ20] S. Mendellon and N. Zhivotovskiy. Robust covariance estimation under L1 L2 norm equivalence. Annals of Statistics, 48(3):1648-1664 2020.
[PBR20] A. Prasad, S. Balakrishnan, and Ravikumar. A robust univariate mean estimator is all you need. In Proc. 23rd International Conference Artificial Intelligence and Statistics (AISTATS), 2020.
[PJL20] A. Pensia, V. Jog, and P. Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. CoRR, abs/2009. 12976, 2020.
[PSBR20] A. Prasad, A. S. Suggala, S. Balakrishnan, and P. Ravikumar. Robust estimation via robust gradient estimation. Journal the Royal Statistical Society: Series B (Statistical Methodology), 82(3):601-627, July 2020.
[TP14] A. M. Tillmann and M. E. Pfetsch. The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing. IEEE Transactions on Information Theory, 60(2):1248- 1259, 2014.
[Tuk60] J. W. Tukey. A survey of sampling from contaminated distributions. Contributions probability and statistics, 2:448 4854, 1960.
[van16] S. van de Geer. Estimation and Testing Under Sparsity. Number 2159 in École d'été de Probabilités de Saint-Flour. Springer, 2016.
[Ya885] Y. G. Yatracos. Rates of convergence of minimum distance estimators and Kol- mogorov's 's entropy. Annals of Statisties, 13:768-774, 1985.
[7JS21] B. Zhu, J. Jiao, and J. Steinhardt. Robust estimation via generalized quasi-gradients. Information and Inference: A Journal of the IMA, 11(2)5811-63, 08 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
13

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xqhwUbSCxTe", "reviewer": "Reviewer_VSiz", "summary": "Algorithmic robust statistics is concerned with building efficient algorithms for statistical estimation problems when the observed data contains adversarial or heavy-tailed noise. For the canonical problem of mean estimation, a single grossly corrupted data point can completely invalidate the performance of the sample average as a natural estimate of the population mean. In the problem of heavy-tailed mean estimation under the strong contamination model, one observes $n$ data points generated in the following manner:\n\n1. First $n$ ``good'' data points are generated from the true underlying heavy-tailed distribution $D$. Note that assumptions on $D$ are usually very mild -- often only that its variance exists. \n2. An adversary then inspects the generated samples and corrupts an arbitrary set of $\\epsilon n$ points in a completely unconstrained manner.\n\nGiven a target failure probability $\\delta$ and corrupted dataset  $X = \\left\\\\{x_i\\right\\\\}_{i = 1}^n \\subset \\mathbb{R}^d$, the goal is to optimally recover the mean of $D$ generating the good data points. Here, optimality is measured in terms of the relevant parameters of interest $n, d, \\delta, \\epsilon$. With no further assumptions, computationally efficient algorithms have been designed achieving the information theoretically optimal rate of:\n\\begin{equation*}\n    O \\left(\\sqrt{\\frac{d}{n}} + \\sqrt{\\frac{\\log (1 / \\delta)}{n}} + \\sqrt{\\epsilon}\\right).\n\\end{equation*}\nNote that this rate is optimal upto constants -- in fact, a family of Gaussians witness the terms depending on $d$ and $\\delta$ despite making no assumptions on the higher-order moments of $D$. \n\nThe paper considers the sparse setting where the mean, $\\mu$, of $D$ is $k$-sparse. In typical sparse estimation problems, this usually allows an improvement of the sample complexity to depending polynomially only on $k$ and poly-logarithmically on $d$. In this paper, the authors construct an algorithm for sparse heavy-tailed mean-estimation achieving optimal recovery when $n \\gg (k^2 \\log (d) + \\log (1 / \\tau)) / \\epsilon$ which is optimal under the conjectured statistical computational gap (information theoretic recovery is possible with $(k \\log (d) + \\log (1 / \\delta)) / \\epsilon$ samples). The paper imposes a mild assumption on the higher order moments and assumes additionally that $\\mathbb{E} [(X_i - \\mu_i)^4] = O(1)$.\n\nTechnically, the paper uses a well-established stability based framework for robust estimation with some minor modifications. Specifically, the data points are truncated in the $\\ell_\\infty$ norm (using a coarse estimate of the true mean using the coordinate-wise median-of-means estimate) to remove spikes along sparse directions and utilizing a standard median-of-means pre-processing technique. Having established these stability conditions, the algorithm follows largely from the prior work. \n\nIn the dense setting, the goal is to establish a set of well-spread weights $w$ such the empirical covariance of the data points weighted by $w$, $\\Sigma_w$, is small in spectral norm. Intuitively, $w$ would ideally be the uniform distribution over the good data points. Formally, one requires:\n\n$$\n    \\min_w \\lVert \\Sigma_w \\rVert = \\min_w \\max_{M \\succcurlyeq 0, \\mathrm{Tr} M = 1} \\langle \\Sigma_w, M \\rangle = \\max_{M \\succcurlyeq 0, \\mathrm{Tr} M = 1}  \\min_{w} \\langle \\Sigma_w, M \\rangle = O(1)\n$$\n\nwhere the inversion of the min and max is guaranteed by von-Neumann's min-max inequality. The last step is crucial since it suffices to design a set of weights depending on the ``direction'' $M$. Through a clever rounding argument from [DL 22], it suffices to only consider the case where $M$ is rank $1$ up to appropriate adjustments in constants. Therefore, one only requires $d$ data points to effectively cover the set of plausible directions as opposed to the $d^2$ sized cover of $M$.\n\nIn the sparse setting, it suffices to only search for sparse directions leading to the following modification of the above equation:\n\n$$\n    \\min_{w} \\lVert \\Sigma_w \\rVert = \\min_{w} \\max_{M \\succcurlyeq 0, \\mathrm{Tr} M = 1, \\lVert M \\rVert_1 \\leq k} \\langle \\Sigma_w, M \\rangle = \\max_{M \\succcurlyeq 0, \\mathrm{Tr} M = 1, \\lVert M \\rVert_1 \\leq k}  \\min_{w} \\langle \\Sigma_w, M \\rangle = O(1)\n$$\n\nTo prove the stability condition, the authors proceed through a similar rounding argument as [DL 22] with the additional difficulty that it is not clear how to round such a $M$ to a sparse vector/matrix. In the dense case, it suffices to draw a zero-mean Gaussian with covariance $M$. Inspired by [Li 18] (where a decomposition of such a matrix into a sum of sparse matrices is carried out in Lemma 3.4.4), the authors design a careful probabilistic decomposition of $M$ to carry out this approach.\n\n[DL 22] J. Depersin and G. Lecué. Robust sub-Gaussian estimation of a mean vector in nearly linear time.\n\n[Li 18] J. Li. Principled Approaches to Robust Machine Learning and Beyond.\n\n**** POST REBUTTAL UPDATE ****\n\nI acknowledge the authors' response and will retain my current evaluation.", "questions": "My main question to the authors is the requirement of higher-order moments. In the example provided in the paper, they construct a distribution centered at $0$ with identity covariance that when $\\ell_\\infty$ truncated at $\\sqrt{k}$, whose covarince increases in spectral norm to $O(d / k)$. However, this is along an extremely dense direction oriented along the all 1s vector. It still remains the case that if one were only looking along sparse directions, the variance would remain small. In this case, it is not obvious to me that higher order moments are required. It would be immensely helpful if the authors could comment further on the necessity of these assumptions.\n", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper makes significant progress the problem of building robust estimators for sparse mean estimation under heavy tailed and adversarial noise. Prior results only held for dense setting or under extremely strong distributional assumptions such as sub-gaussianity. However, one downside to the paper is the lack of technical novelty the design and analysis of the estimator. The algorithm follows naturally from well-established frameworks and its subsequent analysis is based on a rounding approach from prior work. However, the decomposition of sparse matrices for the rounding step to go through is novel and interesting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "wmPUtC3f7o", "reviewer": "Reviewer_kKU6", "summary": "The paper study robust mean estimation in a sparse high-dimensional setting. Specifically, the goal is to exhibit an estimator that verify the following properties: the estimator has a sub-gaussian concentration  around the true mean when the data are heavy-tailed, the error due to a proportion epsilon of corrupted data can be controlled and is of order $O(\\sqrt(\\epsilon))$. \n\nThe authors use the $\\ell_2$ norm of the $k$ largest coordinates of a vector in magnitude to define a sparse distance and they show how to construct an estimator verifying the aforementioned properties with respect to this distance. Thanks to this sparse notion of distance they replace the usual dimension-dependent error by an error that depends on $k$ which can be a lot larger when the data are truly sparse.", "questions": "\n- The estimator does not seem computable, which contrast with the author's claim that it is. The theorems provided in the article guarantee a polynomial complexity, however this does not guarantee that the estimator is computable in practice. Moreover, the choice of constants given in Section C.1 does not seem to be practical. Finally, no experiment were given with the article which seems to indicate that it is not usable in practice. Could the authors comment on that ?\n\n- Would the analysis still work with only two finite moments  ? Is a fourth finite moment something that is needed for the algorithm to work ?\n\n- The algorithm for now needs to know $\\epsilon$. Is there a hope to give an algorithm that does not need the knowledge of $\\epsilon$ ? For example the Tukey median does not need the knowledge of $\\epsilon$ but it is not computable.\n\n- The constants are hidden even though it can be very important to have tight constants in front of the leading term (See Catoni \"Challenging the empirical mean and empirical variance: a deviation study\" (2012) and the more recent work of S.Minsker \"U-statistics of growing order and sub-Gaussian mean estimators with sharp constants\" (2022) investigating this problem in dimension 1). If the constants are very far from being tight, it should be said in the article.\n\n- Even though the authors claim that $O(\\sqrt{\\varepsilon})$ is optimal in your setting, this does not seem to be true. When the data have a finite fourth moment as in Theorem, $O(\\varepsilon^{3/4})$ and more generally when the data have $q$ finite moments, the optimal error is $O(\\varepsilon^{1-1/q})$ (see S. Minsker \"Uniform bounds for robust mean estimators\" for example). This discrepancy seems to be due to the requirement of $k \\ge 1/\\sqrt{\\varepsilon}$ in Lemma E.1. When $\\varepsilon$ goes to $0$, this requirement is very strong. On the other hand, when $\\varepsilon$ is larger than some constant $\\varepsilon_0$, then we can say that $\\sqrt{\\varepsilon}\\le \\varepsilon/\\varepsilon_0$ and hence $O(\\sqrt{\\varepsilon})=O(\\varepsilon)$ which makes me think that the interesting case is when $\\varepsilon$ goes to $0$. Could the authors comment about that ?\n", "limitations": "No potential societal impact.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This is mostly clear and states the assumptions and results properly. In general finding an estimator exhibiting optimal sub-gaussian rate and optimal corruption error is hard and this is the first algorithm I know that manage this in the sparse setting.\n\nWeaknesses: The paper claims that the algorithm used can be used in practice but I have doubts about that (more details in the questions). Some of the constants are hidden and it would be interesting the magnitude of these constant clearly. The paper is not very original and the theoretical results are not very surprising for an untractable algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ei4fRtPer7T", "reviewer": "Reviewer_5B6A", "summary": "This paper studies outlier-robust sparse mean estimation for heavy-tailed distributions. Prior work has considered robust sparse mean estimation for the light-tailed distribution (such as sub-Gaussian). The sample complexity for the proposed algorithm scales with k^2 log d, which is near optimal, and the assumption for the underlying heavy tailed distribution is mild. \n\nHowever, the technical contribution of this paper is incremental: the usage of coordinate MOM estimators for heavy tailed distribution is standard, and the filtering analysis basically follows from [BDLS17], which involves a time-consuming sparse PCA relaxation. Hence, given the theoretical guarantees of prior algorithmic result, the remaining challenge is to show that a large subset of the uncorrupted heavy tailed samples satisfies the “stability” condition.", "questions": "The presentation of Algorithm 1 is confusing. It would be great if authors can present the algorithmic box in a self-consistent fashion.", "limitations": "Please refer to the Strengths And Weaknesses session.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n-- The introduction of the related work is comprehensive, and the theoretical presentation is clear. \n-- The theoretical guarantees matches the best-known results.\n\nWeakness:\n\n-- The theoretical innovation is quite limited.\n-- The actual running time for the algorithm is very time consuming compared to other robust sparse mean estimators.\n-- Provided vast literatures in robust sparse mean estimation ([BDLS17, DKK+19]), this paper does not have experimental comparisons to show potential superior performance than these baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NVGR9xAgPrd", "reviewer": "Reviewer_DNt7", "summary": "This paper considers robust mean estimation problem with sparsity constraint for heavy-tailed distribution. The proposed estimator is claimed to achieve the first sample complexity which has a logarithmic dependence on the dimension and tightly matches with other parameters.", "questions": "N/A", "limitations": "Yes.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I appreciate authors' effort in the paper. But to be honest, this paper is out of my expertise, and I found it hard for me to write a review which makes some sense. The system also keeps failing to process my request for a change in reviewers. To keep a high quality of review, I will just make an educational guess, authors and other reviewers may just skip my review.\n\nThank you for the effort.\n\nReviewer", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "F-COwFQhUSS", "reviewer": "Reviewer_L8yB", "summary": "The paper considers the problem of robust sparse mean estimation. In this problem, we observe samples from a heavy-tailed distribution whose mean is a sparse vector. This distribution is assumed to have bounded variance and is assumed to satisfy a weaker form of bounded 4th moment assumption. In addition, it is assumed that a constant fraction of the samples are arbitrarily corrupted by a malicious adversary. For this problem, the authors propose a mean estimator which achieves convergence rates of the order $O(\\sqrt{\\epsilon} + \\sqrt{k^2\\log{d}/n} + \\sqrt{\\log(1/\\tau)/n})$, where epsilon is the fraction of corruptions, k is the sparsity, d is the dimension, tau is the failure probability. The algorithm is based on the popular filtering algorithm and involves an additional truncation step for ensuring the samples satisfy the stability condition. ", "questions": "See above", "limitations": "See above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First of all, I have been asked to review the paper at the last minute. So I didn't have time to read the proofs in the appendix. But, I have gone through the main paper. \n\nThe paper addresses two corruption models simultaneously: malicious adversary model and heavy-tailed model. In addition, the paper tries to do sparse mean estimation. The heavy-tailed part in the paper looks interesting and could be useful to the community (especially given that there is no prior work which can get computationally efficient estimators for this problem). However, it is not immediately clear if the results for malicious adversaries are optimal, and is debatable (see below for more details). The core algorithmic ideas are not novel (except for the truncation step). The main novelty is probably in the analysis of the truncation step. Nonetheless, I believe the pros of the paper marginally outweigh the cons.\n\n$$\\textbf{Theoretical Results}.$$ \n1. $\\epsilon\\  \\textbf{dependence}.$  It is not clear if the derived error bounds have optimal dependence on $\\epsilon$. For bounded $4^{th}$ moment distributions, the optimal rates have $\\epsilon^{3/4}$ dependence [1,3]. I understand that the paper considers a weaker condition than bounded $4^{th}$ moment. But the lower bounds presented in the paper don't clearly show what the optimal dependence should be. The current lower bounds only hold for $k>\\epsilon^{-1/2}.$  For smaller $k$, will the lower bounds still be $\\epsilon^{1/2}$? At least for the hard instance created in the proof, it looks like the lower bounds will be $\\epsilon^{3/4}$ when $k=1$. Given this, it is hard to judge if the rates are optimal in $\\epsilon$ for all $k$. \n2. $4^{th}$ $\\textbf{moment condition}$. The $4^{th}$ moment condition in the paper looks weird. It is not a rotational invariant condition. Let's say I have a distribution which satisfies this condition. Now, I create another distribution by rotating this distribution such that the new distribution doesn't satisfy the moment condition. The algorithm works for the first distribution but not the second distribution. This naturally raises the question if this assumption can be further relaxed or totally removed. It'd be great if the authors try to relax this condition.\n\n$$\\textbf{Other comments}.$$\n1. Some relevant work hasn't been cited [1,2]. The current work is certainly not the first to study sparse mean estimation in heavy-tailed settings with outliers. [1] considers the same problem as the one considered in this work and provides an optimal estimator, albeit they provide a computationally inefficient estimator. These works should cited and discussed in the paper.\n2. At a number of places it is claimed that for robust mean estimation of Gaussian distribution, the error rates will scale as $O(\\sqrt{\\epsilon})$ (for example, Fact 1.2). This is not correct and needs to be fixed. The optimal error rates will scale as $O(\\epsilon)$ [3]. \n3. Why is $||\\cdot||\\_{2,k} $ norm used instead of $||\\cdot||\\_{2}$ norm, if they are both equivalent upto constant factors?\n\n[1] A Robust Univariate Mean Estimator is All You Need. https://proceedings.mlr.press/v108/prasad20a.html \n\n[2] A Unified Approach to Robust Mean Estimation. https://arxiv.org/pdf/1907.00927.pdf\n\n[3] Recent Advances in Algorithmic High-Dimensional Robust Statistics. https://arxiv.org/pdf/1911.05911.pdf\n\n\n-------------------------------------------------------------------------------------------------------------------------------------------\nUpdate after discussion with other reviewers: I believe the heavy tailed results in the paper are useful, especially given that this is the first computationally efficient estimator in this setting. So I'm increasing my score.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept