List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering
Authors: Ilias Diakonikolas
Daniel Kane
Sushrut Karmalkar
Ankit Pensia
Thanasis Pittas
Venue: NeurIPS 2022 Accept (2022)
Keywords: list-decoding
sparse estimation
robust statistics
high-dimensional inference

Abstract: We study the problem of list-decodable sparse mean estimation. Specifically, for a parameter $\alpha \in (0, 1/2)$, we are given $m$ points in $\mathbb{R}^n$, $\lfloor \alpha m \rfloor$ of which are i.i.d. samples from a distribution $D$ with unknown $k$-sparse mean $\mu$. No assumptions are made on the remaining points, which form the majority of the dataset. The goal is to return a small list of candidates containing a vector $\hat \mu$ such that $\|\hat \mu - \mu\|_2$ is small. Prior work had studied the problem of list-decodable mean estimation in the dense setting. In this work, we develop a novel, conceptually simpler technique for list-decodable mean estimation. As the main application of our approach, we provide the first sample and computationally efficient algorithm for list-decodable sparse mean estimation. In particular, for distributions with  ``certifiably bounded'' $t$-th moments in $k$-sparse directions and sufficiently light tails, our algorithm achieves error of $(1/\alpha)^{O(1/t)}$ with sample complexity $m = (k\log(n))^{O(t)}/\alpha$ and running time $\mathrm{poly}(mn^t)$. For the special case of Gaussian inliers, our algorithm achieves the optimal error guarantee $\Theta (\sqrt{\log(1/\alpha)})$ with quasi-polynomial complexity. We complement our upper bounds with nearly-matching statistical query and low-degree polynomial testing lower bounds. 

