List-Decodable Sparse Mean Estimation
Authors: Shiwei Zeng
Jie Shen
Venue: NeurIPS 2022 Accept (2022)

Abstract: Robust mean estimation is one of the most important problems in statistics: given a set of samples in $\mathbb{R}^d$ where an $\alpha$ fraction are drawn from some distribution $D$ and the rest are adversarially corrupted, we aim to estimate the mean of $D$. A surge of recent research interest has been focusing on the list-decodable setting where $\alpha \in (0, \frac12]$, and the goal is to output a finite number of estimates among which at least one approximates the target mean. In this paper, we consider that the underlying distribution $D$ is Gaussian with $k$-sparse mean. Our main contribution is the first polynomial-time algorithm that enjoys sample complexity $O\big(\mathrm{poly}(k, \log d)\big)$, i.e. poly-logarithmic in the dimension. One of our core algorithmic ingredients is using low-degree {\em sparse polynomials} to filter outliers, which may find more applications.

List-Decodable Sparse Mean Estimation
Shiwei Zeng
Jie Shen Department Computer Science
Department of Computer Science Stevens Institute of Technology szeng40stevens. edu
Stevens Institute of Technology jie, shendstevens. edu
Abstract
Robust mean estimation is one of the most important problems in statistics: given a set of samples in I& where an fraction are drawn from some distribution D and the rest are adversarially corrupted, we aim to estimate the mean of D. surge of recent research interest has been focusing the list-decodable setting where (0, žl. and the goal is to output a finite number of estimates among which at least approximates the target mean. In this paper, consider that the underlying distribution D is Gaussian with k-sparse mean. Our main contribution is the first polynomial-time algorithm that enjoys sample complexity (pooy log d)), i.e. poly-logarithmic in the dimension. One of our core algorithmic ingredients is using low-degree sparse polynomials to filter outliers, which may find more applications.
Introduction
Mean estimation is arguably fundamental inference task in statistics and machine learning. Given set of samples {a1,.... ................................ Fn C Rd where an fraction are drawn from some well- (e.g. Gaussian) distribution D and the rest are adversarially corrupted, the goal is to estimate the mean of D. In the noiseless case where of measure phenomenon [LT9T] However, this is rarely the case as modern data sets are often contaminated by random noise or even by adversarial corruptions. Thus, great deal of recent efforts are focused on efficiently and robustly estimating the target mean in the presence of outliers.
1, the problem can be easily solved in view of the concentration
Generally speaking, there phase transition between > 1/2 and 0 < S 1/2, and solving either problem in a computationally efficient manner is highly nontrivial. The problem that most of the samples uncorrupted, i.e. 1/2, has a very long history dating back the 1960s Tuk66 Hub64], yet only until recently have computationally efficient algorithms been established [DKK 16 [RVI6]. The other yet more challenging regime concerns that an overwhelming fraction of the samples are corrupted, i.e. a < 1/2. which even renders estimation impossible. This motivates line of research on list-decodable mean estimation CSVI7. where in place of outputting one single estimate, the algorithm is allowed to generate a finite list of candidates and is considered to be successful there exists at least one candidate in the list that sufficiently close to the target mean.
In this work, we investigate the problem of list-decodable mean estimation, for which there have been plethora of elegant results established in recent years. From a high level, most of them concern error guarantees and running time. For example, [CSVI7] proposed the first tractable algorithm based on semidefinite programming. which runs in polynomial time and achieves optimal error rate for multi-filtering scheme and showed that the error rate can be improved by using high degree polynomials if the underlying distribution is Gaussian. The more recent works [CMY20) pKK*2le further addressed the computational efficiency of this task and achieved almost linear running time in certain regimes.
sariance-bounded distributions. [DKSI8 8D developed
Although all of these algorithms exhibit near-optimal guarantees on either error rate or computational complexity, it turns out that less is explored to improve another yet important metric: the sample
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

complexity. In particular, the sample complexity of all these algorithms is (ppoly(d)) hence they quickly break down for data-demanding applications such as healthcare where the number of available samples is typically orders of magnitude less than the dimension d [Wail9]. Therefore, a pressing question that needs to be addressed in such a high-dimensional regime is the following:
Does there exist provably robust algorithm for list-decodable mean estimation that runs in polynomial time and enjoys a sample complexity bound of O(polylog(d))?
In this paper, we answer the question in the affirmative by showing that when the target mean is k-sparse, i.e. it has at most k non-zero elements, it is setribudt-effiiiently list-decodable.
Theorem (Main result). Given parameter a E (0, 21 failure probability T E (0, 1). a natural number 2 1, and a set T of -1"""" 'log" of (art) )) samples in R", of which at least a (2x)) -fraction are independent draws from the Gaussian distribution (H, Is) where ||eo S k, there exists an algorithm that runs in time poly (IT'), d', 2)), ) uses polynomials of degree at most 26, and returns list of (1//)) number of k-sparse vectors such that with probability 1 TT, the list contains at least one f E Rdd with I| 8i4-yl; pll2 Ō(a= VV(Et + log 2)). where Õ()) hides poly-logaritmii factors.
o'
Remark 2. The key message of the theorem is that when the true mean is k-sparse, it is possible to efficiently approximate it with O (pplyylog( (d) samples. This is in stark contrast to existing list- decodable results [CSVIZ DKST (MY20 DKK20al DKK 21al where the sample complexity (ppoly(d)). The only attribute -eficieenn robust mean estimators are [[DLSI7] DKK*1 19 CDK+21 but their results hold only for the mild corruption regime where a > 1/2.
Our algorithm and analysis hold for any degree 2 1. When & 1, the sample complexity reads as -7 log 6 d) and the algorithm achieves error Ö(a=²) 2). As opposed to an O(1 - a)) error rate obtained for a > 1/2, the (non-vanishing) error rate Ō(a 3) is typically what one can expect for list-decodable mean estimation under bounded second order moment condition, in light of the lower bounds in DKS 85)) When leveraging degree-2f polynomials into algorithmic design, we obtain the improved δ (a VZ(e + log 1)) eгror guarantee. Specially, when taking
Remark 3.
{ = ( log 2t) our algorithm achieves error rate of Ö log 3 (+)) in quasi-polynomial time. This is very close the minimax error rate of (log3 (1)) established in [DKSI8b).
Remark 4. If we further increase the sample size with an ll multiplicative factor with & = Olog 2) our algorithm will achieve an Ó logg (2)) error guarantee, which matches the minimax lower bound. The proof follows the same pipeline and we leave it to interested readers.
1.1 Overview of Our Techniques
Our main algorithm is inspired by the multifiltering framework of (DKSI&b) where the primary idea is to construct a sequence of polynomials to test the concentration of the samples to Gaussian so that the algorithm either certifies that the sample set behaves like Gaussian, or sanitizes it by removing a sufficient amount of outliers. Our key technical contribution lies into a new design of sparse polyuomials, and new filtering rules tailored the sparse polynomials.
Sparse polynomials and sparsity-indueet filters. To ensure that our algorithm sarribute-efficiee we will only control the maximum eigenvalue of the sample covariance matrix on sparse directions. Since such computation is NP-hard in general, we first consider a sufficient condition which tests the maximum Frobenuis norm under cardinality constraint, similar to the idea of [DKK*1] 19) If such Frobenuis norm is small, it implics a small restricted eigenvalue and hence the sample mean is returned. Otherwise, by a set of 44f) basis polynomials and O(E22)) coordinates of the samples (see Definition 7) and measure the concentration of these sparse polynomials to the Gaussian. Now the underlying polynomials are sparse, we also design new sparsity- induced filters to certify the sample set, as otherwise large amount of clean samples will be removed. See Algorithm 3 and Algorithm 2!
construct sparse polynomials in the sense that they can be represented
Clustering by norm. Technically, the success of our attribute-efficciet multifiltering approach hinges on a condition that all the samples lie within small -nom ball. It is not hard to see that all the Gaussian samples satisfy such condition, and we show that there is a simple scheme which can simultancously prune and cluster the given samples into O(1/a) groups, such that the

---

retained samples are close under the Lx- norm and at least one group contains most of the Gaussian samples. We note that the use of the -. noom as our metric ensures attribute efficiency this step. An immediate implication of this clustering step is that the polynomials of Gaussian samples will be close enough, which facilitates the analysis of the performance of our filters. See Section
1.2 Related Works
Breaking the barrier of the typical (ppolydd) sample complexity bound is one of the central problems across many fields of science and engineering, Motivated by real-world applications, property termed sparsity is often assumed for this end, meaning that only & out of the d number of attributes contribute to the underlying inference problem. In this way, an improved bound of
O(poly log d)) can be obtained in many inference paradigms such as linear regression CCDS98
Tib96 CTO5 Don06 [S SL SL18 WSL18. learning of threshold functions [[188 BHL95
STT12
PV13 ABHZI6 ZSA20 She20 SZ211. principal component analysis [Ma13] DKK 19).
and mean estimation BDLSIZ
DKK* + 19 CDK*21] Unfortunately, the success of all these attribute-
efficient algorithms hinges on the presumption that the majority of the data are uncorrupted.
Learning with mild corruption (a 1/2). Learning in the presence of noise has been extensively studied in broad context. In supervised learning where a sample consists of an instance (i.e. feature vector) and label, lots of research efforts were dedicated to robust algorithms under label noise [AL8 Slo88 [N06]. Recent years have witnessed significant progress towards optimal
algorithms in the presence of label noise, see for example, [KKMS05| ABLI7 DKTZ20 ZSA20
DKK+20b SS22 and the references therein. The regime that both instances and labels are corrupted turns out to be significantly more challenging. The problem of learning halfspaces under such setting was put forward in the 1980s Val5 KL88), yet only until recently have efficient algorithms been
established with near-optimal noise tolerance ABLL DDS ISal She21] SZ211. In addition, [BJKT5 KKMI& LSLC20 studied robust linear regression and [DLI presented a set of interesting results under various statistical models. More in line with this work the problem of robust mean estimation, see the breakthrough works of [DKK 16 LRVI6 and many follow-up works [DK 17
BDLSI7 DKS17 SCVI8 KSSI& DKK 19 HLZ20
2D
Learning with overwhelming corruption (a S 1/2). The agnostic label noise of Hau92 KSS92
seems the earliest model that allows the adversary to arbitrarily corrupt any fraction of the data (say 70%), though it can only corrupt labels. Following (CSVI7). considerate number of of recent works have studied the scenario that both instances and labels are grossly corrupted, and the goal is to output finite list of candidate parameters among which at least one is a good approximation to the target. This includes list-decodable learning of mixture models DKSTTh DKK*211 regression [KK]19 RY20al, and subspace recovery [RY20b] BK21] Interestingly, there are some works studying the problem under crowdsourcing models, where the samples are collected from crowd workers and most of them behave adversarially SVCI1 ABHMI MV18 ZS21.
It worth noting that IDKK#22 concurrently and independently developed a polynomial-time algorithm to solve the same problem, with an interesting difference-of pairs metric to filter outliers.
1.3 Roadmap
We collect useful notations, definitions, and some preliminary results in Section Our main algorithms are described in Section aloon with performance guarantees. We conclude the work in Section hi and defer all proof details to the appendix.
2 Preliminaries
Vector, matrix, and tensor. For a d-dimensional vector v = (Ui...., va), denote by ||e|| its L2-norm, ||v|| its Lo-mo,, Illllo its Lo-"norm" that counts the number of non-zeros, and | le its infinity norm. The hard thresholding operator trim; Rd - I2d keeps the is largest elements (in magnitude) of vector and sets the remaining to zero. Let [d] := 21.2..... ... d} for some natural number 0. For an index set C [d]. on the vector of v restricted on Ω. We say a vector is k-sparse if it has at most & non-zero elements, and likewise for matrices and tensors. For matrix M of size di x d2, denote by [M P its Frobenius norm and by ||M]]_ its nuclear norm. For
U C [di] x [d2], denote by My the submatrix of M with entries restricted to U.
3

---

We also use tensors in our algorithms to ease expressions. Note that vectors and matrices can be seen as order-1 and order-2 tensors respectively. We say that an order-/ tensor symmetric i = A A1 (f1.....)) ..) for all permutations я. Given two tensors A and B, denote by A x B the outer product (or tensor product) of A and B. We will slightly abuse ||Al|2 to denote the L2-norm of long vector.
a tensor A by seeing
Probability. We reserve the capital letter G for a random draw from N(, Ia), i.e. G ~ (1, Id), where μ E Rd the target mean that we aim to estimate which is assumed to be k-sparse. Suppose that T is a finite sample set. We use pr to denote the sample mean of T, i.e. PT TT Exer and use p(T) to denote the random variable p(z) where z is drawn uniformly from T.
Constants. The capital letter C' and its subscript variants such as C1, C2 are used to denote positive absolute constants. However, their values may change from appearance appearance.
2.1 Polynomials
Let (II,..., Ta) be d-dimensional vector in Rd, and let (ai,..., Ca) E Nd be d- dimensional multi-index. A monomial of x a product of powers of the coordinates of with natural exponents, written as xº := multiplied by real coefficients; that is, p(z) EaEA Ca where A C. Nd is finite set of multi- indices and the Co 's are real coefficients. Note that the degree of p(z) is given by maXacA ||a||]- We denote by P(R4, 1) the class of polynomials on R with degree at most I. We will often use the probabilist's 's Hermite polynomials that form a complete orthogonal basis with respect to N (0, Ia).
== I[ "; aj A polynomial of x. p(z), is a finite sum of its monomials
Definition 5 (Hermite polynomials). Let x E IR be a variate. For any natural number E N, the degree-/ Hermite polynomial is defined Her(x) (-1)e =2 d'
der e $. For E N2 and x E Rd, the d-variate Hermite polynomial is given by Hc (x) = I Hca, (I:), which is of degree ||a|]
Harmonic and homogeneous polynomials. A polynomial h(x)) E P(R411) 1) is called harmonic if it can be written as a linear combination of degree-l Hermite polynomials. A polynomial Hom(x) e P(Rd, 1) is called homogeneous if all of its monomials have degree exactly I.
Fact If a polynomial is degree-l harmonic or homogencous, then there is one-to-one mapping between it and an order-l symmetric tensor.
To see this, we may define an operation "o" such that He,(x;) o Her(z,) = (z, Hey (a,) if i * and equals Hez (zx) otherwise. Then any degree-! Hermite polynomial can be written as (I;,) o He, (Zi,) ... o Hcz(z,,) (Is,) where all the indices & E [d]. We will consider that one such sequence (fi...., ..) in) exactly corresponds to one degree-l Hermite polynomial on R4, and there are d' number of such sequences that form all degree-/ Hermite polynomials. In this sense, any harmonic polynomial h(x) can be written as h(x) = Ei..... Ai.....i Hej (ara.) Hez (I.,)... ..... He (zi.). where A......, 's are the coefficients which form an order-/ tensor. If we choose A as symmetric, it is easy to see that A fully represents hz)). Then, we can convert "o" back to the regular product by counting the number of times particular index j appearing in (i....., 4t). If we denote this number as eg it). we have
h(x)=
1
Σ
A A
(e =: ha(x), with Σ (c) -1 (2.1)
where the factor 1/Vil is only used to normalize the magnitude of A to ease our analysis. Likewise, any homogeneous polynomial takes the form
(o) = Σ A A
II x (lhh...
11.....3
Sparse polynomials. In order to define sparse polynomials, we will first specify set of basis polynomials (bi,..., b C P((Rd, 7). In this paper, we will either choose such set as all degree-l monomials or all degree-/ Hermite polynomials.

---

Definition 7 ((K, -sp-rse polynomials). We that polynomial E P(R is (k, (i)-sparse if it can be represented by most number of basis polynomials and & coordinates the input vector. We denote by P(RR", (b) the class of (x. 1/)-spase polynomials.
Note that when and I are fixed, p(a)) will depend at most x coordinates. Thus, the introduction of the parameter vp makes sense only when và S k. In our algorithm, we will always have < 26, 1 and 2fk for some natural number l 1.
2.2 Representative Set and Good Set
To ease our analysis, we will need a deterministic condition on the set uncorrupted samples. Definition (Representative set). Given (0, 2] and E (0, 1), say that a sample set So Rd representative with respect to P P( 22, k 22k2*) if the following holds:
a
sup Pr(pp(G 2 0] - Pr[p((a) 2 0]| & co. where eo == 100A22 log 2 PEF
We show that a sufficiently large set drawn independently from (M, L,) representative. The proof follows from the classic VC theory, and is deferred to Appendix A.1
Proposition 9 (Sample complexity). Given a E (0, 1) and t (0, 1), let Sa be a set consisting SSc C (L*+v) log log sufficiently large absolute constant. Then, with probability -T,
(I++t)logg log independent samples from Nu,, Ia) where C 0 is
22
sup PEP(2"
[Pr[p(G) 20 (-rp(((aS))))) 2 011 c.
In particular, when 26, K ke vp = 2t and E 100% log 2 t4 for some natural number é 2 1, it suffices pick |Sal = C' so that Sg is a representative set.
C" 6n -log'( aat for some sufficiently large constant as
Our algorithm will progressively remove samples from T. and key property that ensures the success of the algorithm is that most corrupted samples eliminated while almost all uncorrupted samples are retained. Alternatively, we hope that T contains a representative set that contributes to a nontrivial fraction. For technical reasons, we also require that all samples in T lie in small Lx -bll..
Definition 10 (a-good set). multiset T C Rd is a-good if the following holds:
1. There exists a set SG which is representative and satisfies |e NTI > max((1 a x/6) |Sal. a [T]}.
2. maxz,yer || vll SC. Vlo((d [ for some constant C > 0.
It is not hard verify that the initial sample set 7 satisfies the first condition, and will also fulfill the second one with a simple data pre-processing, as stated in the next section.
2.3 Clustering for the Initial List
Since the corrupted samples may behave adversarially, we will perform preliminary step of clustering which splits T' into an initial list of subsets, among which at least one is a-good in the sense of Definition TO We first show that all Gaussian samples have bounded L -nomm with high probability, which simply follows from the Gaussian tail bound.
Lemma 11. Given E (0, 1), with probability 1 T. we have max || Ml1 S v 2og 4Sal where So is set of samples drawn independently from N I.).
The above observation implies that for any z, Sç, their distance under the - metric is at most 2 [Scl/T) /T) S O(v log ed) as far as the size of Sg has the same order with the one in Proposition 9 To guarantee the existence of such Sc. it suffices to draw corrupted sample set T that is 1/a times larger than (Sa). The lemma below further shows that this sufficient to guarantee the existence of an a-good subset of
5

---

Algorithm 1 CLUSTER a,, T,
Require: A multiset of samples T C Rd, parameter E (0, 1/2]. failure probability (0, 1),
degree of polynomials /
1: A set of centers C + 0, radius 7 +- Co . E-ooo
T. proceed as follows: if there ar for some constant Co > 0.
2: For each
least a [T] samples y in T that satisfy || yll.0 - 2,, and no sample z' E C satisfies I|x - 2l I 6y then <- C {x}.
3: For each 24g E C, let T; {y T: || ullxc S 67).
4: return . ].
Lemma 12 (CLUSTER). Given E (0, and E (0, let T be the sample set given to the
learner. If [ C Ciple log St (d)) and a (2a)-fraction are independent samples from N La). Algorithm 1 returns a list of at most I/a many subsets of such that with probability at least T, at least one of them is an a-good set.
As will be clear in our analysis, the motivation of bounding the Log -dittanc is to make sure that the function value of any p(x) ha(z WTT) E [PR L, K, 1/) is bounded for samples in the a-good subset T;. This is because when there exist significant fraction of good samples Ti, we want to efficiently distinguish the corrupted and uncorrupted ones. A value-bounded polynomial function will facilitate our analysis on the function variance.
Lemma 13. Suppose that T is a- a-good and a polynomial p P(R 1, 1,4 22k22) satisfies the following: there exists symmetric order-l tensor A such that ||ll| S and p(x) = ha (x WT).
Then, it holds that max (p(x:) p(y)) S 2k . where 7 = Co v loog kd
3 Main Algorithms and Performance Guarantees
We start with review of the multifiltering framework that has been broadly used in prior works [KSI8B DKK20al DKK followed by a highlight of our new techniques.
The multifiltering framework, i.e. Algorithm 2 includes three major steps. The first step is to invoke CLUSTER (Algorithm) D to generate an initial list L which guarantees the existence of an o-good subset of T (see Lemma T2). We then imagine that there tree with root being the original contaminated sample set and each child node of the root represents a member in C. The algorithm iterates through these child nodes and performs one of the following: (1) creating leaf node which is an estimate of the target mean; (2) creating one or two child nodes where are subsets of the parent node; (3) certifying that the set cannot be a-good and delete branch. In the end, if all leaves of the tree cannot be further split or deleted, the mean of the subsets on leaf nodes will be collected as list M. is worth noting that the goal of algorithmic design is to guarantee that there always exists a branch that includes only a-good subsets. In other words, at any level of the algorithm, at least one of the subsets of T is a-good, which ensures the existence of good estimation in the returned list M. The final step is black-box algorithm that reduces the size of M from O(poly (1 (1))) to O(1/a,,, which due to [DKST8b]. Our technical contributions lie into an attribute-ffficient implementation of the first and second steps. In this section, claborate on the second step, i.c. the algorithm.
3.1 Overview of Attribute-Efficien Multifiltering
The ATTRIUTTEEEFIIIIE-MMUUTTE
algorithm is presented in Algorithm 3 The starting point of the algorithm is a well- well-known fact that if the adversary were to significantly deteriorate our estimate on μr, the spectral norm of a certain sample covariance matrix Σ would become large [DKK 16 ( In order to achieve attribute-efficientt sample complexity O(poly(k: log d)), it is however vital to control the spectral norm only on k' -'-sparse directions for some pre-specified polynomial degree & > 1, which can further be certified by a small Frobenius norm restricted on the largest 2.26 entries. If the restricted Frobenius norm is sufficiently small, it implies that the sample covariance matrix behaves as a Gaussian one, and the algorithm returns the empirical mean truncated to be k-sparse (see Step 4h. Otherwise, the algorithm will invoke either BASICME (i.c. Algorithm f

---

Algorithm 2 Main Algorithm: Attribute-fficiien List-Decodable Mean Estimation
Require: A multiset samples C CR,, parameter a E (0, 1/2, failure probability T E (0, 1),
degree of polynomials & 2 L.
1: (Ti,..., Tm + CLUSTER( (T, a. (T, 2 t (/T). (Tm, a/2)), M t 0.
2: while L & 0 do
3: (T',a') a²) < an element in L. LM a'))-
4: ANS ATTRIBUTE-RFFICIEEE SEFFIIIINTTMMUUTILLEERRR (T
(i) if' ANS is vector then add it into M.
if' ANS is list of (Ti, aq) then append those with a; L.
(iii)
if' ANS = NO then go to the next iteration.
5: end while
6: return LISTREDUCTION(T,O a, a, M).
Algorithm 3 AATRABUTT--HHHHLAAAMTTTTTEEEEEEE a, T,E)
Require: A multiset of samples T C RR parameter (0, failure probability (0, degree of polynomials & 2 1.
1: Σ + - PPee(T -TT and (a.e(z) is the column vector of all degree- Hermite
polynomials of
(1* 4k*) + index of the k diagonal entries and _ - k*) entries above the main diagonal of Σ with largest magnitude. U <- ((4.::))121 U ((i, 42221, U t I I,
2: (()))))))
with = fir)e1 U (1th221-
[[ (e+CC C1 log 2) log² log _ 2 for large enough constant C₁ 0. 4: if [E)v S Xaparse then return j +- trim (PT)
3: Aaasre
5: (X", ", f- the largest eigenvalue and eigenvector of (E)r.
6: X Naparse then
7: if l then ANS + DASICMF(T,0,T.)) else ANS +- (ARM where Pi (I) == v² Pa.e(=-ur) MT).
8:
else
9:
P2(x)= + T (Pacle-1ay - A Pasla -TT) with == =EE).
10: ANS < HARMONICMF(T,Q.T.0)
11:
end if
12: return ANS.
or HARMONICMF (i.e. Algortihm to examine the concentration of a polynomial of the empirical data that of Gaussian. Both algorithms will either assert that the current sample set does not contain a sufficiently large amount of Gaussian samples, or will prune many corrupted samples to increase the fraction of Gaussian ones. A more detailed description of the two algorithms can be found in Section 3 and Section 3.2.2 respectively. What is subtle in Algorithm 3 is that we will check the maximum eigenvalue X of the empirical covariance matrix restricted on carefully chosen subset U" which corresponds to the maximum eigenvalue on a certain (2x2r)-sparse J-sparse direction. If X too large, this indicates easy problem since it must be the case that the adversary corrupted the samples in an aggressively way. Therefore, suffices to prune outliers using degree-E polynomial Pi which is simply the projection of Pa.e(æ (UT) onto the span of the maximum eigenvector; see Step 7 in Algorithm 3 On the other hand, if X on a moderate scale, it indicates that the adversary corrupted the samples in a very delicate way that it passes the tests of both Frobenius norm and spectral norm. Now the main idea is to check the concentration of higher degree polynomials induced by the sample set; we show that it suffices to construct degree-2( harmonic polynomial; see Step 10
While sparse mean estimation has been studied [DKK + 19 and the idea of using restricted Frobenius norm and filtering was also developed, we note that their analysis only holds in the mild corruption regime where a > 1/2. To establish the main results, we will leverage the tools from [DKST&b] with specific treatment on the fact that μ is k-sparse, to ensure an attribute-efficient sample complexity bound. As we will show later, a key idea to this end is to utilize a sequence of carefully chosen sparse polynomials in the sense of Definition / along with pearsity-induce filters.

---

The performance guarantee of ATTRIBUTE EFFICIENT- AITRCINTT-EFFRCIENT
MULTIFILTER is as follows.
Theorem 14 (Algorithm B. Consider Algorithm G and denote by ANS its output. With probability 1- T, the following holds. ANS cannot be TBD. If ANS is a k-sparse vector and if a-good. then || All S Ō(a $ VE(l + log ))) If ANS NO, then is not a-good. If ANS
())) for some mn S 2, then T, C T for all i E [mm] and E 1 S - if additionally T
a-good, then at least one T; is ok-good. Finally, the algorithm runs in time (ppoly((T),dB))
3.2 Analysis of
We first show that if the restricted Frobenius norm of the sample covariance matrix is small, then the sample mean is a good estimate of the target mean.
Lemma 15. Consider Algorithm
3 If the algorithm returns a vector ja at Step 3 and if is a-good,
we have that / - Hll2 S O(a IZ VV. (f + log b) logg (2 + log ))
Next, we give performance guarantees on the remaining steps of Algorithm where we consider the case that the algorithm does not return at Step 4 Namely, the algorithm will either reach at Step 7 or Step TO and will return the ANS obtained thereof. These two steps will invoke BASICMF or HARMONICMF on different sparse polynomials. Observe that both algorithms may return 1) "NO", which certifies that the current input set T is not a-good; 2) a list of subsets {(T, a:) for some m 2, which Algorithm 3 will be called in a recursive manner, 3) TBD, which indicates that the algorithm is uncertain on being a-good. In the following, we prove that the way that we invoke BASICMF and HARMONICMF ensures that they will never return TBD when being called within Algorithm 3 We then give performance guarantees on these two filtering algorithms when they return "NO" or { (1T,, ) thus establishing Theorem 14
Let us consider that the algorithm reaches Step 7 i.e. the largest eigenvalue on one sparse direction is larger than the threshold Xsparse It is easy to see that when & = 1, ANS cannot be TBD since the only way that BASICMF returns TBD is when Var[p(TT) is not too large, but this would violate the condition that x > Xaparsn in view of our setting on Spparse- Similarly, we show that under the large x regime, HARMONICMF will not return TBD either. Thus, we have the following lemma.
Lemma 16. Consider Algoritim
If it reaches Step then ANS + TBD.
Now remains to consider the case that the algorithm reaches Step TO which more subtle since the evidence from the magnitude of the largest restricted eigenvalue is not strong to prune outliers. Note that this could happen even when T contains many outliers, since x is not the maximum eigenvalue on all sparse directions but large, we show that the algorithm can still make progress by calling HARMONICMF on dfgree-2f sparse polynomials. This is because higher-degree polynomials are more sensitive to outliers than low-degree polynomials, as far as we can certify the concentration of high-degree polynomials on clean samples. As result, we will have the following guarantee.
submatrix indexed by U' Fortunately, if X is not
Lemma 17. Consider Algorithm
If it reaches Step T0 then ANS + TBD.
3.2.1 Basic Multifilter for Sparse Polynomials
The BASICMF algorithm (Algorithm 4 is a key ingredient in the multifiltering framework. It takes as input sparse polynomial p and uses to certify whether T is a-good and sufficiently concentrated. The central idea is to measure how p(T) distributed and compare it to that of the distribution of p(G). We require the input p has certifiable variance on G. i.c. Varlp(G)] S 1, as otherwise, it could filter away large number of the good samples. We note that the bounded variance condition is always satisfied for degree-1 1 Hermite polynomials under proper normalization, while for high-degree polynomials, one cannot invoke BASICMF directly (see Section 3.2.2 for a remedy).
The way that BASICMF certifies the input sample set not being a-good is quite simple: if not all samples lie in a small ball, it returns "NO" at Step 2 in that this contradicts Lemma [3] Otherwise, the algorithm will attempt to search for a finer interval (a, b) such that includes most of the samples. If such interval exists, then either the adversary corrupted the samples such that the sample variance is as small as that of Gaussian while the sample mean may deviate far from the target, in which case BASICME returns TBD at Step 5 or the sample variance is large, in which case
8

---

Algorithm 4 BASICMF(TT T,
Require: A multiset of samples T C Rd, parameter E (0, 1/2), failure probability (0, 1), a polynomial E P(R ((RR,,,, k42 2 such that 1 s 26, Var[p(G)] I 1, and p(r) =
hA pT).
,2 +- Co. ve log 4d. 1: R t- 1og ( 1
2: if maxr.yeT (p(x) p(y)] > 2k .f then return "NO".
3: if there is an interval (a, of length C1 lo log a) that contains at least (1 a )-fraction
2
of samples in {p(z) z E ] then
4: if Varlp(T)] S Ci (e C C, log 4) l2 + log ( then
5: return "TBD".
6: else
7:
Find threshold t 2R such that
20
Pr weT
min [xx) - 1p(x)) b/} 2 > exp( (t- ( +
1.26 log' Ad
T' fx min(pp()) al 1p(x) - baj s 5t). a' t (1-a//3121
8:
[27]
9: return a(T),
end if
11: else
Find R. R' > such that the sets Ti := {o T p(x) > t R' and T3 == fx T
p(x) < t + R'} satisfy
Th. 2 + |T2l S 2T (1 aa000)² and |T| m (T)) (T)
13: 0; - a. - a² a2/100) /T/ Ty).
1, for i 1,
14: return (TT,
15: end if
it is possible construct a sparsity-induced filter to prune outliers (see Steps and We note that in Step 7 the first term on the right-hand side derived from Chernoff bound for degree-l Gaussian polynomials and the second term is due to concentration of empirical samples to Gaussian (see Definition g). both of which are scaled by a factor 8/a so that the number of the samples removed from T is 8/a times more than that of the good samples in the representative set SG C T, which means most of the removed samples are outliers. We show by contradiction the existence of the threshold & (see Lemma 26 In fact, had such threshold / not existed, the set T must be sufficiently concentrated such that the algorithm would have returned at Step This essentially relies on our result of the initial clustering Algorithm D which guarantees that each subset bounded in small Loo -ball and the function value of on the a-good T' does not change drastically (Lemma L We then show that equipped with such threshold T" a subset 7 and it a' a'ogood T' is a-good (Lemma 28).
When there is no such short interval [a, b), the algorithm splits T into two overlapping subsets (T1, T such that Tj n T2 is large enough to contain most of the samples in Sc. This guarantees that most of the samples in Sq (if T is a-good)
always contained in one subset and thus there always exists an a--ood subset of T. We show that an appropriate threshold / can also be found at (Lemma 30). and at least one T; is og-good if T a-good.
Stepl 12
As result, we have the following guarantees for Algorithm 4 see Appendix B for the full proof.
Theorem 18 (BASICMF), Consider Algorithm f Denote by ANS its return. Suppose that T being a-good implies Varlp(G)) < 1. Then with probability 1 - т, the following holds. ANS is either "NO", "TBD", or a list of {[T,, ax)) y )mm with m S 2. If ANS = NO, then T is not a-good. 2) If ANS TBD, then Varlp(T)) ((( + log 2)²² log 2 (2+ log :)); and if additionally T is a-good, then EEp(G)) Elp(T)] < ( + log 2)² log(2 + log 1)). 3) If ANS = {(T,, ax) then 1 S 2 for all i E [m]: if additionally T is a-good, then at least one T: is gooo T; C T and E. az

---

Algorithm 5 HARMONICME(Z, T,P)
Require: A multiset of samples T C Rd, parameter E (0. 1/.1 failure probability т E (0, 1),
polynomial E P(R 1, 2 2
such that p(z) = hhaee pT) and ||A||2 = 1.
1: for 0, ,,.... do
2: Let B(y)) be an order-2l' tensor with B B by....ly J Ju
Σ boak
3: Consider B(y) d' @d symmetric matrix by grouping each of the i1, 11..... by and j1, ......... 3
coordinates together. Apply eigenvalue decomposition B(') obtain B((") E, VV&VV
4: ANS; + MULTILINEARMF(T V,, a, r/(d")) for every V.. If ANS; NO or a list of ([] for some i, then return ANS, If ANS, = TBD, continue.
5: end for
6: ANS & BASICMF(T, a,,, gha(r
g, - -r)) with B == (C1 (1 + log ") log (2 log :))²
If ANS = NO or list of (T) return ANS. If ANS TBD, still return "NO".
3.2.2 Harmonic Multifilter with Hermite Polynomials
Recall that applying BASICMF (Algorithm 4 polynomial p requires Varlp(G)) 1. It is nontrivial to verify this condition for a high-degree polynomial p, as the variance of high-degree Gaussian polynomials depends on the distribution mean, i.e. H(rr this case, which is unfortunately unknown. As a remedy, notice that for any harmonic polynomial A (z), Ee (n ( equals the summation of homogeneous polynomials of μ²,, which can also be seen as the expectation of multilinear polynomials over independent variables (4) N(,',, Thus, only need to verify the expectation of these corresponding multilinear polynomials, whose variance on G does not hinge on p'. The harmonic multifilter is presented in Algorithm where the subroutine MULTILINEARMP can be found in Appendix D We first present the guarantee when Algorithm returns all TBD at Step and reaches Step where we can certify bounded variance for h h -TT on G.
Lemma 19 (Variance of p). Consider Algorithm 5 have AG -
If it reaches Step 6 and T is a-good, then we
(a-GGGG-T )²] 88.
Based on Lemma 19
we have that Varlha - pT)/3 S 1, for which we can invoke BASICMF on can be applied immediately. We are ready to elaborate the proof
A / and Theorrm can
ideas for Lemma 16 and 17 First, observe that BASICMF returns "TBD" at Step 6 if and only
Varlha(T /
C1 (E C2 Co 2) log" log 1 Now return Algorithm
3 When
AA (2 PT) = Pa (z), this could not happen because Var(pı (T)) = Variu" Pa.e(T (T) X
X Apaars = [C (8 Ct log 2)-
log (2 + log 1 2 32 Ci (e C1 log 2 (2 log 4) contradiction that implies Lemma 16 When ha( - PT) = P2 (z). the case is more delicate. Here,
instead show that T must not be a-good and HARMONICMF will return "NO" correctly. This is because if T is a-good, Proposition 18 implies that E[ps is close to ETp)(T)). and together with
Lemma 19 we can show that E(p2(T)) is small. However, by construction ||())/|| || = E/pa (T) >
sparse contradiction that gives Lemma 17 The detailed proof can be found in Appendix B.3
4 Conclusion and Future Work
In this paper, we developed an attribute-efficien mean estimation algorithm which achieves sample complexity poly-logarithmic in the dimension with low-degree sparse polynomials under the list- decodable setting. A natural question is whether the current techniques could be utilized to attribute- efficiently solve the other list-decodable problems, such as learning of halfspaces and linear regression.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers and meta-reviewer for valuable discussions. This work is supported by NSF- 1948133 and the startup funding from Stevens Institute of Technology.
10

---

References
[ABHM17] Pranjal Awasthi, Avrim Blum, Nika Haghtalab, and Yishay Mansour. Efficient PAC learning from the crowd. In Proceedings of the 30th Annual Conference on Learning Theory, pages 127-150, 2017.
[ABHZ16] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. Learn- ing and 1-bit compressed sensing under asymmetric noise. In Proceedings of the 29th Annual Conference on Learning Theory, pages 152-192, 2016
[ABL17] Pranjal Awasthi, Maria-Florina Balcan, and Philip M. Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM, 63(6):50:1- 50:27, 2017.
[AL87] Dana Angluin and Philip D. Laird. Learning from noisy examples. Machine Learning, 2(4):343-370, 1987.
[BDLS17] Sivaraman Balakrishnan, Simon S. Du, Jerry Li, and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. In Proceedings the Conference on Learning Theory, pages 169-212, 2017.
the 30th Annual
[BHL95] Avrim Blum, Lisa Hellerstein, and Nick Littlestone. Learning in the presence of finitely or infinitely many irrelevant attributes. Journal of Computer and System Sciences, 50(1):32-44) 40, 1995.
[BJK15] Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression via hard threshold- ing. In NIPS, pages 721-729, 2015.
[BK21] Ainesh Bakshi and Pravesh K. Kothari. List-decodable subspace recovery: Dimen- sion independent error in polynomial time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, pages 1279-12977 2021.
[CDK+21] Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Rong Ge, Shivam Gupta, and Mahdi Soltanolkotabi. Outlier-robust sparse estimation via non-convex optimization. CoRR, 0ts/2109.11515, 2021.
[CDS98] Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposi- tion by basis pursuit. SIAM Journal on Scientific Computing, 20(1):33-61) 61, 1998.
[CMY20] Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. List decodable mean estimation in nearly linear time. In 6/ IEEE Annual Symposium on Foundations of Computer Science, pages 141-148. IEEE, 2020.
[CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 47-60, 2017.
[CTO5] Emmanuel Candès and Terence Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51(12))4203-4215, 2005.
[DKK + 16] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pages 655-664, 2016
[DKK 17) Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 999-1008. PMLR, 2017.
[DKK+19] 19] Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, and Alistair Stewart. Outlier-robust high-dimensional sparse estimation via iterative filtering. NeurlPS, pages 10688-10699, 2019.
11

---

[DKK20a] Ilias Diakonikolas, Daniel Kane, and Daniel Kongsgaard. List-decodable mean esti- mation via iterative multi-filtering. Proceedings of the 34th Annual Conference on Neural Information Processing Systems, 2020.
[DKK 20b] Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. A polynomial time algorithm for learning halfspaces with Tsybakov noise. CoRR, abs/2010.01705, 2020.
21K] Ilias Diakonikolas, Daniel Kane, Daniel Kongsgaard, Jerry Li. and Kevin Tian, List- decodable mean estimation nearly-pea time. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems, pages 10195-10208, 2021.
[DKK+21b] Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian. Clustering mixture models in almost-linear time via list-decodable mean estimation. CoRR, abs/2106.08537. 2021.
[DKK*22] Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, and Thanasis Pittas. List-decodable sparse mean estimation via difference-of- pairs filtering. CoRR, abs/2206.05245, 2022.
[DKS17] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, pages 73-84, 2017.
[DKS18a] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing, pages 1061-1073, 2018
[DKS18b] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 1047-1060. ACM, 2018.
[DKTZ20] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspaces with Massart noise under structured distributions. Proceedings of the 33rd Annual Conference on Learning Theory, pages 1486-1513. 2020.
[Don06] David L. Donoho. Compressed sensing. IEEE Transactions on Information Theory,
52(4): 1289-1366, 2006.
[Hau92] David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78-150, 1992.
[HLZ20] Samuel B. Hopkins, Jerry Li, and Fred Zhang. Robust and heavy-tailed mean estimation made simple, via regret minimization. CoRR, abs/2007. 15839, 2020.
[Hub64] Peter J. Huber. Robust Estimation of Location Parameter. The Annals of Mathematical Statistics, 35(1):73 - 101, 1964.
[KK]19] Sushrut Karmalkar, Adam R. Klivans, and Pravesh Kothari. List-decodable linear regression. In Proceedings of the 33rd Annual Conference on Neurul Information Processing Systems, pages 7423-7432, 2019.
[KMМ88] Adam R. Klivans, Pravesh K. Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regression. In Proceedings of the 31 Annual Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1420-1430. PMLR, 2018.
[KKMS05] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. In Proceedings of the 46th Annual IEEE Symposium Foundations of Computer Science, pages 11-20, 2005.
12

---

[KL88] Michael J. Kearns and Ming Li. Learning in the presence of malicious errors. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 267-280, 1988.
[KSS92] Michael J. Kearns, Robert E. Schapire, and Linda Sellie. Toward efficient agnostic learning. In Proceedings of the Fifth Anmual ACM Conference on Computational Learning Theory, pages 341-352, 1992.
[KSS18] Pravesh K. Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1035-1046, 2018.
[Lit87] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear- threshold algorithm. In Proceedings of the 28th Annual IEEE Symposium on Founda- tions of Computer Science, pages 68 77, 1987.
[LRV16] Kevin A. Lai, Anup B. Rao, and Santosh S. Vempala. Agnostic estimation of mean and covariance. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pages 665 674, 2016.
[LSLC20] Liu Liu, Yanyao Shen, Tianyang Li, and Constantine Caramanis. High dimensional robust sparse regression. In The 23rd International Conference on Artificial Intelligence and Statistics, volume 108 of Pruceedings of Machine Learning Research, pages 41 411-421. PMLR, 2020.
[LT91] Michel Ledoux and Michel Talagrand. Probability in Banach Spuces: Isoperimetry and Processes. Springer-Verlag Berlin Heidelberg, 1991.
[Ma13] Zongming Ma. Sparse principal component analysis and iterative thresholding. The Annals of Statistics, 41 4122)7722801,, 2013.
[MN06] Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, pages
2006.
[MV18] Michela Meister and Gregory Valiant. A data prism: Semi-verified learning in the small-alpha regime. In Proceedings of the 31st Conference On Learning Theory, pages 1530-1546, 2018.
[PV13] Yaniv Plan and Roman Vershynin. Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach. IEEE Transactions on Information Theory, 59(1):482-494, 2013.
[Y200a] Prasad Raghavendra and Morris Yau. List decodable learning via sum of squares. In Proceedings of the 2020 ACM-SIAM Symposium Discrete Algorithms, pages 161-180, 2020.
[RY20b] Prasad Raghavendra and Morris Yau. List decodable subspace recovery. In Proceedings of the 33rd Annual Conference on Learning Theory, pages 3206-3226, 2020.
[SCV18] Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: criterion for learning in the presence of arbitrary outliers. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference, pages 45:1 1-5:21, 2018.
[She20] Jie Shen. One-bit compressed sensing via one-shot hard thresholding. In Proceedings of the 36th Conference on Uncertainty Artificial Intelligence, pages 510-519, 2020.
[She21] Jie Shen. Sample-optimal PAC learning of halfspaces with malicious noise. In Pro- ceedings of the 38th International Conference Machine Learning, pages 9515-9524, 2021.
[SL17a] Jie Shen and Ping Li. On the iteration complexity of support recovery via hard thresholding pursuit. In Proceedings of the 34th International Conference on Machine Learning, pages 3115-3124, 2017.
13

---

[SL17b] Jie Shen and Ping Li. Partial hard thresholding: Towards a principled analysis of support recovery. In Proceedings of the 31st Annual Conference on Neural Information Processing Systems, pages 3127-3137, 2017.
[SL18) Jie Shen and Ping Li. A tight bound of hard threshokding. Journal of Machine Learning Research, 18(208):1 1-22, 2018.
[Slo88] Robert H. Sloan. Types of noise in data for concept learning. Proceedings of the First Annual Workshop on Computational Learning Theory, pages 91-96, 1988.
[STT12] Rocco A. Servedio, Li- Li-Yang Tan, and Justin Thaler. Attribute-efficient learning and weight-degree tradeoffs for polynomial threshold functions. In Proceedings of the 25th Annual Conference on Learning Theory, pages 1-19, 2012.
[SVC16] Jacob Steinhardt, Gregory Valiant, and Moses Charikar. Avoiding imposters and delinquents: Adversarial crowdsoureing and peer prediction. In Proceedings of the 30th Annual Conference on Neural Information Processing Systems, pages 4439 4447, 2016.
[SZ21] Jie Shen and Chicheng Zhang. Attribute-efficient learning of halfspaces with malicious noise: Near-optimal label complexity and noise tolerance. In Proceedings of the 32nd International Conference on Algorithmic Learning Theooy, pages 1072-1113, 2021.
[Tib96] Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society: Series B (Methodological) 58(1):267-288, 1996.
[Tuk60] John W. Tukey. A survey of sampling from contaminated distributions. Contributions to probability and statistics, pages 448 485, 1960.
[Va185] Leslie G. Valiant. Learning disjunction of conjunctions. In Proceedings of the 9th
International Joint Conference on Artificial Intelligence, pages 560-566, 1985.
[Wai19] Martin J. Wainwright. High-dimensional statistics; A non-asymptotic viewpoint. Cam- bridge University Press, 2019.
[WSL18] Jing Wang, Jie Shen, and Ping Li. Provable variable selection for streaming features. In Proceedings of the 35th International Conference Machine Learning, pages 5158-5166, 2018.
[ZS21] Shiwei Zeng and Jie Shen. Semi-verified learning from the crowd with pairwise comparisons. CoRR, abs/2106.07088 2021.
[ZS22] Shiwei Zeng and Jie Shen. Efficient PAC learning from the crowd with pairwise com- parisons. In Proceedings of the 39th International Conference Machine Learning, pages 25973-25993, 2022.
[ZSA20] Chicheng Zhang, Jie Shen, and Pranjal Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, pages 71 7184-7197, 2020.
14

---

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] See the appendix.
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 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]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're 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]
15


Reviews:
[{"review_id": "fyw3cJQeIAh", "reviewer": "Reviewer_yoWU", "summary": "The authors consider a mean-estimation problem for a sample with (adversarially) corrupted entries.  Assuming that the true mean is sparse, they provide an approximate algorithm, poly-logarithmic in dimension. The proof is based on the use of sparse polynomials.", "questions": "It is desirable to explain more about the novelty of the current work. This might includes heuristic ideas about how an efficient algorithm as proposed in the manuscript is available when the entries are corrupted.\nIs the key idea to use the Hermite basis?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: A concrete, efficient algorithm for the mean estimation is provided. The manuscript is generally well-written.\n\nWeaknesses: The novelty of the algorithm is not clearly explained. It is hard to grasp the improvement since it lacks the comparison with existing algorithms, especially numerical experiments.", "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": "ftDFbFtKV19", "reviewer": "Reviewer_7URr", "summary": "\nThe 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 an isotropic Gaussian 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 too large when the ambient dimension is too large. The paper constructs a polynomial-time estimator which achieves sample complexity $\\mathrm{poly} (k, 1 / \\alpha, \\log d)$ achieving recovery error of $1 / \\sqrt{\\alpha}$. While the recovery error and sample complexity are sub-optimal (one would expect information theoretic recover error arbitrarily close to $\\sqrt{\\log (1 / \\alpha)}$ and sample complexity $O(k \\log (d) / \\alpha)$), the number of samples is nearly independent of $d$. \n\nThe algorithm is based on the ``multi-filter'' framework for the list-decodable estimators. Intuitively speaking, one starts with a candidate set of good data points and infers one of the following:\n\n- The dataset is well behaved (typically in terms of its moments) and the empirical mean is a good estimate\n- Alternative, 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 one (when $\\alpha > 1/2$) or more (when $\\alpha < 1/2$) subsets of the original dataset which are better behaved.\n\nIn the multi-filter approach, care must be taken to ensure that we do not create too many datasets or more accurately, the sum of the number of points at any level of this iterative process remains bounded. At the conclusion of this process, the empirical means of all the refined datasets are returned as candidate in the returned list. In the standard list-decoding setting, the certificates belong to the unit vector along the sphere and signify directions along which moments (first and second) deviate significantly from their expected behavior. However, in the sparse setting, it suffices to check only sparse directions -- unit vectors which are $k$-sparse. Since searching for sparse violating directions is typically a hard problem, the paper instead searches for large entries in $\\hat{\\Sigma} - I$ and uses the $k^2$ largest entries to construct an appropriate certificate.\n\n**** POST REBUTTAL UPDATE ****\n\nThe authors have since updated the manuscript with improved results when higher order moments are available at the expense of increased computational and statistical complexity. I've updated my score to reflect these changes.", "questions": "Some explanation of the main technical contributions of the paper would be helpful with regards to prior work employing the multi-filter ([DKS 18] for instance). It would be great to have an intuition section detailing the key points of difference from prior work and where sparsity complicates the design of an effective multi-filter.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The design robust algorithms for the setting of sparse estimation is an important problem and the paper makes important progress in this direction conceptually matching the types of improvements that were previously obtained for sparse estimation. My main concern is the lack of technical novelty in the design of the estimator. The algorithmic approach and its subsequent analysis are based on a well-established framework and does not seem significantly novel. For instance, the key lemma (Lemma 12) controlling the behavior of the polynomials used to certify violating directions draw heavily from analogous results in [DKS 18]. Furthermore, the results obtained in the paper are sub-optimal both in terms of recovery guarantees and sample complexity even accounting for the conjectured statistical-computational gap at ($k$ vs $k^2$) for sparse estimation. Despite these drawbacks, the results in the paper are interesting and relevant and would be of interest to the theoretical machine learning and algorithms communities. ", "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": "Djyzc4Bizay", "reviewer": "Reviewer_zY2p", "summary": "The setup for list-decoding of mean estimation (no sparsity yet) is the following:\n\nThere is an unknown d-dimensional Gaussian G with mean mu and identity covariance, and an algorithm receives a set of n samples x_1,..., x_n with the promise that alpha * n of the samples are drawn from the unknown Gaussian. The task is to output a list of vectors hat{mu}_1, ..., hat{mu}_l such that one of them is close to mu.\n\nThe notable aspects of this setting is that alpha may be significantly smaller than 1/2, so that *most* of the dataset is actually adversarially corrupted. It turns out that the best one can hope for is to output this list of candidate means hat{mu}_1,..., hat{mu}_l, with l = O(1/alpha) such that at least one of them is close to mu. If we want our algorithm to be computationally efficient (i.e., run in time polynomial in the input -- which is sample size * d), then \"close\" to mu actually depends on alpha. \n\nThe first such results along these lines were from [Charikar, Steinhardt, and Valiant (CSV) '17] who got ~O(1/sqrt{alpha}) closeness, and then [Diakonikolas, Kane, Stewart (DKS) '18] improved the closeness parameter to O(1/alpha^{eps}), where the running time of the algorithm is a polynomial of degree O(1/eps). In this setup, the sample complexity is polynomial in d, so the resulting algorithms run in time which is polynomial in d.\n\nThis paper considers a very natural scenario, where d is very large, such that polynomial-in-d sample complexity is unacceptable. In this case, one needs an additional assumption on the underlying distribution, and the authors consider the case that mu is k-sparse. This is a very typical assumption to make, and the parametrization in terms of k leads to a sample complexity which is linear in k but logarithmic in d. Hence, the question is whether these list-decodable mean estimation algorithms can be made to run with only poly(k log d) samples. \n\nThe main result of this work is an algorithm for achieving this. For any alpha, an algorithm receives poly(k log d) samples, with the promise that an alpha-fraction of the samples come from an identity covariance Gaussian with mean mu which is k-sparse. The algorithm runs in time polynomial in the sample complexity and d, and outputs a list of O(1/alpha) candidate hat{mu}_1,..., hat{mu}_l where one of them is within O(1/sqrt{alpha}) from mu.\n\nAs the authors point out, it may be possible to use techniques from [DKS] to improve the error to O(1/alpha^{eps}) with algorithms whose running time is a polynomial in degree O(1/eps). \n\nThe approach that this work takes is the 'filtering' approach, which at a high level, proceeds in the following way. First, one comes up with a candidate list of subsets of samples. In each step, an algorithm will argue that either the empirical mean of the subset of samples is good enough for estimation, or else it can remove some samples from the set where the amount of 'false' samples (outliers) removed is much larger than true samples. While the paper proceeds in this approach, there are significant technical challenges in adapting the tools to this setting. Since the number of samples that we have is only poly(klog d), anything which we use samples to estimate will have an error on the order of 1/poly(k log d). The paper consider finding directions to filter outliers by only considering sparse polynomials. Another challenge is that one cannot iterate through all choices of k coordinates in [d], which causes additional technical difficulties.\n", "questions": "I don't think I have any particular questions. ", "limitations": "The limitations in the theorems are thoroughly discussed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nThis is a natural problem and follows a line of work on robust algorithmic statistics. The work is original and clear. It is significant that the techniques developed for 'dense' Gaussians can be adapted for a poly(k log d) dependence when including sparsity.\n\nWeaknesses:\n\nOne may consider that this paper leaves the question of 1/alpha^{eps}, involving techniques in [DKS] to future work. In that sense, the paper may be quickly improved.\n\n**** This has since been incorporated! While I cannot verify correctness of the change (I am not an expert in the area), I think that the contribution now contains all elements of a solid paper. The problem is natural, timely, and available avenues have been explored. Therefore, I am changing my score to accept.", "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