List-Decodable Sparse Mean Estimation via Differencce-f-Pairs Filtering
Ilias Diakonikolas UW-Madison ilias@cs, wisc. edu
Daniel M. Kane UC, San Diego dakane@cs. uesd. edu
Sushrut Karmalkar UW-Madison skarmalkar@viscc.ok
Ankit Pensia UW-Madison ankitpBcs sassc.edu
Thanasis Pittas
UW-Madison pit pittasSwisc.
Abstract
We study the problem of list-decodable sparse mean estimation. Specifically, for a parameter a E (0, 1/2), we are given m points in R", [amm] of which are i.i.d. samples from distribution D with unknown k-sparse mean μ.. No assumptions are made on the remaining points, which form the majority of the dataset. The goal is to return small list of candidates containing a vector ğ such that A| 2l/2 is small. Prior work had studied the problem of list-dccodable mean estimation in the dense setting. In this work, we develop a novel, conceptually simpler technique for list- decodable mean estimation. As the main application of our approach, we provide the first sample and computationally efficient algorithm for list-decodable sparse mean estimation. In particular, for distributions with "certifiably bounded" 1-th moments in k-sparse directions and sufficiently light tails, our algorithm achieves error of (1/a)0(1/t) with sample complexity m (oo())))) /a and running time (oly(mn)). For the special case of Gaussian inliers, our algorithm achieves the optimal error guarantee e ((vTog(1/ai) with quasi-polynomial complexity. We complement our upper bounds with nearly-matching statistical query and low-degree polynomial testing lower bounds.
Introduction
It is sell-establlshe that when dataset is corrupted by outliers, many commonly-used estimators fail to produce reliable estimates [Tuk600, ABH The field of robust statistics was developed to perform reliable statistical inference in the presence of constant fraction of outliers, even when the data is high- sigh-iimensional [HR09, HRRS86]. Although statistical rates of high-dimensional robust estimation problems are relatively well-understood by now [DL88, Yat85, DG92, HR09, CGR 16), all of the estimators developed in these works were computationally inefficient, with runtime exponential in the dimension. The goal of algorithmic robust statistics, beginning with the works of [DKK+ 16, LRV16], is to design computationally efficient algorithms for high-dimensional robust estimation tasks. We refer the reader the survey [DK19] for introduction this field.
The bulk of the recent progress in algorithmic robust statistics has focused on the setting where the fraction of outliers is a small constant, and the majority of samples are inliers, see, e.g.. [DKK 16, LRV16, KKM18). In contrast, when the fraction of outliers outnumbers the fraction of inliers. is generally cnommation-thhoretiaall impossible to output single estimate with non-vacuous error guarantees. such situations, we allow the algorithm to return small list of candidates such that one of the candidates is close to the true parameter. This list-decodable learning setting was first introduced in [BBV [08) and developed in [CSV17]. We define the model below.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Definition 1.1 Dist-Decodable Learning). Given a parameter 0 < < 1/2 and a distribution family D on R", the algorithm specifies m 2, and observes set of m samples constructed as follows: First, a set S of [am] i.i.d. samples are drawn from an (unknown) distribution D) E 'D. Then, an adversary is allowed to inspect S and choose a multiset E. of m - [ml] points. The multiset T, defined as T == S U E, of m points is given as input to the algorithm. We say that D is the distribution of inliers, the elements in S are inliers, the points in E are outliers, and T is an (1 - -coorrppe dataset S. The goal is to output a "small" list of hypotheses L at least one of which is (with high probability) close to the target parameter of D.
The list-decodable learning setting, interesting in its own right, is closely related to several well- studied problems. A natural example is the problem of parameter recovery from mixture models, e.g.. Gaussian mixtures (see, e.g., [Das99, VW04, AK0S, DS07, KK10, RV 17].. List-decodable mean estimation can serve as a key step in learning mixtures, since one can treat any component of the mixture as the set of inliers (see, e.g., [CSV17, DKS18a, 8a, KS17)). In addition, list-decodable learning can be used to model data important applications where mixture models are not sufficient, such as crowdsourcing (see, e.g., (SVC16, SKI.17, MV18)) and community detection in stochastic block models (c.g.. [CSV17]).
Prior work on list-decodable mean estimation has focused on the unstructured setting, where the target mean is an arbitrary dense vector (see, e.g., [CSV17, KS17, D8SI8a, RY20a, CMY20, DKK20, D DKK MKK++2201 22b]). Sparse models have proven to be useful in wide range of statistical tasks, and thus understanding the statistical and computational aspects of sparse estimation is a fundamental problem (see. e.g.. [EK12, HTW15, 15, van]6]). Here we study list-decodable sparse mean estimation, where the target mean vector is known to be k-sparse, i.e., it has at most non-zero coordinates. Given an (1 - -cccrrpppppeeed set of samples, our goal is to output, in a computationall--eficiieen manner, a small list of vectors containing good approximation fú to the true mean μ (ef. Definition 1.1). Importantly, the goal is to achieve this with far fewer samples than in the dense setting, While the dense setting would require sample size polynomial in n - the ambient dimension of the data- the goal here is to solve the problem in number of samples polynomial in A and only polylogarithmic in n.
In this paper, we present novel and conceptually simple technique for list-decodable mean estima- tion (that is applicable even in the dense setting). Combining our framework with the concentration results from [DKK* + 22a], we obtain the first sample and computationally efficient algorithm for list-decodable sparse mean estimation. We note that, while prior results [KS17, RY20a] can possibly be modified to incorporate the sparsity framework of [DDKK-22]] after sufficient effort, a notable con- tribution of our work is general and conceptually simpler framework for list-decodable estimation, which can easily be adapted to incorporate various structural constraints.
1.1 Related Work
Efficient estimators for high-dimensional robust statistics with sparsity constraints have been recently developed for various problems, such as mean estimation and PCA (see, e-g., [BDLS17, DKK 19, Li17, 222)). The problem of dis-ddeceaalle mean estimation was first introduced in [CSV17]. which achieved an error guarantee of Ó(L/ Va) for distributions with bounded second moment; this guarantee turned out be optimal for this distributional assumption (see [D])) Subsequent work improved the algorithmic guarantees for this problem (see, e.g., [CMY20, DKK20, 21J).
To achieve better error guarantees, it is necessary to make further assumptions the distribution, e.g.. Gaussianity or bounded higher moments. In terms of the minimax optimal rate', [DKS 8a] showed that the optimal error for Gaussians is O @(vlog(11/)) algorithm that achieves the optimal error for Gaussians must take either super-polynonee or samples, and presented an algorithm with matching guarantees. When the distribution D has bounded t-th moment for some even > 2 i.e. E((v, X E[X]>*] is bounded for all unit vectors v), [DKS18a] proved that the minimax optimal rate is @(a-1/1) For distributions with certifiably bounded (-th moments, [KS17, RY20a] provided algorithms obtaining an error rate of (((1/a)0(//)) with sample complexities m = poly(n'/ /at, and runtimes poly(m' (m'n') and poly(mn) (olyym))oolytt.//// (o)), respectively. Recently, in the context of moment estimation and clustering
They also showed that any SQ time
'Infrrmally speaking, we say that the minimax optimal rate is ry if (i) no algorithm (regardless of sample size and runtime) has error o(7) with a list of size independent of dimension n, and (ii) there is an algorithm with error O(7) with list of size independent of n;; in case, poly poly(n/a) samples and O11aa) list size suffice.
2

---

problems, [ST21] showed how to improve the dependence on m in the runtime of algorithms that depend on certifiably bounded moments from poly(m'n')) to poly(mn'). While it is possible that their result might be applied to [KS17, RY20a], our algorithmic technique naturally lends itself to achieve runtime poly (mm') for the dense as well as sparse settings. We provide detailed comparisons with (see, e.g., [DKS18s 8a, KS17, RY20a]) in Section 1.3. Finally, we mention that the list-decodable setting has also been studied in the context of linear regression (see, e.g., [KKK19, RY20a, DKP+ and subspace recovery (see, e.g., [BK21, RY20b]).
In an independent and concurrent work [ZS22], Zeng and Shen also study list- distddeco sparse mean estimation when the underlying distribution is spherical Gaussian.
1.2
Our Results
We demonstrate an algorithm to perform list-decodable sparse mean estimation with (k log n.) m) samples, when the mean μ E IR. known to be k-sparse. For this to be possible, we will require some assumptions on the underlying distribution of inliers D. Prior work in the dense setting ([KS17, RY20a]) assumed that the inlier distribution D in Definition 1.1 satisfies d-certifially bounded f-th moments in every direction (i.e., for some moment bound M > 0, M|llll - Ex~Dl(t, X u)"] can be expressed as a sum of square polynomials of degree at most d = O(t) in the entries of v). and D has light tails. We highlight that our algorithmic technique can also be used in the dense case, under the same assumption, and provides qualitatively similar error guarantees with much simpler arguments and improved runtime. Below we apply our technique to the sparse setting.
Our results hold when (i) the f-th moment of D d-certifiably bounded for every v that is s-spass with d = O(t), and (ii) D has light tails. For ease of exposition, we state the result assuming D has subexponential tails (i.e., for some universal constant c, for all unit vectors u and p E N. EXx_IIKU, X 10) S cp).
Theorem 1.2 Liist-Decodable Sparse Mean Estimation). Let t be an integer power two. Let D be a distribution over Rn'h with k-sparse mean μ.. Suppose that D has t-th moments d- d-certifiably bounded in k-sparse directions by M for some d O(t (cf. Definition 2.3) and subexponential tails in the standard basis directions. There is an algorithm which, given a, M, I, k. and a (1-a)-corrupted set of (tk log n)0(; max(1, M-2)/a samples from D, runs in time poly(mm') and returns vector ja E R such that with probability ((a it is the case that 1| /|l2 O, (UW)))
Note that with high probability over the inliers and for any choice of outliers, with probability 2(a) over the internal randomness of the algorithm, the algorithm of Theorem 1.2 outputs an estimate js close to p. By running our algorithm O(1aa) times, we can generate list of size O(1/a) such that with probability 0.9 the list contains the desired estimate pt
Notably, for the important special case of Gaussian (H, f) inliers, our algorithm achieves the information- coanaaaionnthoortticalll theoretically optimal error rate. This is because N(u, I) has its t-th moment certifiably bounded by /²2 in all directions. Specifically, for a large enough constant C > O, we obtain the following result: Given a, t, and (1 - corruueee set of m (tk log n) samples from N(,, I) for a k-sparse vector 1s, our algorithm runs in time poly(mn') ) and with probability 2())) outputs a vector ğ such that |1 #l12 I O(vi/a Thus, by taking t = C' logg(1 (1)a,, we obtain the optimal error of O( / /log(1//))) in quasi-polynomial sample and time complexity.
We also note that broad and natural class of distributions satisfying Definition 2.3 is the class of a- P-Poincare distributions (see, e.g., [KS17]). A distribution is said to be o-Poincare if for all differentiable functions f R. + IR, we have that Varx-n [S(X)] S a² (x=D[IV\(XX)
We complement our algorithm of Theorem 1.2 with a qualitatively matching lower bound in the Statistical Query (SQ) model [Kea98]. Instead of directly accessing samples, SQ algorithms are only allowed to perform adaptive queries of expectations of bounded functions of the underlying distribution, up to some desired tolerance (c.f. Definition C.I). The class of SQ algorithms is fairly broad: wide range of known algorithmic techniques in machine learning are known to be implementable in the SQ model (see, e.g., [FGR* 13]).
An SQ lower bound is an unconditional statement that for any SQ algorithm, either the number of queries 9 must be large or the tolerance, T, of some query must be small. Since simulating a query of
It suffices for D to have po log(n)) bounded moments in axis-aligned directions; see Section 2.
3

---

tolerance T by averaging i.i.d. samples may need up to (11/7²) many of them, SQ lower bounds are naturally interpreted as a tradeoff between runtime (2(q) and sample complexity (111/²2). An adapta- tion of the result in [DKS18a] yields Theorem 1.3, which indicates that the (O()) factor in the sample complexity of Theorem 1.2 might be necessary for efficient algorithms, even for Gaussian inliers.
Theorem 1.3 (SQ Lower Bound, Informal). Consider the problem of list-decoding the mean of Nu, D), for a k-sparse vector μ E I", up to error better than (ta) -1/t), Any SQ algorithm that solves the problem does one of the following: (i) It returns list of size n ( (ii) it uses at least one query of tolerance k-((()) exp(O(la))221) or (iii) it makes at least n k queries.
Theorem 1.3 states that any SQ algorithm that runs in time less than Th for a constant c > 0 and achieves the minimax-optimal error of v /logg(// (1/a) must use at least (. log log(1/a)) samples. This follows by setting = (l /a) log (og(1/a)), A similar lower bound holds for the computational model of low wwwdegree polynomial tests, as a consequence of the recently established relationship between the two models [BBH 221]. See Appendix C for more details.
1.3 Overview of Techniques
We begin with brief overview of the existing techniques for dense list-decodable mean estimation. We then highlight some of the obstacles in adapting these techniques to the sparse setting. Then, we provide an overview of our algorithmic approach and explain how it overcomes these obstacles.
Prior Work on List-Decodable Mean Estimation In the dense setting, prior algorithmic techniques for list-decoding the mean with error better than (1/21/2 are quite complicated. [DKS I 8a] uses a multifilte-bbseed technique for list-decoding spherical Gaussians, which relies critically on knowing the higher degree moments of the inliers (and thus does not generalize to less specific distribution families). Moreover, this method runs into technical difficulties related to being unable to determine the variance of higher degree polynomials on the inliers without knowing the mean ahead of time. The other approach in the literature (see, for example, [KS17, RY20a]) uses the Sum-of Squares method (SoS) to find these clusters of points. The algorithm in [RY20a) involves solving a nested SoS program and then applying complicated rounding procedure to get the final list. It should be noted that the runtime of [RY20a] is exponential in poly voly(1/a) (1/a). which can be quite large. Finally, [KS17] gave an SoS based list-decodable mean estimation algorithm for the dense case with error, sample complexity, and list size similar to the ones that are obtained in our work; but significantly worse runtime. The approach of [KS17] has some important differences. First, the clustering relaxation is conceptually harder, involving a more complex optimization problem for each filtering step and second, after the filtering ends, the error guarantee scales with the norm of the unknown mean; thus a complicated re-clustering step that combines ideas from [SCV18] is needed to reduce the error.
Here we present significantly cleaner method to perform the outlier removal step; avoid problems like not knowing the mean ahead of time by simply taking pairs of differences of our samples to make their mean zero. While it is likely that either of the prior techniques could be adapted to the sparse setting with sufficient effort, this would result in significantly more complicated algorithms. We briefly point out some difficulties below.
First, to ensure that the algorithms identify subsets of the samples that satisfy certifiably bounded moments in all k-sparse directions, requires additional variables and constraints to the algorithms. Additionally, one would need to replace the bounded moments in all directions condition by the corresponding condition for the sparse case, and ensure that all the proof steps can be modified to rely only on the latter- - this would result in minor modifications of the original algorithms, such as thresholding of candidate solution vectors.
Second, at the end of this process, while the algorithm might qualitatively match the er- ror guarantee that we achieve, the runtime would continue to be (mn)00t) for [KS17] or for [RY20a] - both of these are qualitatively worse than the
(o/looolyo (n (max((1/aa runtime we achieve when is sufficiently small. To obtain improved runtime using these prior techniques, one would require additional ideas, e.g., from [ST21], to be adapted to this setting, overall resulting in far more complicated algorithm.
On the other hand, it seems difficult to adapt the multi-filtering technique from [DKS] 18a] to the setting we consider, without any introduction of an SoS component. We remind the reader that the [DKS 18a]

---

algorithm depends critically on knowing the higher moments of the inliers exactly, and does not generalize less specific distribution families. Even in the Gaussian setting, generalizing [DKS18a] might be difficult, since it would require the design of an efficiently verifiable notion of matching higher moments in k-sparse directions.
We believe that our novel list-decoding technique is significantly simpler. As result of simplifying the optimization programs involved, our technique naturally improves the runtime from poly(m'v) n'' in prior work to poly (mn'²).
Novel List-Decodable Mean Estimation Algorithm All known list-decoding algorithms are based upon the following fundamental observation. Suppose that S is a dataset that contains a subset Sy of samples with bounded moments. If we can find a subset S' of S with bounded moments and large overlap with Sg. then the means of 5" and Sg cannot be too far apart (see Lemma 3.3). The goal of a list-decoiing algorithm is find such subset S" (or, more precisely, a small number of hypotheses for such a subset). In order to generalize this to the sparse mean setting, it suffices for the subsets Sg and S" to have bounded moments only in all k-sparse directions. This will imply that (v, Mg us)) ) is relatively small for all k-sparse unit vectors v, which will in turn imply that truncating u to its k largest entries will provide suitable approximation jig. (see Fact A.2).
The basic idea behind our novel list-decoding technique, which we call the difference of pairs filter, is the following: let T be the set of differences of pairs of elements of S. The set ' will contain relatively large subset, Tg. (consisting of the pairwise differences of elements of Sg)) whose moments in k-sparse directions are bounded. Our goal will be to find subset T c T that has large overlap with 7g and also has bounded (k-sparsee) moments.
Naïvely, we can do this as follows. We start with T moments (in which case we are done) or there is some sparse direction v in which the average value of [t,xx' If over 7" is substantially larger than the average value over Tp. By throwing away points x from T" with probability proportional to <v,x')]' we eliminate mostly bad points. We repeat this until T' has bounded sparse moments. Unfortunately, while this approach can be shown to be correct, it does not suffice for our purposes because it is computationally infeasible in general to determine whether not T' has bounded sparse moments. However, if we assume additionally that Sg has bounded k-sparse moments provable by a low-degree sum-of-square proof (i.e., the moment bound inequality can be re-expressed 0), then so will Tg. There is an efficient algorithm to determine whether or not T has certifiably bounded moments in k-sparse directions as well. If T' does not have certifiably bounded moments, standard techniques for -funoof-Suuarss programs imply that we can manufacture a non-negative polynomial p so that the average value of p on 1" is substantially larger than the value of p on any set with SoS-certifiabbl bounded moments in k-sparse directions. Thus, filtering out points x in T" with probability proportional to p(x) will likely remove mostly bad points. Using this idea, we can find such a set T" efficiently (see Theorem 3.1).
= T. Either this set has bounded k-sparse
sum of square polynomials being greater than
We are thus left with set of differences of samples rather than set of samples. At this point, we will need a rounding method that given a set T" of differences with bounded k-sparse moments guaranteed to have large overlap with Tg. finds small list of sets S' with bounded k-sparse moments so that at least one of them has large overlap with Sg- Note that T' might be the union of T; - T, where each T; is an individual cluster drawn from a moment- -ouundd distribution. This demonstrates the necessity of a rounding step to identify the means of individual clusters. To achieve this, it is helpful to think of T' consisting of set of pairs of elements of S. or equivalently as graph over S. Given T", our first task is to find some reasonably large subset of S with bounded moments (ideally which has large overlap with Sg). It is not hard to see that it suffices to find any large clique in T" (see Lemma 3.3). Unfortunately, '"' may well not have any large cliques, and even if it does, finding them may be computationally difficult. However, we are saved here by the observation that if Ku, - y)1' and (v. y - l are both small, then so is (e, graph H of all pairs of vertices (v. w), where v and w have many common neighbors in T", this new graph will also have relatively small k-sparse moments (see Lemma 3.5). As most elements of S, are adjacent in T' to most other elements of Sg, it is not hard to see that this new graph will have relatively large cliques; unfortunately, finding them may still be computationally difficult.
2)1'. This means that if we replace 7" by the
To find these large cliques efficiently. we need one final observation. If u is a random vertex of a graph G, then there will (on average) be very few pairs of neighbors. u and w, of u so that u and w do not have large number of common neighbors with each other in G (see Lemma 3.6). This means
5

---

that if we pick random sample z in S, then most pairs of neighbors of z in T' are neighbors in H. Using densification procedure (see Lemma 3.7). it is not hard to find a large subset S' of these neighbors so that any two elements of 5' have many neighbors in common in G. By Lemma 3.5, this implies that S' will in fact have bounded k-sparse moments. Furthermore, if we happened to pick from Sg. it is not hard to see that it is likely that S' has large overlap with Sg. and thus its mean provides us with a good estimate.
While the above describes our algorithmic approach, we also need to consider the sample complexity of our method. We know that the distribution D has the property of bounded moments in k-sparse directions, and our algorithm requires that the property is also satisfied by the uniform distribution over the samples Sg. order for Sg to have it as well, it suffices that the tth moment tensor of S. l be close to the corresponding moment tensor of D μ. It turns out that if these moment tensors are ōk --cloe coordinate-wee wise, which takes O(t log(n))kO(t) /8²) samples, this suffices to get the kind of certifiable concentration we require, This captured by Lemma 2.4, restatement from [DKK* 22a].
2 Preliminaries
Basic Notation. We use Z4 to denote positive integers. For n E 24 we denote [m] := (1.......) We denote by 1[21,- ..... Id]sd the set of real-valued polynomials of degree most dl in variables UI....,,2 We use (-) to indicate a quantity that is polynomial in its arguments. For an ordered set of variables Q = {xI,... ...,, In we will denote p(Q) to mean p(zi,.... ...,,...... .nn. .......,,,n.... We use L, to denote the n X n identity matrix. For a vector v, we let ||0|||2 denote its fn-norm. We call a vector k-sparse it has at most & capital letters for random variables and El.] for expectation. When S is a set, we will use the notation X ~ S mean that X is distributed uniformly over S. For a graph G we denote by (xr the neighborhood of x in G. Throughout the paper, we will use the letter n for the dimension, m for the number of samples, for the degrees of the SoS proofs, and & for the number of bounded moments.
coordinates. We use (v, u)) for the inner product of the vectors u, V. We use
SoS Preliminaries The following preliminaries are specific to the SoS part of this paper. We refer to [BS16, FKP19] for more complete treatment of the SoS framework. Here, we review the basics.
Definition 2.1 (SoS Proof). Let æ1,.... Tn be indeterminates and let A be a set of polynomial
equalities {pi (x) = O,..., Pm (x) = 0}. An SoS proof of the inequality r(x) 2 0 from axioms A is a set of polynomials (r)))/mmmm] U {ro(z)} such that ro is a sum of square polynomial and ry's 's are arbitrary, and r(x) = ro())) + Eie(m) re(x))p((x). If the set of polynomials (ra(x)) pe(xr) i E [d] U {ro(z)} have degree at most d, we say that this proof is of degree d and denote it by A 7 r(x) 2 O. When we need to emphasize what indeterminates are involved in particular SoS
proef, we denote it by A Ala r(z)= 2 0. When A is empty, we omit it, e.g., la r(x) 2 =Oorlz la r(x) 2 O.
We will also use the objects called pseudoexpectations.
Definition 2.2 (Pseudoexpectation)) Let II,..., IIn be indeterminates. A degree-d pseudoexppetattion
pelyyeeedddllyy É is a linear map É. IR(,,,..., 2nn.....,,],,, La] + R. from degree-d polynomials to R such that È [p(x)²] 2 0 for any p of degree at most d/2 and [1] of polynomial inequalities, we say that a pseudoexpecttation E satisfies A if for every i E [m].
1. If A {pi(z) = -..... ........m..6 (2) 0} is set
Els [[)())p(())] for all polynomials s(x) such that s(x)p;(1:) has degree at most d.
is well known (see, e.g., [BS16]) that pseudoexpectations are dual objects to SoS proofs in the following sense: given set P of polynomial equalities in n variables and polynomial q(I1,..., either there exists an SoS proof P _ q(x) 2 0 or there exists a pseudoexpectation E of degree satisfying P but having E E[g(=)] < O. More importantly, there is an algorithm that runs in time ((e) and finds that pseudoexpectation when we are in the second case. Due to lack of space, we defer formal statements and brief overview of SoS to Appendix A.
Certifiably Bounded Moments in k-sparse Directions Our algorithm succeeds whenever the uncor- rupted samples have cerlifiably bounded moments in k-sparse directions, defined as in [DKK + 22a]:
Definition 2.3 (M,,, d) Certifiably Bounded Moments in k-sparse Directions). Let Q = {2] 2i)ee()) Uf44 = viteen U W 4 = k) U
{Ui.... Uns .... En } and Ak-sparse
6

---

[E=="²=-1 For an M > 0 and even t E N. a distribution D with mean μ satisfies (M, t, d)
certifiably bounded moments in k-sparse directions if Ak-sparse 1 d Ex-D [( n3) s M
The definition of Als-sarse based on the fact that a vector v = " Un) is k-sparse if and only there exists = (21..... 2n) such that v, satisfy Au-sparee
We will use the following lemma proved in [DKK 22a] to bound the number of samples it takes to certify bounded moments in k-sparse directions. Although this is stated for subexponential distributions, it needs the distribution to have only bounded e² log(d) moments (see Lemma A.10).
Lemma 2.4 (IDKK 22al). Let D be distribution over R" with mean μ.. Suppose that D has sub- exponeenet tails around for constant e and that Aje-sarse To(t) Ex~D [(, 22) S M Let (X1..... .........)) be a set of m i..dd samples from D, D' be the uniform distribution over S. and şí == Ex~D-(X] If m > C(tk(logn)) n))²r max(1,M M for a sufficiently large constant C, then with probability at least 0.9 we have the following: (i) Ak-spare To(e) EX-D Ku, - =T)1? < 8M² and (ii) (v, To 1---p u.) S M2 / /a for every k-sparse unit vector e.
Main Result: Proof of Theorem 1.2
Fm Recall our setting: we are given E 10.1/2) and multiset S == ( such that an unknown subset of [am] many of these points satisfy (M, t, d) certifiably bounded central moments in k-sparse directions, and the remaining are arbitrary. The goal is to recover candidate that is close to := Ex=n[X] with probability 2(a). In what follows, / will always be 2 for some & E Z,.
3.1
The SoS-based Filter
Let T be the set of pairwise differences of all samples in S (similarly denote by Tg the subset of corresponding to inliers Sg). We would like to either detect that the moments of T are already bounded in all k-sparse directions or find direction that violates this and filter out mostly outliers. Unfortunately, this kind of check computationally infeasible, but can be done efficiently if we check for moment bounds that are certified by SoS proofs. This is done in Algorithm 1, which takes as input the set along with the parameters I, d, M and performs filtering until the resulting set 7 has (M, d) bounded moments.
Algorithm 1 SoS- filter for list-decodable mean estimation
1: function LDMEAN-SON SOO-AA--SS--F--E-RTT := {I1, [Fi..... Fm Jt,, M) FILTER(T 2: Let Q = (U1,.... Un, .1...., } and T = T.
3: while there is no SoS proof of Ak-sparse Ld Exer (v, x/ s (M do
4: Find a degree-d E on Q satisfying An-spanse and El > 6M/T).
5: Throw out x T' with probability É [(v, x maxzer E [1,
6: end while
7: return T'
8:
end function
Theorem 3.1 (Filter Identifies a Subset Satisfying Bounded Moments). Let T be a multiset of points in Th for which there exists subset Ty T with (Tgl a a² for some >> O. Furthermore assume that Tg has zero mean and (M, 1, d.--ertiiiyy bounded moments in k-sparse directions for some M 0, E4, and even t. Then Algorithm 1, given T, M, t, d, returns subset T" T in time poly (mm" so that, with probability at least 2/3, the following holds: (i) For any k-sparse unit vector v, we have that Exer (v, < (T)))) and (ūi) [T" n Tg. [22/22.
{21, 121..... Zas U1 ... ). In Algorithm 1, Lines 3 and 4 use the separation oracle of Theorem A.4 with P = Ap-eee Since Tg has zero mean and (M, f, d) bounded central moments in k-sparse directions, we have that
Proof. Let Q
1 As-sparse M E X
[(u,X)9 2 0.
(I)
7

---

Thus, if sparse 2 Exer((e, (r, I 6M the algorithm identifies that and stops (in which case
we have the desired conclusion that for any k-sparse vector v. Emer {v, x) 2 6M otherwise finds a degree-d pseudo-expectation E on Q satisfying Ak sparse and E - -6M [T| + Exer (v, > O, in which case we can create filter: Using Equation (1) and [Tg] a² [T), we have that M 2
Ex-T, (((,, N TIT EMET,NT E [(v, Since É [-6M[]]] + Ener (v, 0 and
E is linear, we see that Everor B [vaa)"]
Enery E ((,a) S 2/6 This means if we throw out sample with probability [U, / max,er E [(u,, x) (which is indeed in [0, 1] since (v, x)* is SoS, so its pseudoexpectation is non-negative value), on average, only an a /6 fraction of the points that are removed will be from Tg. Since the with the largest value of É [v,, algorithm will terminate in polynomial time. We now analyze the size of [T" n Tgl- By the above analysis, at each step the expected number of samples thrown out from Tg is at most a2/6 times the expected total number of samples removed. Thus, the potential function A = ((Tg n T' is submartingale. Note that always 0 S A/a² I 1, and initially we had A/a² 5/6. By Doob's 's martingale inequality (Proposition A.9 applied with t = 1/2 to the submartingale (A/a²)), )) the probability that A/a² remains at least a² throughout the execution of the algorithm
will be removed, the
(a² (T)
is at least 2/3. Thus, we will have (Tg n n 2 (a² (2) T = lTgl/2 throughout the execution.
3.2 Identifying a Subset of Samples with Bounded Moments
Having identified a subset T T satisfying the conclusions of Theorem 3.1, we want to extract from T' a vector that is close to the original mean. Since the average of the set of differences is likely to be close to zero regardless of the true mean, we will need to use the information about the pairs that we get from 7" to find subsets of the original samples that satisfy the appropriate concentration bounds. We will need the following definition.
Definition 3.2. Let S C R.. A graph (V, E) on S with V = S is said to have (M,1)- bounded moments in k-sparse directions if for all k-sparse unit vectors v, (1/1512) ((.))E) (v, y)* S M.
By the guarantee of our filter, if T' is the set returned, the graph G with edges (æ,, v) for which x or y - x belongs to T' will have bounded moments in the above sense. If G contains a clique C which intersects with an a- c-fraction of the target samples Cg. the means of C and Cg are close.
Lemma 3.3. Let S c. R and G be a graph on S satisfying Definition 3.2. Let C c S be a clique in G. Let Cg C. C be a subset with [Cg] 2 alS). If pe and Pa denote the means of C and Cg respectively, then (U. - pay² < 2M 2a² for all k-sparse unit vectors v.
Proof. By using the fact that is even and the fact that G satisfies Definition 3.2, we see that MiS Eiewe x -xy' 2 1 Ex.eec -y) 2 EoE (v, .uing Jensen's inequality we obtain, MIS Evec,vec (v,2- > |G,1CC C (v. ma)", > (
Unfortunately, even the inliers might not form a clique in G. However, the guarantee that (T' NTy > l/2l/2 2 implies that the inliers share many neighbors in the graph G. Thus we look at the overlap graph defined below, in the hope that this graph will be more dense.
Definition 3.4 (Overlap Graph). Let G = (V, E) be a graph and q > O. The overlap graph (G) is defined to be the graph with the vertex set V where each (I., y) is an edge in the graph iff [Na(x) n No(v) 2 V.V, where No(x) denotes the neighborhood of the vertex x in G.
The following result shows that if G has bounded moments, then so does (G). While this is not sufficient by itself, we will subsequently modify (G) to ensure that we end up with graph having bounded moments, as well as an identifiable clique.
Lemma 3.5 (If G has bounded moments, then (G) has bounded moments). Let S be set of points and G be a graph with (M, ty-bounded moments in k-sparse directions. Then for 7 > (G) has (2. 2 M M/r,3 -bounddd moments in k- k-sparse directions.
8

---

Proof. For any 2. y in (G),, the triangle inequality implies (u, (z-aj a) - (a (a-3))² - 2 a)' + (u.y a)"). By taking sum over all in Na(x)) n (y)) we have
(v, (z - a) (a y))* S (21/>11))
(0,--9)- E
Σ
10,0 a) + y a}a
[Na())
Oe aENa(w)nNNo())
aENa(2)nNe(v))
Denote [(aa = {v : neighbor of z in R (G) and neighbor of a in G}. Summing over all the edges (zz, /) in (G), and since is even and G has (M,t) bounded moments in k-sparse directions,
we see: LeeyEER (G) (v, x -- y)²
S 75 Σ (uyyER (G) EneNece)NNetyl x-a)² + + a))
2'
Σ (ax)EE Ever(, (0, a)* S|S|
2-2
2-2'-191 7/S]
Ela,yer(u, x)² 2
7
While (G) may not have any cliques either, it is guaranteed to have fairly dense subgraphs. We will subsequently prune out points so that the resulting final graph will have clique.
Lemma 3.6 (G)(G) has dense subgraphs). Lei G = (V, E) be graph and n > O. x is a randomly selected vertex of G, then the expected number of pairs y, = E No(x)) so that y and z are not neighbors in (G) is at most /
Proof. The expectation in question is 1/[V] times the number of triples N. 2 E V so that and are not neighbors in R. (G), but are both neighbors of G. By the definition (G), if y and are not neighbors in R. (G), they have at most 7/ V common neighbors in G. Thus, the number of such triples is at most 7 V so the expectation in question at most 7/V|2.
As outlined above, the inliers in R. (G) form a dense subgraph. The next procedure (Pruning in Algorithm 2) prunes out points from dense subgraph (inliers in R, (G) for us) to find clique.
Algorithm 2 Algorithms for clique creation and rounding
1: function PRUNING(G = (V, E), W C V)
2: Let W W
3: while 3x E W' that is not connected to at least | 1/3 vertices in W Remove x from W
4: return W
5: end function
6: function ROUNDING(S, G E))
7: Let d = a2/4608.
8: Choose x É S uniformly at random, let W No(x), and let G' = Rs(G)
9: if the number of pairs of points in W that are not connected in G" is more than (85/a)]V|2
or if [W[ < [a] return FAIL
10: else Run PRUNING on G' and W to obtain W
return Ex=w[[X]
12:
end function
Lemma 3.7 (Dense subgraphs can be pruned to obtain clique). Les G (V, be graph and let W C V be a set of vertices with W|= V and all but 7 V pairs of vertices in W are connected in G. for 8,7 >> 0 with γ S 1/////3/ /36. There exists an algorithm (PRUNING in Algorithm 2) that given
G. W, 3,y runs in polynomial time and returns a W C W so that [W'| > [ (6v/B)|V and so
that [W'| is a clique Re)
Proof. In Line 3 of the Algorithm, the point which is removed satisfies [No(x) n W < 2/ If we also have that [W' 2 5/W1// (something that we will verify later), the removal of æ decreases the number of pairs of unconnected elements in W by I (Na(t) n n'I |W'|- (2/3) > | = (V This can happen at most (6>/3) times before we run out of unconnected pairs of elements in W" thus [W'| Z [W| - (67/3)V upon termination. Also, since it holds (6r/B)]V| < (8/6) V = /, we indeed have [W' 2 5 W1/6 as claimed at the start. Now note that each element of W is connected at least 2|W|/3 other elements of W in G. Thus any pair of elements of W' have at least |W//3 common neighbors, and thus are adjacent in Reys(G).
O
We are finally ready to prove our main algorithmic result on rounding. The basic idea is that most of the inliers in G (which are at least a- erfrrction of vertices) are connected to many other inlicrs, and

---

thus if we start with an inlier, its neighborhood will also contain many inliers and will be dense in the overlap graph G' (Lemma 3.6). Thus, we can apply the pruning of Lemma 3.7 to obtain a large clique in the overlap graph of G", which also has bounded moments by two applications of Lemma 3.5.
Theorem 3.8 (Rounding). Let S C R" and let G (V, be graph with V = S and (M, t) bounded moments in k-sparse directions. Suppose there is a subset Sy C S with |S 2 a and at least half of the pairs of points in Sg are connected by an edge in G. Suppose that the Se has mean ug and I-th moment bounded by M in k sparse directions. Then, there exists a randomized algorithm that given G, S and a runs in polynomial time and returns a RR" such that with probabilit Ma)) for all k-sparse unit vectors v, (0, J4 pgg = O(10' Ma-
Proof. The algorithm we consider is ROUNDING (Algorithm 2). Let and G' be as in Line 8. We will claim that algorithm ROUNDING succeeds as long as the following hold: (i) x E Sg. (ii) x has at least S /4 neighbors in Sg in G", and (iii) the number of pairs of neighbors of x that are not neighbors in G' is at most (85/ (0//a)] |V)2 First, we show that these conditions hold with probability M2(a). The first condition holds with probability at least a over the choice of x. Conditioned on x E Sp. the expected number of non-neighbors that x has in Sg. is at most /g./2. Thus, the probability that it has more than 3 /4 non-neighbors is at most 2/3 by Markov's s inequality. Thus, the first two conditions both hold with probability at least 0//3. Finally. the expected number of pairs of neighbors of x that are non-neigh non-neighbors in G' is at most / by Lemma 3.6. Thus, by Markov's 's inequality, there will be more than (85/a)]VVP such connecend neighbors with probability at most a/8. Combining with the above, all three conditions hold with probability at least a/24.
Given these assumptions, we note that [ 2 | 4 2 (o/4)]V), and at most in W are not connected in G This implies that we pass the condition in Line 9. We will now verify the conditions in Lemma 3.7. Since 3 := [W] / 2 a/4 and y, the number of pairs of vertices in W that are not connected in G', is at most 86 66/a- = a² /576, we have y S /2/36, satisfying the assumptions of Lemma 3.7. Thus the returned W" is clique in Rgys(G") and satisfies
of pairs
| - |W'| < (6>/B)]V) <
S (a/24)/VV/-
This means that [W' Sgl > |5.1/4- (a [ 2 |Sgl/6. On the other hand, we know that G has (M,t) t) bounded moments in k-sparse directions. Lemma 3.5 implies that G' has moments bounded by D(20MM/0/)))
Applying the lemma once more implies that Raya(G" has moments bounded by
044 M/4M2 B)) = O(4'M/a)) Since W is a clique in R3/3(G") (G)), we have by Lemma 3.3 that if is the sample mean of Sg 0 W', then
(u - ji)* < 0(4 Ma for all k-sparse unit vectors V.
(2)
Since |Sg nw'
|66 and the Sy has bounded t-th moment along k-sparse directions, we have that
(v, 1 - ) 3 O(M) (see Lemma B.I for a proof of this fact). Combining this with Equation (2)
using triangle inequality completes the proof.
3.3 Proof Sketch of Theorem 1.2
We sketch the proof here, deferring the full proof to Appendix B.I. Let S be the (1 (1-a --oorupte set of samples, and Sg be the inliers. Let T = fo y y. E S) and Tg be its part due to inliers. To every subset 7' of T, we can associate graph GT", having vertices S and edges between the pairs included in T'. Because of Lemma 2.4, Tg has certifiably bounded moments in k-sparse directions. By Theorem 3.1, the filtering step will return subset T" c T that has sizable overlap with Tg and its graph GT has bounded moments in k-sparse directions. Finally, By Theorem 3.1, the rounding algorithm will return á that is close to i in all k-sparse directions. This f can be truncated to yield a vector close to y in the standard Ey-norm (Fact A.2).
Acknowledgments
ID was supported by NSF Medium Award CCF-2107079, NSF Award CCF- (CAREER). a Sloan Research Fellowship, and a DARPA Learning with Less Labels (LwLL) grant. DK was supported by NSF Medium Award CCF-2107547, NSF Award CCF-1553288 (CAREER), Sloan Research Fellowship, and a grant from CasperLabs. SK was supported by NSF under Grant #2127309 to the Computing Research Association for the CIFellows 2021 Project. AP was supported by NSF grants NSF Award CCF-1652862 (CAREER), DMS- 1749857, and CCF-1841199 TP was supported (CAREER) and NSF Medium Award CCF-2107079.
by NSF Award
10

---

References
[ABH*72] D. F. Andrews, P. Bickel, R. Hampel, P. Huber, W. H. Rogers, and J. W. Tukey. Robust Estimates of Location: Survey and Advances. Princeton University Press, Princeton, NJ, USA, 1972.
[AK05] S. Arora and R. Kannan. Learning mixtures of separated nonspherical gaussians. The Annals of Applied Probability, 15(1A):69 2005.
[BBH+21] M. Brennan, G. Bresler, S. Hopkins, J. Li, and T. Schramm. Statistical query algorithms and low degree tests are almost equivalent. In Conference on Learning Theory, 2021.
[BBV08] M. F. Balcan, A. Blum, and S. Vempala. A discriminative framework for clustering via similarity functions. STOC, pages 671 671-680, 2008
[BDLS17] S. Balakrishnan, S. S. Du, J. Li, and A. Singh. Computationally efficient robust sparse estimation high dimensions. In Proc. 30th Annual Conference on Learning Theory, 2017.
[BK21] A. Bakshi and Kothari. List-decodable subspace recovery: Dimension independent еπror in polynomial time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1279-1297. SIAM, 2021.
[Bom98] I. M. Bomze. On standard quadratic optimization problems. Journal of Global Optimization, 13(4), 1998.
[BS16] B. Barak and D. Steurer. Proofs, beliefs, and algorithms through the lens of sum-of- squares. 1, 2016.
[CGR16] M. Chen, C. Gao, and Z. Ren. A general decision theory for Huber's SlepsilonS- contamination model. Electronic Journal of Statistics, 10(2):35223377,, 2016.
[CMY20] Cherapanamjeri, Mohanty, and M. Yau. List decodable mean estimation nearly linear time. In 2020 IEEE 61 Annual Symposium Foundations of Computer Science (FOCS), pages 141-148. IEEE, 2020.
[CSV17] M. Charikar, J. Steinhardt, and G. Valiant. Learning from untrusted data. In Proc. 49th Annual ACM Symposium on Theory of Computing, pages 47-60, 2017.
[Das99] S. Dasgupta. Learning mixtures of Gaussians. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages
1999.
[DG92] D. L. Donoho and M. Gasko. Breakdown properties of location estimates based on halfspacce depth and projected outlyingness. Ann. Starist., 10(4):1803-18)) 1992.
19] I. Diakonikolas and D. M. Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv: 1ee::9911000000 1.05911, 2019.
[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), pages 655-664, 2016.
[DKK + 19] I. Diakonikolas, S. Karmalkar, D. M. Kane, E. Price, and A. Stewart. Outlier-robust high-dimensional sparse estimation via iterative filtering. In Advances in Neural Information Processing Systems 33, NeurIPS 2019, 2019.
[DKK20] I. Diakonikolas, D. M. Kane, and D. Kongsgaard. List-decodable mean estimation via iterative multi-filtering. Advances in Neural Information Processing Systems, 33:9312-9325, 2020.
[DKK+21] I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. List-decodable mean estimation in nearly-pea time. Advances in Neural Information Processing Systems, 34, 1021.
11

---

[DKK 22a] I. Diakonikolas, D. M. Kane, S. Karmalkar, A. Pensia, and T. Pittas, Robust sparse mean estimation via sum of squares. 35th Anmual Conference on Learning Theory (COLT), 2022.
[DKK I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. Clustering mixture models in almost-lines time via list-decodable mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 1262-1275 2022.
[DKP*21] I. Diakonikolas, D. M. Kane, A. Pensia, T. Pittas, and A. Stewart. Statistical query lower bounds for list-decodable linear regression. Advances in Neural Information Processing Systems, 34, 2021.
[DKS17] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high- diteemmmiiinnll Gaussians and Gaussian mixtures. In Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 73-84, 2017.
[DKS18a] I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory Computing, STOC 2018, pages 1047-1060, 2018. Full version available at
[DKS 18b] I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1047-1060, 2018.
[DKS18c] I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical Gaussians. Proc. 50th Annual ACM Symposium on Theory of Computing (STOC), pages 1047-1060, 2018.
[DL88] D. L. Donoho and R. C. Liu. The "Automatic" Robustness of Minimum Distance Functionals. The Annals of Statistics, 16(2):552-586, 1988.
[DS07] S. Dasgupta and L. J. Schulman. A probabilistic analysis of em for mixtures of separated, spherical gaussians. Journal of Machine Learning Research, 8:203-226. 2007.
[ЕК12] Y. C. Eldar and G. Kutyniok. Compressed sensing: theory and applications. Cambridge university press, 2012.
[FGR+13] 13] Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and lower bound for detecting planted cliques. In Proceedings of STOC' 13, pages 655-664, 2013, Full version in Journal of the ACM, 2017.
[FKP19] N. Fleming, P. Kothari, and Pitassi. Semialgebraic proofs and efficient algorithm design. Foundations and Trends@ in Theoretical Computer Science, 14(1-2):1-22) 2019.
[GLS8I] M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981.
[Hop18] B. Hopkins. Clustering and sum of squares proofs: Six blog posts on unsupervised learning. 2018.
[HR09] P. J. Huber and E. M. Ronchetti. Robust statistics. Wiley New York, 2009.
[HRRS86] F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust statistics. The approach based on influence functions. Wiley New York, 1986.
[HTW15] T. Hastie, R. Tibshirani, and M. Wainwright. Statistical Learning with Sparsity: The Lasso and Generalizations. Chapman & Hall/CRC, 2015.
[Kea98] M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, -836) 1998.
12

---

[KK10] A. Kumar and R. Kannan. Clustering with spectral norm and the k-means algorithm. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 299-308. IEFE, 2010.
[9K S. Karmalkar, A. Klivans, and P. Kothari. List-decodable linear regression. In Advances in Neural Information Processing Systems, pages 1423-7432, 2019.
[KKMI8] A. Klivans, P. Kothari, and R. Meka. Efficient algorithms for outlier-robust regression. In Proc. 31st Annual Conference on Learning Theory (COLT), pages 1420-1430, 2018.
[KS17] P. K. Kothari and J. Steinhardt. Better agnostic clustering via relaxed tensor norms. CoRR, abs/171 .07465, 2017.
[Las01] J. B. Lasserre. New positive semidefinite relaxations for nonconvex quadratic programs. Advances in Convex Analysis and Global Optimization, pages 319-331. Springer, 2001.
[Li17] J. Li. Robust sparse estimation tasks in high dimensions. CoRR, abs/1 702.05860. 2017.
[LRV16] K. A. Lai, A. Rao, and S. Vempala. Agnostic estimation of mean and covariance. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS), pages 665-674, 2016.
[MV18] M. Meister and G. Valiant. A data prism: Semi-verified learning in the small-alpha regime. In Conference On Learning Theory, COLT 2018, pages 1530-1546, 2018.
[Nes00] Y. Nesterov. Squared functional systems and optimization problems. In High perfor- mance optimization, pages 405-440. Springer, 2000.
[RV17] O. Regev and A. Vijayaraghavan. On learning mixtures of well-separated gaussians. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 85-96. IEEE, 2017.
[RY20a] P. Raghavendra and M. Yau. List decodable learning via sum of squares. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 161- 180. SIAM, 2020.
[RY20b] P. Raghavendra and M. Yau. List decodable subspace recovery. Conference on Learning Theory, COLT 2020, volume 125 of Proceedings of Machine Learning Research, pages 3206-3226. PMLR, 2020.
[SCV18] [8] J. Steinhardt, M. Charikar, and G. Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. In Proc. 9th Innovations in Theoretical Computer Science Conference (ITCS), pages 45:1-45:21, 2018.
[Sho87] N.Z. Shor. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 1987.
[SKL17] J. Steinhardt, Wei Koh, and S. Liang. Certified defenses for data poisoning attacks. In Advances in Neural Information Processing Systems 30, pages 3520-3532 3502,,33,200 2017.
[ST21] D. Steurer and S. Tiegel. Sos degree reduction with applications to clustering and robust moment estimation. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
SIAM, 2021.
[SVC16] J. Steinhardt, G. Valiant, and M. Charikar. Avoiding imposters and delinquents: Adver- sarial crowdsourcing and peer prediction. Advances in Neural Information Processing Systems, 29, 2016.
[Tuk60] J. W. Tukey. survey of sampling from contaminated distributions. Contributions to probability and statistics, 2:448-45 485, 1960.
[van16] S. van Geer. Estimation and Testing Under Sparsity. Number 2159 in École d'é de Probabilités de Saint-Flour. Springer, 1st ed. 2016 edition, 2016.
13

---

[VW04] S. Vempala and G. Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841-88) 2004.
[Yat85] G. Yatracos. Rates of convergence minimum distance estimators and Kol- mogorov's entropy, Annals of Statistics, 13:768-774, 1985.
[ZS22] Shiwei Zeng and Jie Shen. List-decodable sparse mean estimation, 2022.
Checklist
1. 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 experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as 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 are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work 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]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 'rere using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "hcRJ9587Zz", "reviewer": "Reviewer_Ymm8", "summary": "The field of algorithmic robust statistics is concerned with the development of efficient algorithms for statistical estimation problems in settings where the observed data is extremely (often adversarially) noisy. 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 settings usually considered in this domain, one assumes that the algorithm observes $n$ data points generated in the following manner:\n\n1. First $\\alpha n$ ``good'' data points are generated from the true underlying distribution $D$.\n2. An adversary then inspects the generated samples and adds an arbitrary set of $(1 - \\alpha) n$ points to the dataset. Note that the algorithm is given no knowledge of where the corrupted data points are. \n\nRestricting to the specific problem of mean estimation in high dimensions where the data set $X = \\left\\\\{x_i\\right\\\\}_{i = 1}^n \\subset \\mathbb{R}^d$, the goal is to recover the mean of the distribution $D$ generating the good data points. This task is made complicated by the fact that the algorithm does not actually know which points these are and natural approaches such as distance based thresholding yield sub-optimal results. In the standard setting when $\\alpha \\in (1/2, 1]$, approximate identification of $\\mu$ is possible with error (in Euclidean norm) ranging between $\\sqrt{1 - \\alpha}$ to $\\alpha$ and computationally and statistically efficient estimators have been designed. In the more challenging list decoding setting when $\\alpha < 1/2$, even approximate identification is not possible and one instead returns a list of $1 / \\alpha$ estimates one of which is guaranteed to be close to $\\mu$. Note that a list of this size is necessary by considering the special case where the data is generated from a mixture of $1 / \\alpha$ well behaved distributions. Efficient estimators have also been proposed in this setting with the guarantee that at least one of the elements in the list is close to $\\mu$. The degree of closeness ranges between $1 / \\sqrt{\\alpha}$ when only second moment assumptions are placed on $D$ with improvements possible when stronger restrictions are placed on the distribution. Typically, these involve higher order moments of the distribution and the recovery error correspondingly improves to $(1 / \\alpha)^{O (1 / t)}$ if $t$ moments are available. \n\nThis paper considers the list decodable setting in the sparse regime where $\\mu$ is assumed to be $k$-sparse and $D$ is a distribution centered at $\\mu$. In line with prior work on sparse estimation, the goal of the paper is to build an estimator whose sample complexity depends very mildly on the ambient dimension. All prior work incur sample complexity at least $d / \\alpha$ which while optimal under no additional assumptions may be prohibitive when the ambient dimension is too large. The paper constructs a polynomial-time estimator which achieves sample complexity $\\mathrm{poly} (k \\log d)^{O(t)} / \\alpha$ achieving recovery error of $(1 / \\alpha)^{O(1 / t)}$ which is essentially optimal up to constants in the exponent when the distribution has $t$ certifiably good moments in sparse directions. Furthermore, the paper proposes a novel conceptually simpler approach to list-decodable estimation which avoids the more intricate filtering techniques used in prior work. \n\nIn the ``multi-filter'' framework for building estimators in the list decodable setting, one starts with a candidate set of good data points and infers one of the following:\n\n- The dataset is well behaved (in terms of its moments) and the empirical mean is a good estimate\n- Alternatively, the dataset is poorly behaved but a certificate of this fact (usually a direction along which moments are not well concentrated) can be used to refine (remove bad points from) the dataset. One then constructs a set of subsets of the original dataset which are better behaved.\n\nAt the conclusion of this process, the empirical means of all the refined datasets are returned as candidates in the returned list. Carrying out this approach requires careful design of the filtering and pruning mechanisms to avoid exponential growth in the number and sizes of subsets obtained in the leaves. The intricacies of this approach make reasoning and analysis of these algorithms difficult motivating simpler alternatives. \n\nIn the paper, the authors propose a novel approach where the start by constructing the difference of all pairs of of points in $X$ to construct a new $n^2$ sized dataset $T$. Crucially, all points $y = x_i - x_j$ when both $x_i$ and $x_j$ are drawn from $D$ have zero mean and have well-behaved moments around $0$. Furthermore, these points comprise a substantial $\\alpha^2$ fraction of the dataset $T$. The authors then devise a one dimensional filter that given searches for points significantly increasing the sparse-directional moments of the set of datapoints $T$. Formally, one searches for a solution to the following set of polynomial constraints:\n\\begin{equation*}\n    \\\\left\\\\{z_i^2 = z_i\\\\right\\\\}\\_{i \\\\in [d]} \\\\cup \\\\left\\\\{v_i z_i = v_i\\\\right\\\\}\\_{i \\\\in [d]} \\cup \\\\left\\\\{\\sum_{i \\in [d]} z_i = k\\\\right\\\\} \\cup \\\\left\\\\{\\sum_{i \\in [d]} v_i^2 = 1\\\\right\\\\} \\cup \\\\left\\\\{\\sum_{x \\in T} \\langle x, v \\rangle^t \\geq 6M|T| \\\\right\\\\}.\n\\end{equation*}\nThe first four encode a sparsity constraint in the direction $v$ while the last searches for a direction with large directional moment. Since, the above polynomial optimization is non-convex and in general NP-Hard, the paper instead solves a sum-of-squares relaxation. If no solution to the above set of equations is found, the process terminates with a well behaved set of points. Otherwise, the algorithm uses the solution to prune the points in $T$ to a smaller set with better moment behavior. A large good set exists because the $(\\alpha n)^2$ sized subset consisting of pairs from the true distribution exists in $T$ and these points are very rarely removed. This step is conceptually similar to simple filtering strategies for the conceptually simpler iterative filtering setting where $\\alpha > 1/2$.\n\nHaving pruned $T$ to a set with well-defined moments, the authors then design an intuitive procedure to identify a large subset of $X$ with substantial overlap with the good set and well-behaved moments. To do this, they note that $T$ induces a graph with vertices $X$ and pairs retained by the pruning process. The good set is expected to form an approximate clique within this graph. However, identifying a large clique is a hard problem in general. However, the authors observe that the graph has several nice properties. The first being that one can add edges between points $(x_i, x_j)$ whose neighborhoods have substantial overlap which also results in a larger corresponding difference set with well-behaved moments. The authors then show that if a random point from the set of good points is chosen and its neighborhood set is pruned based on the number of neighbors within the set, this yields a set of points with well behaved moments and large overlap with the set of good points. The mean of these points then yields a good approximation to the true mean $\\mu$ from these two properties. Finally, selecting a point at random results in an point in the good set with probability at $\\Omega (\\alpha)$. Thus repeating this procedure $O(1 / \\alpha)$ times results in a list of size $O(1 / \\alpha)$ one of which is a good approximation to the true mean.\n\n**** POST REBUTTAL UPDATE ****\n\nI acknowledge the authors response and have decided to retain my current evaluation.", "questions": "One question I have for the authors is the implications of these results for list-decodable sparse mean estimation with fewer moments. For example, in the setting where the underlying distribution only has $2$ moments (bounded covariance), does this approach achieve the optimal recovery of $O(1 / \\sqrt{\\alpha})$ with say $\\mathrm{poly} (k, \\log d, 1/\\alpha$ samples? This is in line with prior work on list decodable estimation which yield conceptually simpler algorithms in the bounded covariance setting albeit with worse recovery guarantees due to the milder moment requirements.\n", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper makes good progress on the important problem of building robust estimators in the sparse regime. Furthermore, the natural framework proposed in the paper is substantially simpler than prior approaches to list-decodable estimation. However, it is not clear from the current draft the implications of this framework for other settings where much fewer moments are available in the good planted distribution. In particular, it is not clear if the exponent in the recovery guarantees are optimal when one is concerned with the heavy tailed regime. \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": {}}, {"review_id": "gvEXOQjg16U", "reviewer": "Reviewer_EBeb", "summary": "This work considers list-decodable mean estimation: a small fraction (say 10%) of the data are iid draw from D, while the rest are adversarial. The goal is to output a finite number of estimates such that one of them approximates the mean of D. This had been broadly studied since [CSV17]. The main contribution of the current work is two-folds: 1) consider the sample complexity when the mean of D is sparse; and 2) design a new algorithm that runs in manageable time (in some regimes, polynomial time).\n\nOverall, I think this is a solid work.", "questions": "See above.", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n1. Understanding the sample complexity of sparse mean estimation is important, and the work presents an algorithm with sample size poly(k, log(n)). This significantly improves prior results which attained poly(n) (though without the sparsity condition).\n\n2. The use of sparsity in SoS system is interesting.\n\n3. The developed difference-of-pairs filtering algorithm looks interesting, which did not appear in the literature. That being said, it is unclear whether such technique is vital to tackling the underlying problem under bounded moment condition. For example, a concurrent work shows similar results under Gaussian distribution without the new filtering approach:\n\n- List-Decodable Sparse Mean Estimation, Zeng & Shen, arXiv:2205.14337\n\n4. An SQ lower bound is also established and is useful to understand the fundamental limits of statistical estimation. I think it will be helpful to expand a bit on technical innovation to derive such SQ lower bound. How does it differ from [DKS17]? \n\n5. While the SQ-type lower bound has been widely studied, it is weaker than information-theoretic bound. Can the authors comment on the challenge of characterizing the latter?\n\n6. The description on sum-of-squares proof is rather short. I suggest authors include more background to make the paper self-contained. In particular, I saw that SoS is a useful tool to certify bounded moments, but is this the only purpose? Does it imply that for *any* general problems, SoS can be used in such a way as certification?", "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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "69_vSQKY8D", "reviewer": "Reviewer_AakN", "summary": "This paper studies the problem of list-decodable mean estimation in the sparse setting. For distributions that have certifiable bounded t-th moment in any k-sparse directions, it proposes an algorithm that achieves error of (1/alpha)^{O(1/t)} in a sample and computationally-efficient manner. For Gaussian distribution, it achieves error rate \\sqrt{log(1/alpha)} with quasi-polynomial complexity. The work leverages a technique called the “difference of pairs filter”, which filters on the difference between pairs of points instead of the points themselves, and a rounding scheme that recovers a reasonably good estimation of the underlying distribution.\n", "questions": "The structure of the paper can be improved (see Q2). It would be better if the technical highlights (probably for each algorithm) can be placed more evenly into the text, thus leaving the overview more concise. The paper can add more discussions on the merit of the “difference of pairs” technique and probably any other problems that could benefit from this new technique. \n", "limitations": "The work seems not have any negative societal impact as it is purely theoretical.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengthes: The problem of list-decodable learning has addressed a flurry of recent interest in the machine learning community. It concerns learning from modern data that is usually corrupted with a high amount of noise, thus is considered to be significant and relevant. The proposed technique “DoP filter” is quite novel, which elegantly leverages the fact that the differences between the good points are close to zero. The performance of the algorithms are near-optimal.\n\nWeaknesses: The structure and the presentation of the paper can be better. For example, the introduction seems to take up to 4.5 pages of the main text, while the algorithms, theorems, and proofs take the rest, making it harder to appreciate the contribution of this work. \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