Robust Mixture Learning when Outliers Overwhelm Small Groups
Authors: Daniil Dmitriev
Rares-Darius Buhai
Stefan Tiegel
Alexander Wolters
Gleb Novikov
Amartya Sanyal
David Steurer
Fanny Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: robust statistics
mixture learning
list-decodable learning
small group
outliers
mean estimation
efficient algorithms
Primary area: learning_theory
TL;DR: Meta-algorithm for the mixture learning problem with guarantees for small groups in the presence of large additive adversarial contamination.

Abstract: We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fraction is significantly smaller than the minimum mixing weight, much less is known when outliers may crowd out low-weight clusters – a setting we refer to as list-decodable mixture learning (LD-ML). In this case, adversarial outliers can simulate additional spurious mixture components. Hence, if all means of the mixture must be recovered up to a small error in the output list, the list size needs to be larger than the number of (true) components. We propose an algorithm that obtains order-optimal error guarantees for each mixture mean with a minimal list-size overhead, significantly improving upon list-decodable mean estimation, the only existing method that is applicable for LD-ML. Although improvements are observed even when the mixture is non-separated, our algorithm achieves particularly strong guarantees when the mixture is separated: it can leverage the mixture structure to partially cluster the samples before carefully iterating a base learner for list-decodable mean estimation at different scales.

Robust Mixture Learning when Outliers Overwhelm Small Groups
Daniil Dmitriev
Rares-Darine Buhai
Stefan Tiegel
Alexander Wolters
Gleb Novikov
Amartya Sanyal
David Steurer!
Fanny Yang!
'ETH Zurich
2TU Munich
3 Lucerme School of Computer Science and Information Technology
UUniversity of Copenhagen
Equaa contribution
Abstract
We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fraction is significantly smaller than the minimum mixing weight, much less is known when outliers may crowd out low-weight clusters setting we refer to as list-decodable mixture learning (LD-ML). this case, adversarial outliers can simulate additional spurious mixture components. Hence, if all means of the mixture must recovered up to small error in the output list, the list size needs to be larger than the number of (true) components. We propose an algorithm that obtains order-optimal error guarantees for each mixture mean with minimal list-size overhead, significantly improving upon list-decodable mean estimation, the only existing method that is applicable for LD-ML. Although improvements are observed even when the mixture is non-separated, our algorithm achieves particularly strong guarantees when the mixture is separated: it can leverage the mixture structure partially cluster the samples before carefully iterating base learner for list-decodable mean estimation at different scales.
1 Introduction
Estimating the mean distribution from empirical data is one of the most fundamental problems in statistics. The mean often serves as the primary summary statistic of the dataset or is the ultimate quantity interest that often not precisely measurable. practical applications, data frequently originates from mixture of multiple groups (also called subpopulations) and natural goal is to estimate the distinct means each group separately. For example, we might like to use representative individuals study how complex decision procedure would impact different subpopulations. In other applications, such as genetics [1] or astronomy [2] research, finding the means themselves can be a crucial first step towards scientific discovery. In both scenarios, the algorithm should output list estimates that are close to the unobservable true means.
However, in practice, the data may also contain outliers, for example due to measurement errors or abnormal events. We would like find good mean estimates for all inlier groups even when the proportion of such additive adversarial contuminations is larger than some smaller groups that we want to properly represent. The central open question that motivates our work thus:
What is the cost of efficiently recovering small groups that may be outmumbered by outliers?
More specifically, consider scenario where the practitioner would like to recover the means of small but sigmificant enough inlier groups which constitute at least Woow E (0, 1) proportion of the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(corrupted) data. If k is the number of such inlier groups, for all E [K]], we then denote by w; b Wlow the unknown weight of the i-th group with mean H4. Further, we use to refer the proportion of additive contamination - the data that comes from an unknown adversarial distribution. The goal is to estimate the unknown means J4, for all i E [M)
Existing works on robust mixture learning such as [3, 4] consider the problem when the fraction of additive adversarial outliers smaller than the weight of the smallest subgroup, i.c. whow However, for large outlier proportions where > Wlow. these algorithms are not guaranteed to recover small clusters with w, & E. In this case, outliers can form additional spurious clusters that are indistinguishable from small inlier groups. As a consequence, generating a list of size equal to the number of components would possibly lead to neglecting the means of small groups. In order to ensure that the output contains a precise estimate for each of the small group means, it is thus necessary the estimation algorithm to provide a list whose size is strictly larger than the number of components, We call this paradigm list-decodable mixture learning (LDD-LL), following the footsteps of a long line of work on dist-decodable learning (see Sections 2 and 5).
Specifically, the main challenge in LD-ML is to provide a short list that contains good mean estimates for all inlier groups. We first note that there is minimum list size the algorithm necessarily has to output to guarantee that all groups are recovered. For example, consider an outlier distribution that includes several copies of the smallest inlier group distribution with means spread out throughout the domain. Since inlier groups are indisntinguishable from spurious outlier ones, the shortest list that includes means of all inlier groups must be of size least | > k + min, wi Here, min, w. can be interpreted as the minimal list-size overhead that is necessary due to "caring" " about groups with weight smaller than e. The key question is hence how good the error guarantees of an LD-ML algorithm can be when the list size overhead stays close to min an; while being agnostic to w; aside from the knowledge of Wlow. Furthermore, we are interested in computationally efficient algorithms for LD-ML, especially when dealing with high- nigh-dimensional data.
To the best of our knowledge, the only existing efficient algorithms that are guaranteed to recover inlier groups with weights w; & & are list-decodable mean estimation (LD-ME) algorithms. LD-ME algorithms model the data as a mixture of one inlier and outlier distribution with weights a き 1/2 and 1 - a respectively. Provided with the weight parameter a. they output a list that contains an estimate close to the inlier mean with high probability. However, for the LD-ML setting, the inlier weights w; are not known and we would have to use LD-ME algorithms with Wlow as weight estimates for each group. This leads suboptimal error in particular for large groups, that hence (somewhat counter intuitively) would have to "pay" for the explicit constraint to recover small groups Furthermore, even if LD-ME were provided with w;. by design it would treat inlier points from other components also as outliers, unnecessarily inflating the fraction of outliers to 1 - wy instead of e.
Contributions In this paper, propose an algorithm that (i) correctly estimates the weight of each component only given a lower bound and (ii) does not overestimate proportion of outliers when components are well-separated. In particular, we construct meta-algorithm that uses mean estimation algorithms as base learners that are designed to deal with adversarial corruptions. This meta-algorithm inherits guarantees from the base learner and any improvement of the latter translates to better results for LD-ML. For example, if the base learner runs in polynomial time, so does our meta-algorithm. Our approach of using the output of weak base learners achieve better performance is reminiscent of the boosting paradigm that is common in machine learning practice.
Our algorithm achieves significant improvements in error and list-size guarantees for multiple settings. For ease of comparison, we summarize error improvements for inlier Gaussian mixtures in Table 1 (see Theorem 3.3 for the general result regarding distributions with bounded moments). The main focus of our contributions is represented in the second row; that is the setting where outliers outnumber some inlier groups with weight wy < and the inlier components are well-separated
ie., || 14 2' Vlog Whow where μ4 's are the inlier component means. As we mentioned before, robust mixture learning algorithms, such as [4, 7], are not applicable here and the best error guarantees in prior work is achieved by an LD-ME algorithm, e.g. from [3]. While its error bounds are of order
O log Wlow for list size of O Wjow ) our approach guarantees error O( Vlo log = ) for list size
We adopt the following standard notation: f& 9. 0(g), and g R2ff) mean that f & Cg for some universal constant C > 0. O-notation hides polylogarithmic terms.
2

---

Type of inlier mixture
Best prior work Ours
Inf.-theor. lower bound
Large (Vj E < wy), sep. groups ((e/ws)
Ö(E/wa)
A(E/w;), see [5]
Small (3j é > wj). sep. groups
log
log Etaer
Shtw Ω2 log
Prop. 3.5
wlow
wy
mi
Non-separated groups
log
O
log
log
see [6]
Whow
Table 1: For a mixture Gaussian components N(j;; fa), we show upper and lower bounds for the error of the iccoppoeent given a output list L (of the respective algorithm) mingez / -u:ll- When the error doesn't t depend on i, all means have the same emror guarantee irrespective of their weight. Note that depending on the type of inlier mixture, different methods in [3] are used as the 'best prior work': robust mixture learning for the first row and list-decodable mean estimation for the rest.
of l: + O (..)) Remarkably, we obtain the same error guarantees as if an oracle would run LD-ME Whow
on each inlier group with the correct weight w; separately (with outliers). Hence, the only cost for recovering small groups the increased list-size overhead of order O Www ). Further, a sub-routine in our veta-allorithm also obtains novel guarantees under no separation assumption, as shown in the third row of Table 1. This algorithm achieves the same error guarantees for similar list size as a base learner that knows the correct weights of the inlier components.
Based on a reduction argument from LD-ME to LD-ML,, we also provide information-theoreti (IT) lower bounds for L.-ML.. If the LD-ME base learners achieve the IT lower bound (possible for inlier Gaussian mixtures), so does our LD-ML algorithm. In synthetic experiments, we implement our meta-algorithm with the LD-ME base learner from [8] and show clear improvements compared the only prior method with guarantees, while being comparable or better than popular clustering methods such k-means and DBSCAN for various attack models.
2 Settings
We now introduce the learning settings that appear in the paper. Let d E N.+ be the ambient dimension of the data and i E N4 be the number of mixture components (inlier groups/clusters).
2.1 List-decodable mixture learning under adversarial corruptions
We focus on mixtures that consist of distributions that are sufficiently bounded in the following sense. Definition 2.1. Let t E N+ be even and let D(4) be a distribution on IRd with mean μ.. We say that ((u) has sub-Gaussian I-th central moments if for all even < l and for every v E Rd with ||ا||| 1, Ez~D (x u, < (s 1)!!.
This class of distributions is closely related commonly studied distributions in the literature (see, e.g., (5)) with bounded (-th moment. Our requirement for the boundedness of all moments & < t stems from the fact that our algorithm should adapt to unknown and possibly non-uniform mixture weights.
We assume that are given samples from corrupted d-dimensional mixture of k inlier distributions Da(ws) satisfying Definition 2.1, where the mixture is defined as
X = Σ w. w.(s)) +EQ,
(2.1)
1=1
and Σ w; + 1, where for all L....,K,, k. it holds that we > Wlow Further, an E > proportion of the data comes from an outlier distribution Q chosen by the adversary with full knowledge of our algorithm and inlier mixture. Samples drawn from D; (14) constitute the gth inlier cluster. The goal in mixture learning under corruptions as in Eq. (2.1), is to design an algorithm that takes in i..d. samples from X and outputs a list L, such that for each í E [k], there exists ja E L with small estimation error || Al|-
To the best of our knowledge, we are the first to study the list-decodable mixture learning problem (LD-ML) that considers the case of large fractions of outliers E 2e min, Wi and the goal is to achieve
3

---

small estimation errors while the list size [ remains small. While in robust estimation problems, the fractions of inliers and outliers are usually provided to the algorithm, in mixture learning, the mixture proportions are explicit quantities of interest. Throughout the paper, we hence assume that both the true weights w; of the mixture and the fraction of outliers & are unknown. Instead, by definition in Eq. (2.1), we assume knowledge of valid lower bound Whow < min; W4.
Note that when E X min; wi, the problem is known as robust mixture learning and can be solved with list size |2| = k as discussed in [3, 7J. However, algorithms for robust mixture learning fail when the fraction of outliers becomes comparable the inlier group size. In the presence of "spurious" adversarial clusters, it is anformation-theoreieee
impossible to output list L, such that (i) [ k and (ii) L contains precise estimate for each true mean.
2.2 Mean estimation under adversarial corruptions
In order to solve LD-ML, we use mean estimation procedures that have provable guarantees under adversarial contamination. Mean estimation can be viewed as a particular case of the mixture learning problem in Eq. (2.1) with i = 1, the fraction of inliers a = W1 and the fraction of outliers & = 11 a. The mean estimation algorithms we use to solve LD-ML with Woow need exhibit guarantees under stronger adversarial model, where the adversary can also replace a small fraction (depending on Wlow) of the inlier points; see details in Definition B.I. This is a special case of the general contamination model as opposed to the slightly more benign additive contamination model in Eq. (2.1). For different regimes of a we use black-box learners that solve corresponding regime when provided with a.
Robust mean estimation When the majority of points are inliers, we are the RME setting. Robust statistics has studied this setting with different corruption models and efficient algorithms are known to achieve information- theoreiicly optimal error guarantees (see Section 5).
List-decodable mean estimation When inliers form a minority, we are in the list-decodable setting and are required to return a list instead of single estimate. We refer to this setting cor-kLD (corrupted known list-decoding). For mixture learning, a is usually unknown and we need to solve the cor-aLD (corrupted agnostic list-decoding) problem (i.e., a is not provided, but instead a lower bound Kloow E [Woow: a] is given to the algorithm). Finally, when only additive adversarial contamination is present, as in Eq. (2.1), we recover the standard list-deooding setting studied in prior works (see Section 5) that we call sLD (simple dist-decoiing. In Appendix we show that two algorithms designed for sLD also exhibit guarantees for cor for any Wlow
3
Main results
We now present our main results for list-decodable and robust mixture learning defined in Section 2. In Section 3.1, we provide algorithmic upper bounds and coammation-theoreete lower bounds. For the special case of spherical Gaussian mixtures, we show in Section 3.1 that we achieve optimality. Our results are constructive as we provide a meta-algorithm for which these bounds hold.
As depicted in Figure 1, our meta-algorithm (Algorithm 2) is two-stage process. The outer stage (Algorithm 6) reduces the problem to mean estimation by leveraging the mixture structure and splitting the data into small collection J of sets T. Each set T E T should (i) contain at most one inlier cluster (and few samples from other clusters) and (ii) the total number of outliers across all sets should be most O(En). We then run the inner stage (Algorithm 3) on sets T, which outputs mean estimate for the inlier cluster in T. First, a cor-aLDD algorithm identifies the weight of the inlier cluster and returns the result of cor-kLD base learner with this weight. Then, if the weight is large, we improve the error via an RME base learner. A careful filtering procedure in both stages achieves the significantly reduced list size and better error guarantees. We require the base learners to satisfy the following set of assumptions.
Assumption 3.1 (Mean-estimation base learners for mixture learning). Let be an even integer and consider the corruption setting defined in Definition B.I. Further, let the inlier distribution D(=") E DD where D is the the family of distributions satisfying Definition 2.1 for We assume that

---

Base cor-kI. Algorithm
Outer stage (Algorithm 6): creates collection T of sets 7'
Inner stage (Algorithm 3): for each in J:
Run algorithm for cor-aLD
Base RME Algorithm
2. Improve errors if possible
Figure 1: Schematic of the meta-algorithm (Algorithm 2) underlying Theorem 3.3
(a) for a E [Woow 1/3] in the cor-kLD regime, there exists an algorithm ALLD that uses NLD(a) samples and (a) time to output list of size bounded by 1 1/(0(1)) that with probability at least 1/2 contains some j with | 1='l I| < f(()., where f non-increasing.
(b) for a E - ERME, 1]. with & ERME & 1/2 2w/fow in the RME regime, there exists an RME algorithm A that uses Na(a) samples and 7 Tn(()) time to output with probability at least 1/2 some j with || - 1='| < g(a), where y is non-increasing.
Note that the sample and time complexit functions such NLD and TLD. might depend f, for example growing as d'. We emphasize that (i) the guarantees our meta-algords altttartggimtmm depend on the guarantees of the base learners and (ii) only require the base learners to work in the well- studied setting with known fraction of inliers. Corollary 3.4 uses known base learners for Gaussian distributions achieving ceemmation-thorreicall optimal error bounds. There also exists base learners for distributions beyond Gaussians, such as bounded covariance or log-concave distributions, see, e.g. [9].
3.1 Upper bounds for list-decodable mixture learning
Key quantities that appear our error bounds are the relative proportion of inliers wi and outliers ē;;
Wi + + W
and E Wi. low
(3.1)
These quantities reflect that each set T the inner stage contains at most one inlier cluster and a small (S w fraction of points from other inlier clusters. We present simplified version of our main result in Theorem 3.3 (see Theorem C. for the detailed result) that allows for a more streamlined presentation of the results using the following well-behavedness' of f and g.
Assumption 3.2. Let f. g be defined in Assumption 3.1. For some C 0, we assume (i) ERME > 0.01, (ii Væ E (0, 1/3], (x/22 & Czx)), and (iii) Vr [0.99, 1], g(x (1 x)² & Cg(x).
We ready state the main result of the paper.
Theorem 3.3. Let d, k E N+, Wlow (0, 1/2). and be even integer. Let X. be a d-dimensional mixture distribution following Eq. (2.1). Let ARLD and A satisfy Assumptions 3.1 and 3.2 for some even t. Further, suppose that [|m, - pyl Z ff(1/W/ow) 44/t + of f( ( for all + E [k]]
Then there exists an algorithm that, given poly(d, 1 1/Wrow) (Nr.D ples from X as well d, k. Whow, and
N +-NR(WoW)) ii.d sam in time poly d, 1/ h/Wlow) (TI.D(Wlow) Tnl (R((Wo)))
O(1) outputs a list L of size [L] < k O(E/Wroow where, each and with probability at least low
i [k),, there exists jo L such that
A 10-+1= =0
min (F(L/O)) + f (w 1/3))) 1gt
the relative weight of the i-th cluster large, i.e., 6, 0.001, then the error is further bounded by
|| p O (g(ww)).
The proof together with a more general statement, Theorem C.1, can be found in Appendix C. Note that for mixture setting with l: > 2, the assumption Whow & 1/k & 1/2 is automatically fulfilled. Also, for large weights W; such that log(1/ (1/t;;) < t, the t' that minimizes (1/ is smaller than f, and for small weights the minimizer L! =
5

---

Gaussian case For Gaussian inlier distributions, LD-ME and RME base learners with guarantees for Assumption 3.1 have already been developed in prior work. We can thus readily use them in the meta-algorithm to arrive at the following statement with the relative proportions defined in Eq. (3.1).
Corollary 3,4 (Gaussian case). Let d, le, Wlow and z be as in Theorem 3.3. Let X be as in Eq. (2.1) with Di(H,) = N(u La) with Ju, 's satisfying l|m4 - Hyyl 2 Vlog L/Wlow for all + E [k]]. There exists an algorithm that for (log 1/Wlow): given = poly [1/Wwe)) i.i.d. samples from X and Wlow. runs in Poly(N) time and outputs list L such that with high probability [L] = k+ (E/WWww) and, for all i E [kl, there exists jo E L such that
lla - mill - O (Vlog1/ui)
If the relative weight of the i-th cluster is large, i.e. Es & 0.001, then the error is further bounded by
11 pall = O (E: (ov/oo//E))
Proof.
Theorem 6.12 from [5] provides an LD-ME algorithm ALLD achieving error f(a) &
O( O(VE(1/a))*) for all t' & t. The sample and time complexity scale poly(d', (1/a))). Also, Theorem 5.1 from [10] provides a robust mean estimation algorithm Ar such that for a small enough constant fraction of outliers ε
1/(1- a achieves error g(a) = O((1 - ar) /lgg/1 - a)) with sample complexity $t(d/=9). Using these ALLD and AR. we recover the desired bounds.
Comparison with prior work We now compare our result with the only previous method that can achieve guarantees in the LD-ML setting with unknown utg. As discussed in [3], algorithms for the simple list-decoding model with a = Wlow can be used for LD-ML by viewing single mixture component as the "ground truth" distribution and effectively treating all other inlier components and original outliers as outliers. Besides requiring a much larger list size of O
///ww/)w) >> k ((e/W)ow) and error O Tog 1/ 1/Wlow), this approach has two drawbacks that manifest in the suboptimal guar-
antees: 1) For larger clusters i with ue >> Wlow LD-ME only achieves an error O (Vlog 1/ 1/unow)
Our result, even without separation assumption, achieves a sharper error bound O Vlog 1/ws) 2)
When the mixture is separated, LD-ME cannot exploit the structure since it still models the data as Noo,, Ia) + (I Whow QQ for each i, so that the algorithm inevitably treats all other true components as outliers. This results in the error O ( (VlogL/ L/Wlow > O (Vlog L/ = O(1)
(when e w; < 1). We refer to Appendix A for further illustrative examples. As simple example, consider the uniform inlier mixture with 5 = wi = 1/(k + 1), where k is large. In this case, previous results have error guarantees O F), while we obtain error (1))
Separation assumption For the problem of learning mixture models, a separation assumption is common in the literature [3, 9, 11, 12]. We require separation 1|/4- - 1 2 v((1 /((1/W//w) h///////////////// /42, which we believe to be sub-optimal for the case of finite t. In cases when is small (namely S W]oo), there cxist prior works on clustering allowing smaller separation. Specifically, when t = 2, a recent work [13] only requires [|p. M l| 2 1/ W/ For general t >> 4, [9] succeeds under separation (//low)2t
/2/t, We leave the possible relaxation of the separation requirement in the case of general / and large e for the future work.
In the Gaussian case we require separation || -1yl 2 Vlog 1/ 1//wows which is optimal in the uniform (w; 1/k) case. Indeed, without the separation assumption, even in the noiseless uniform Gaussian case, [6] shows that no efficient algorithm can obtain error asymptotically better than 2( ([VTo 1/m=)) In Corollary B.5, we prove that the inner stage (A (Algorithm 3) of our algorithm, without knowledge of w; and separation assumption, achieves with high probability matching error guarantees O O(Vlog 1/w:) with list size bounded by 0(1 (.]
3.2 Information-thhoretiin lower bounds and optimality
Next, we present information- -hooomtttoonthoortticalll lower bounds for list-decodable mixture learning on well- separated distributions X as defined in Eq. (2.1). We show that our error is optimal as long as the list size is required to be small. Our proof uses a simple reduction technique and leverages established lower bounds in [3] for the list-decodable mean estimation model (sLD in Section 2).

---

Algorithm Outer stage, informal (see Algorithm 6)
Input: X, Wlows A, and sLD algorithm ALLD-
Output: Collection of sets J.
1: L f- (ØI..... f = (X) with Wlowi
2: while L + 0 do
3: for j I. do
4:
compute for an appropriate distance function d
$ {ar E X d(a, ()) < A}, s/8 far E d(r, 34}
5: if for all n. 1 > 2|5 then add X to T and update L t- 0
6:
else
1 | |
7:
< argmax
8: add ( To
X t X ((1)
9:
10: return
Proposition 3,5 (Information-uee thhooretict lower bounds). Let A be an algorithm that, given access to X, outputs list L that, with probability > 1/2, for each E [K]] contains j L with 1 pill & B.
(a) Consider the case with ll, - Myll 2 (1/woow) ) /112 for i + E [R)] D.(p.) having t-th bounded Gau-saann central moments and Bi < C(1/woow) 1/t for each E [k). for some [kc] it holds
that w, & E, then algorithm A must either have error bound Bg (2((1 ūi, 1/t)) or [ > k + d 1.
(b) Consider the case with ||s - Myll 2 Vlog 1/ L/Wlow for + j E [k], D((H)) = N(u, Ia) and 3 & Co/log 1/ Whow for each i E [Rc]. If for some E [k]] it holds that w, & then algorithm A must either have error bound Bg 2 Vivoolog 1 1/0s;) or [L] > k + min(20(d) min((
In the Gaussian inlier case, Corollary 3.4 together with Proposition 3.5 imply optimality of our meta-algorithm. Indeed, if one plugs in optimal base learners (as in the proof of Corollary 3.4), we obtain error guarantee that matches lower bound, In particular, "exponentially" larger list size is necessary for asymptotically smaller error. For inlier components with bounded aub-Gaussian moments, [3] obtains information thhortiiitt (nearly-)optimall LD-ME base learners.
Furthermore, in [3], formal evidence of computational hardness was obtained (see their Theorem 5.7, which gives a lower bound in the statistical query model introduced by [14]) that suggests obtaining error $2, ((1 //t) requires running time least df((), This was proved for Gaussian inliers and the running time matches ours up to constant in the exponent.
4 Algorithm sketch
We now sketch our meta-algorithm specialized to the case of separated Gaussian components N(u,, Ia) and provide intuition for how it achieves the guarantees in Corollary 3.4. In this section, we only discuss how to obtain an error of O /log 1/w,, for each mean when 2 min, wi, We refer to Appendix D for how to achieve the refined error guarantee of OEEy/log 1/E,) when E is small.
As discussed in Section 3.1, running out-of-the-boo LD-ME algorithm for the sLD problem on our input with parameter a = Whow would give sub-optimal guarantees. In contrast, our two- stage Algorithm 2, equipped with the appropriate cor-kI. and RME base learners depicted in Figure 1, obtains for each component an error guarantee that is as good as if we had access to the samples only from this component and from the outliers. We now give more details about the outer stage, Algorithm 1, and inner stage, Algorithm 3, and describe on a high-level how they contribute to a short output list with optimal error bound in Corollary 3.4 for large outlier fractions.
4.1 Inner stage: list-decodable mean estimation with unknown inlier fraction
We now describe how to use black-box cor-kID algorithm to obtain a list-decoding algorithm A&LD for the cor-aLD mean-estimation setting with access only to anow & AaLD is used
7

---

in the proof of Corollary B.5 and plays crucial role (see Figure 1) in our meta-algorithm. In particular, it deals with the unknown weight of the inlier distribution in each set returned by the outer stage. Note that estimating a from the input samples is impossible by nature. Indeed, we cannot distinguish between potential outlier clusters of arbitrary proportion & 1- a and the inlier component. Underestimating the size of a large component would inevitably lead to suboptimal error guarantee. We now show how to overcome this challenge and achieve an error guarantee Of O[ylog 1/ax) for list size + O((1 - a) /lo/)w)) for the cor-aLD setting. Here we only outline our algorithm and refer to Appendix D for the details.
Algorithm 3 first produces large list of estimates corresponding to many potential values of a and then prunes it while maintaining good estimate in the list. In particular, for each & E A == (low) J. we run ALLD with parameter to obtain a list of means. We {Olow, 20lu::.00w....... L 13((3)
append á to each mean in the list and obtain list of pairs (f, a). We concatenate these lists of pairs for all ā and obtain list L of size (1/a2)ow) By design, one element of A is close the true a, so O(ylog
the list I contains at least one ja that is O( /lo //co--llsee - the error guarantee that we aim for and there is indeed least an a-fraction of samples near j.. We call such hypothesis "nearby".
Finally, we prune this concatenated list by verifying for each f whether there is indeed an å-fraction of samples "not too far" from it. This is similar to pruning procedures with known a proposed in prior work (see Proposition B. in [3]). Our procedure (i) never discards a "nearby" hypothesis, and outputs list where (ii) every hypothesis contains sufficient number of points close to it and (iii) all hypotheses are separated. Property (i) implies that the final error is O( / log L/a) and properties (ii) and (iii) imply list size bound + O(11 - a)/ Mow Note that when a < Olww the list size can be simply upper bounded by ((1 [1//ww)), see Remark B.4.
4.2 Two-stage mela-algorithm
Even though we could run A&LD on the entire dataset with alow = Wlows we would only achieve an error for the 7th inlier cluster mean of ((ylog 1/w;) which can be much larger than O /log 1/x;;) for list of size O(1 (1/Wwww). While A&LD takes into account the unknown weight of the clusters, still treats other inlier clusters as outliers. We now show that if the outer stage Algorithm 1 of weta-algorithm Algorithm 2 separates the samples into not-too-large collection T of sets with certain properties, running ALLD separately on each of the sets can lead to the desired guarantees. In particular, let us assume that T consists of potentially overlapping sets such that:
(1) For each inlier cluster C*, there exists one set T E T such that T contains (almost) all points from C' and most (En) other points,
(2) It holds that Σrer [T] < n + O(e)).
By (1), for every inlier cluster C* with a corresponding true weight w", there exists a set T such that the points from C* constitute least an li-fraction of T with == 2(w"" /ww" +E)). By Section 4.1, applying A&LD with Klow = Woow n1/ [T] on such a T then yields list of size 1 + ++1 - W with estimation error at most O / log 1/w).. If contains (almost) no inliers, that is, there is no inlier component that should recovered, then ARLD returns a list of size
Now, by the two properties, (almost) all inlier points lie in at most k sets of T, and all other sets of T contain in total most (en) points. Hence, concatenating all lists outputted by A&LD applied to all T E TJ leads to a final list size bounded by k + (EE/ //)))
4.3 Outer stage: separating inlier clusters
We now informally describe the outer stage that produces the collection of sets with the desiderata described in Section 4.2, leaving the details to Appendix E. The main steps are outlined in pseudocode in Algorithm
Given a set X of N = poly (d', 1//woow/ i.i.d. input samples from the distribution Eq. (2.1) with Gaussian inlier components, the first step of the meta-algorithm is to run Algorithm on X and Wlow with A O( D(v/og 1/Wlow). Algorithm 1 runs an sLD algorithm the samples and produces (large) list of estimates such that, for each mean, at least one estimate O 1 1/WWoow) to it. It then add sets to T that correspond to these estimates via a dynamic "two-scale" process.
8

---

Specifically, for each j E L, we construct two sets 1 C c consisting of samples close to jr. By construction, we guarantee that if ( contains non- negligiileble fraction of samples from any inlier cluster C", then / contains (almost) all samples from C* (see Theorem B.7 (ii)).
Now we very briefly illustrate how this process could be helpful in proving properties (1) and (2). Observe that, long as there exists some j with [ 2|5 we add s(²) to T and remove the samples from 1 Consider one such P.. For property (1), we merely note that if / contains &
part of an inlier cluster C*, then s(2) contains (almost) all of C", so we add a set that contains (almost) all of C*; otherwise, when we remove i (almost) all the points from C* remain in play. For property (2), we merely note that whenever we add S ((2) to T, increasing the number of points in it by |s(2),, we also remove the samples from ( reducing the number of samples by /s > 1/2. The proof of the properties uses some additional arguments of similar flavor, and we defer it to Appendix E.
s(a) we remove (almost) no points from C", so
5 Related work
List-decodable mean estimation Inspired by the list-decoding paradigm that was first introduced for error-correcting codes for large error rates [15]. list-decodable mean estimation has become popular approach for robustly learning the mean of a distribution when the majority of the samples are outliers. long line of work has proposed efficient algorithms with theoretical guarantees. These algorithms are either based on convex optimization [9, 16), a filtering approach [3, 17]. or low-dimensional projections [18]. Near-linear time algorithms were obtained in [19] and [8]. The list-decoding paradigm is not only used for mean estimation but also other statistical inference problems. Examples include sparse mean estimation [20, 21], linear regression [22-24], subspace recovery [25, 26), clustering [27], stochastic block models and crowd sourcing [16, 28).
Robust mean estimation and mixture learning When the outliers constitute a minority, algorithms typically achieve significantly better error guarantees than in the list-decodable setting. Robust mean estimation algorithms output a single vector close to the mean the inliers. In a variety of corruption models, efficient algorithms are known to achieve (nearly) optimal error
Robust mixture learning tackles the model in Eq. (2.1) with E < min, w, and aims to output exactly vectors with an accurate estimate for the population mean of each component [3, 4, 7, 11, 13, 29, 30]. These algorithms do not enjoy error guarantees for clusters with weights w/ < E. To the best of our knowledge, our algorithm is the first to achieve non-trivial guarantees in this larger noise regime.
Robust clustering Robust clustering [31] also addresses the presence of small fractions of outliers in similar spirit to robust mixture learning, conceptually implemented in the celebrated DBScan algorithm [32]. Assuming the output list size is large enough to capture possible outlier clusters, these methods may also be used to tackle list-decodable mixture learning however, they do not come with an inherent procedure to determine the right choice of hyperparameters that ultimately output a list size that adapts to the problem.
6 Discussion and future work
In this work, we prove that even when small groups are outnumbered by adversarial data points, efficient list-decodable algorithms can provide an accurate estimation of all means with minimal list size. The proof for the upper bound is constructive and analyzes plug-and-play meta-algorithm (cf. Figure 1) that inherits guarantees of the black-box cor- algorithm A&LD and RME algorithm AR. which it uses base learners. Notably, when the inlier mixture is a mixture of Gaussians with identity covariance, we achieve optimality. Furthermore, any new development for the base learners automatically translates to improvements in our bounds.
We would like to end by discussing the possible practical impact of this result. Since an extensive empirical study is out of the scope of this paper, besides the fact that ground-truth means for unsu- pervised real-world data are hard to come by, we provide preliminary experiments on synthetic data. Specifically, we generate data from separated --Gusssian mixture with additive contaminations as in Fq. (2.1) and different types of adversarial distributions (see detailed description in Appendix I). We focus the regime& ~ wi where our algorithms shows the largest thcoretical improvements.

---

Kmeans
Robust Kmeans
DBScan
LD-ME
Ours
15.0
30
Worst Estimation Ener
12.5
25
10.0
20
7.5
15
5.0
10-
2.5
0.0
Attack
Attack
Attack
Noise Models
Noise Modell
Figure 2: Comparison of five algorithms with two adversarial noise models. The attack distributions and further experimental details are given in Appendix I. On the left we show worst estimation error for constrained list size and the right the smallest list size for constrained error guarantee. We plot the median of the metrics with the error bars showing 25th and 75th percentile.
50
LD-ME
Ours
Worst Estimation Error
0.7
LD-ME
Ours
40
0.6
Size
30
List
20
0.3-
0.2
Wiow
Wiow
Figure 3: Comparison of list size and estimation error for large inlier cluster for varying Wlow inputs. The experimental setup illustrated in Appendix We plot the median values with error bars showing 25th and 75th quantiles. As Wlow decreases, we observe a roughly constant estimation error for our algorithm while the error for LD-ME increases. Further, the decrease in list size much more severe for LD-ME than for our algorithm.
We then compare the output of algorithm with the vanilla LD-ME algorithm from [8] with Whow = 0.02 and (suboptimal) LD-ML. guarantees as well as well-known (robust) clustering heuristics without LD-ML guarantees, such as the k-means [33], Robust k-means [34], and DBSCAN [32]. Even though none of these heuristics have LD-ML guarantees, they are commonly used and known also perform well practice in noisy settings. In Figure 2 (left), we fix the list size 10 and plot the errors for the worst inlier cluster, typically the smallest. We compare the performance of the algorithms by plotting the worst-case estimation errors for given list size and list sizes that algorithms require to achieve given worst-case estimation error. In Figure 2 (right), we fix the error and plot the minimal list size which competing algorithms reach the same smaller worst estimation error. Further details the experiments are provided in Appendix I. In different experiment (see Figure 3 and Appendix for details), we observe that our approach outperforms LD-ME when Wlow varies, both in achieving smaller list size and smaller estimation error.
Overall, in line with our theory, our method significantly outperforms the LD-ME algorithm, and performs better or on par with the heuristic approaches. Additional experimental comparison and implementation details can be found in Appendix I. Even though these experiments do allow conclusive statements about the improvement of our algorithm for mixture learning for real- world data, they do provide encouraging evidence that effort could well-spent on follow-up empirical and theoretical work building on our results. For example, it would be interesting to conduct more extensive empirical study comparing our algorithm with a variety of robust clustering algorithms. Additionally, practical data often contains components with varying scales. An interesting direction for future work could be to extend our algorithm to handle differently sealed covariances in an agnostic manner.
10

---

Acknowledgements
DD is supported by ETH AI Center doctoral fellowship and ETH Foundations of Data Science initiative. RB, ST, GN, and DS have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 815464).
References
[1] David R Bickel. Robust cluster analysis of microarray gene expression data with the number of clusters determined biologically. Bioinformatics, 19(7):818 1224,,,8822120 2003.
[2] Eric D Feigelson and G Jogesh Babu. Statistical methods for astronomy. arXiv preprint arXiv:/205.206: 2012.
[3] 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 on Theory of Computing, pages 1047-1060, 2018.
[4] Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M Kane, Pravesh K Kothari, and Santosh S Vempala. Robustly learning mixtures of k arbitrary Gaussians. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 1234 1247, 2022.
[5] Ilaas Diakonikolas and Daniel M Kane. Algorithmic high-dimensional robust statistics. Cam- bridge University Press, 2023.
[6] Oded Regev and Aravindan Vijayaraghavan. On learning mixtures of well-separated Gaussians. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 85-96. IEEE, 2017.
[7] Misha Ivkov and Pravesh K Kothari. List-decodable covariance estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1276-122 2022.
[8] Iaass Diakonikolas, Daniel Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian. Clustering mixture models in almost-linear time via list-decodable mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1262-1275, 2022.
[9] 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.
[10] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742-864, 2019.
[11] Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1021-1034, 2018.
[12] Allen Liu and Jerry Li. Clustering mixtures with almost optimal separation in polynomial time. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1 1248-1261, 2022.
[13] Ilias Diakonikolas. Daniel M Kane, Jasper CH Lee, and Thanasis Pittas. Clustering mixtures of bounded covariance distributions under optimal separation. arXiv preprint arX1v:2312.11769, 2023.
[14] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):83-11066 1998.
[15] Peter Elias. List decoding for noisy channels. Technical report, Research Laboratory of Electronics, Massachusetts Institute of Technology, 1957.

---

[16] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, pages 47-60, 2017.
[17] Ilass Diakonikolas, Daniel Kane, and Daniel Kongsgaard. List-decodable mean estimation via iterative multi-filtering. Advances in Neural Information Processing Systems, 33:9312-998 1--323,, 2020.
[18] Ilias Diakonikolas, Daniel Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian. List-decodable mean estimation in nearly-PCA time. Advances in Neural Information Processing Systems, 34:10195-10208, 2021.
[19] Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. List decodable mean estimation nearly linear time. In 2020 IEEE 6/st Annual Symposium on Foundations of Computer Science (FOCS), pages 141-148. IEEE, 2020.
[20] Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Ankit Pensia, and Thanasis Pittas. List- decodable sparse mean estimation via difference-of-pain filtering. Advances in Neural Informa- fion Processing Systems, 35:13947-13360, 2022.
[21] Shiwei Zeng and Shen. List-decodable sparse mean estimation. Advances in Neural Information Processing Systems, 55:24031-240455 2022.
[22] Sushrut Karmalkar, Adam Klivans, and Pravesh Kothari. List-decodable linear regression. Advances in Neural Information Processing Systems, 32, 2019.
[23] Prasad Raghavendra and Morris Yau. List decodable learning via sum of squares. In Proceedings of the Fourteenth Annual ACM-SIAM Symposiun on Discrete Algorithms, pages 161-180. SIAM, 2020.
[24] Ilias Diakonikolas, Daniel Kane, Ankit Pensia, Thanasis Pittas, and Alistair Stewart. Statistical query lower bounds for list-decodable linear regression. Advances in Neural Information Processing Systems, 34:3191-3204, 2021.
[25] Ainesh Bakshi and Pravesh K Kothari. List-decodable subspace recovery: Dimension indepen- dent error in polynomial time. In Proceedings the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1279-1297. SIAM, 2021.
[26] Prasad Raghavendra and Morris Yau. List decodable subspace recovery. In Conference Learning Theory, pages 3206-3226. PMLR, 2020.
[27] Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. A discriminative framework for clustering via similarity functions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 671 1-600, 2008
[28] Michela Meister and Gregory Valiant. A data prism: Semi-verified learning in the small-alpha regime. In Conference On Learning Theory, pages 1530-1546. PMLR, 2018.
[29] Ainesh Bakshi, Ilias Diakonikolas, Samuel B Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K Kothari. Outlier-robust clustering of Gaussians and other non-spherical mixtures. In 2020 IEEE 61st Annual Symposium Foundations of Computer Science (FOCS), pages 149-159. IEEE, 2020.
[30] Allen Liu and Ankur Moitra. Settling the robust learnability of mixtures of Gaussians. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 2021.
[31] Luis Angel Gareía-Escudens Alfonso Gordaliza, Carlos Matrán, and Agustín Mayo-Iscar. A review of robust clustering methods. Advances in Data Analysis and Classification, 4:89-109, 2010.
[32] Martin Ester; Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, al. A density- algorithm for discovering clusters in large spatial databases with noise. In kdd, pages 226-231, 1996.
12

---

[33] Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, pages 129-137, 1982.
[34] Christian Brownlees, Emilien Joly, and Gābor Lugosi. Empirical risk minimization for heavy- tailed losses. The Annals of Statistics, 43(6):2507-2536, 2015.
[35] Ilaas Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robustly learning a Gaussian: Getting optimal error, efficiently. In Artur Czumaj. editor, Proceedings of the Twenty-Ninth Anmual ACM-SIAM Symposium Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2683-2702. SIAM, 2018.
13

---

A Examples
inlier cluster, outlier clusters. model itself. In particular, we consider
One tricky adversarial distribution is the Gaussian mixture
k
X
N(us k
N(j I);
(A.1)
k +
where the first i Gaussian components are inliers and Q is GMM with components, which call fake clusters. Since all inlier cluster weights are identical, we denote w == = 1/(k + c). Assume that 1 c < k, which corresponds
> W. Then, relative weights are Due to large adversary, previous results on learning GMMs cannot be applied, leaving vanilla list- decodable learning. However, the latter also cannot guarantee anything better that 5 (Vvik=//* even with the knowledge of k; long as list size is (kk+c) which can be much worse than our guarantees of (t) for the same list size.
1/(cc((]] x l/c.
Their drawback is that they do not utilize separation between true clusters, i.e., for each i, they model the data as
1 N(p, + le k ( Q.
X
c
where Q can be "arbitratily adversarial" for recovering p4:
Big + small inlier clusters
Consider the mixture
= = - N(p1, Ia) + wN((2, + =Q,
(A.2)
where ||и - -22l = 92( / log 1/w), & < 1, and Q is chosen adversarially, In this example we have two inlier clusters, one with large weight se and another with small weight w. Adversarial distribution Q has large weight relative the small cluster, but still negligible weight compared to the large one.
Previous methods would either (i) recover large cluster with optimal eтror OEe) (see, e.g., [35]) but miss out small cluster or (ii) recover both clusters using list-decodable mean estimation with known a w. but with suboptimal errors Ol 1/w/ and list size (1/wr) In contrast, Corol- lary 3.4 guarantees list size at most 1 + Oss/w) error O( (TVoog//u for the small cluster, and error ( /log 1/2) for the larger. In general, we achieve (i) optimal errors for both clusters and (ii) optimal (up to constants) list size.
B Inner and outer stage algorithms and guarantees
Our meta-algorithm Algorithm assumes black-box access to list-decodable mean estimation algo- rithm and robust mean estimation algorithm for sub-Gaussian (up to the hh moment) distributions. From these we obtain stronger mean estimation algorithms when the fraction of outliers unknown, and finally stronger algorithms for learning separated mixtures when the fraction of outliers can be arbitrarily large. Our algorithm achieves guarantees with polynomial runtime and sample complexity if the block-box learners achieve the guarantees for their corresponding mean estimation setting. In this section we discuss the corruption model and inner and out stage the meta-algorithm in detail and prove properties needed for the proof of the main Theorem 3.3.
B.1 Detailed setting
order to achieve these guarantees, our black-box algorithms need to work under a model which an adversary is allowed to remove small fraction of the inliers and add arbitrarily many outliers. In our proofs, for simplicity of exposition, we require the algorithms to have mean estimation guarantees for small adversarially removed fraction of w Formally, the corruption model as defined as follows.
Definition B.1 (Corruption model). Let d E N4, and a E [whow: 1]. Let D a d-dimensional distribution. An input of size according to our corruption model is generated as follows:
14

---

Algorithm 2 FullAlgorithm
Input: Samples S = (......, F, Whows algorithms ALLD. and A
Output: List
1: Run OuterStage (Algorithm 6) on S and let T be the returned list.
2: I. 0.
3: for T E do
4: Run InnerStage (Algorithm 3) on with Oloow Whow [7]
5: Add the elements of the returned list to L.
6: return L.
Algorithm 3 InnerStage
Input: Samples = { In alow E [Woows 1], AKLD, and A.. Output: List L.
1: alow f min (low)
2: M +-
3: for â {(llow: 20 | (3 [low] do
4: run ARLD S with fraction of inliers
5: add the pair (ft, â) to M for each output ft
6: Let L be the output of ListFilter (Algorithm 4) run on S, (low and M
7: for (f,&) E L do
8: replace ü by the output of ImproveWithRMM (Algorithm 5) run S, p. (0))
4f(á). and Ar
9: return L
Draw a set C* of n = [an]] i.i.d. samples from the distribution D.
An adversary is allowed to arbitrarily remove [wi Ri samples from C*,, We refer to the resulting set as S with size 72 |
An adversary is allowed to add n2 arbitrary points to S*. We refer to the resulting set as Sav with size ny [Save].
If nig < n, pad Sutv with n ng arbitrary points and call the resulting set S.
Return S.
We call cor-kLD the model when woow and a are given to the algorithm and cor-aLD the model when Whw and lower bound Now 2 Wlow are given to the algorithm, such that a Olw- Note that is not provided in cor-aLD model.
Note that in Definition B.1 [S] = n and S* constitutes at least an a:l - ww fractiio of S.
B.2 Inner stage algorithm and guarantees
The algorithm consists of three steps: (1) Constructing list of hypotheses, (2) Filtering the hypothe- ses, and (3) Improving the hypotheses if a > 1 - -ERME- For convenience, we restate the InnerStage algorithm introduced the main text.
Theorem B.2 (Inner stage guarantees). Let d N4, whow E (0, 10,10-+), Whow & Olow & a & 1, and be an even integer. Let D(μ*) be d-dimensional distribution with mean μ³" E gd and nub-Gaussian t-th central moments.
Consider the cor-aLD corruption model in Definition B.1 with parameters d, Wlow. and dis- tribution D(p"). Let Aun and Ar satisfy Assumption 3.1 with high success probability (see Remark B.3).
Then InnerStage (Algorithm 3), given an imput of poly(d, 1/Wrow) (Nr.DW + N WR(Wiow )) samples from the cor-aLD) corruption model, and access the parameters d, Woow Olows
15

---

Algorithm 4 ListPilter
Input: Samples S = (0),... Fn Nlow E [Winws 1/100], and M {(ii, âi),... ... (imm am))
Output: List I,
1: define B(ax) 100x(a) f(a)
2: let Pky be unit vector the direction of N4 - jig for in # ity E (ūt for (A, M}
3: J ++0
4: for (i) E AM in decreasing order of O; do
5:
if exists J, such that || 0,ll < 4,3(a)) then continue
6:
Ti + NJes( S, s.t. [ - A.) < }(
7:
if [T]] < 0.9á, then remove (fe, 6;) from M and continue
8:
add i to J
9:
for j E J \. {i} do
J5+T, E S, s.t. 10 {(a.))
if [T,] 0.9å,n then:
12:
remove Úg) from M rerun List Filter (Algorithm 4) with the new M 14: return ((A,a.), for E J}
Algorithm 5 ImproveWithRME
Input: Samples S {x1 ................................ .....,,,,, Jn vector á. threshold т, and Ar
Output: A vector j E R
1: T-T
2: let á be the smallest value in [1 ERME, 1] that satisfies g(ā) & B/2. If none exists, return ji
3: Ā + ğ and let PRME be the output of Ar run on with inlier fraction set to
4: while || PRMEll < 33/2 do
5:
PRME
6:
ß - =-)(
7:
let ā' be the smallest in [ā + wiow such that g(ā') < 3/2. If none exists, break
8:
á á'
9:
1ct PRME be the output of Ar on S with inlier fraction set to ā
return
and t, runs in time poly(d, 1/Wrow) (TID + Trx (1Too))) and oulputs list L of size 0(1)
|L| + +((1-a))
such that, with probability Wlow
1. There exists js E L such that
l/ - n1' ((bi(a/4)) + M(a44)).
2. a 3 1 -ERME, then there exists ja E such that
A n²ll < Olg(a - woow)
Proof of Theorem B.2 can be found in Appendix D.
Remark B.3. For any N. we can increase probabilities of success of ALLD and Ag from 1/2 to 2- the following way: we increase number of samples by a factor of r, randomly split S into subsets of equal size, apply AuLD and Ar to these subsets and concatenate their outputs. In the proofs we assume that the success probabilities are w for large enough constant C. This increases the size of the list returned by AgLD, the number of samples, and the running time by factor Ologg( 1/ Wlow) )). In particular, we assume that the size of the list returned by ALLD much smaller than the inverse failure probability.
Remark B.4. In the execution of the meta-algorithm, it may happen that Algorithm 3 is run set with almost no inliers, iee. a Oloww We note that from the analysis (see Appendix D, [3]. Proposition B.1), we always have upper bound [ 0(1/atow)
16

---

An immediate consequence of Theorem B.2 are the following guarantees of directly applying Algo- rithm 3 the mixture learning case with no separation. Here we present upper bounds for Algorithm when no separation assumptions are imposed.
Corollary B.5. Let E N+, Wlow E (0, 10_ and be an even integer. For all i = 1,..., k, let Di((s) be a d-dimensional distribution with mean μui E Rdd and sub- Gaussian 1-th central moments. Let & > and, for all i- 1....,k, k, let wi E [Wlow 11, such that Di=1 Wi + = 1. Let X be the d-dimensional mixture distribution
X Σ w,D.(p) +
where Q is an unknown adversarial distribution that can depend on all the other parameters. Let ALLD and Ag satisfy Assumption 3.1.
Then there exists an algorithm that, given poly(d, //rrow)) (Ns.(Wwooe + NR(Woww) )) iidd samples from X, and given also d, k. Whows and t, runs in time poly(d, 1/mlww) (TLD(W)ow) + Tr((ooo )) and outputs a list To of size [T,] (11/Woo)) such that, with probability at least 1 u
1. For each E [k], there exists ja E such that
||i pill & (1h((w5/44 + [wws/4)).
2. For each i [k], if;; P 1 - ERME, then there exists á L such that
|/ pall < Og((w: )l.nw)).
Proof. Proof follows by applying Theorem B.2 to X with Clow Whow and treating each component as a corresponding inlier distribution with a Wi. This gives error upper bound for all inlier components, furthermore, since aow Wlows list size can be bounded as [L] < 1 + O(11
a)/() = O(1/ //llow).
B.3 Outer stage algorithm and guarantees
In the outer stage, presented in Algorithm 6, make of the list-decodable mean estimation algorithm in Theorem B.2 in order to solve list-decodable mixture estimation with separated means. We now present results on the outer stage algorithm. For case of notation, when it's clear from the context, we drop the indices and refer to elements μ4j E M for some j E [[ as μ and their as defined lines 6-7 Algorithm 6, as g(1),s(() Further, for i [k:]. let C denote the set of points corresponding to the i-th inlier component, also called the i-th inlier cluster.
corresponding sets S S
Theorem B.6 (Outer stage guarantees, beginning of execution). Let S consist of n i.i.d. samples from X as in the statement of Theorem C.I. Run OuterStage (Algorithm 6) on S and consider the first iteration of the while-loop and for each E M, denote the corresponding sets as S S(?) O(1)
Then, with probability at least 1 Wlow
have that
(i) the list M. that AID outputs has size M < 2. //Wlows
( nc; > (1 wi? |
(ii) for each i E [k)], there exists m, E [[M]] such that
(ii)) for each [k]] and μ M, we have (5()) nC w |C;1 or (5(2) (1
|C+))
(iv) for each E [k] and a e M such that | n
w |C
have
E Evelun S(2)) n noa < wfon.
(v) for +' E [k] and for j.j E [IM], (1s > wft |C and | no? > w C7p,
then (02 ss52) 0.
17

---

Algorithm 6 OuterStage
Input: Samples S = {z Fn Wlows ASI.D
Output: Collection of sets
1: run A&LD S with
Wlow and let M = {uI,... Marn be the returned list
2: let 0ij be a unit vector in the direction of Hi for i + E [[M]]]
3: T 0 and R < [I,....IMI}
4: while R * 0 do
5:
for all i do
6:
5
Del[ArI)s {x E S. s.t. 10 (i)l < 7 +
5 DElIMI)A {ir S, s.t. 11 Hi)l & By + 37/}
7:
remove all R for which | 100mlow
8:
9:
if RR=0 0 then break
if there exists E R such that |s(20| < 2)5(1)) then
select the i R with (s(22) < 2 for which (s is largest
11:
T TU-UU s
12:
5 S ((1) R+ {i}
13:
15:
else
16:
J J U (S)
17:
break
return
In words, Theorem B.6 (ii) states that initialization, OuterStage represents each inlier cluster well, i.., for each i, the i-th cluster is almost entirely contained some set 5 for some j E [[M]]. Next, (iii) states that either 5(2) intersects negligibly some true component, or 5(2) contains almost entirely the same component. Further, (iv) and (v) state that sets that sufficiently intersect with some true component must be separated from other components and each other.
We now introduce some notation to present the next theorem that establishes further guarantees for the algorithm output during execution. For J, a collection of sets that the output of Algorithm 6, define
G G=
[k:]. such that there exists - with ( no;
wfo |C?|, for some j
(B.1)
In words, the set of inlier components for which a corresponding set with "sufficiently many" points from the i-th component was added to T. It may happen that for a given index i E G, several
j E [[] satisfy 5/²) E T and ( i cr
2 witow |C,] We define 9i E [[ to denote the index
of the first such set s(2) added J.
to be the set of inlier points from the i-th component, which were not removed from S at the iteration corresponding gi. Let == UieqU' denote the union of such 'left-over' inlier points.
Further, we define U; == -C, n S \ ((
Theorem B.7 (Outer stage guarantees, during execution). Let S consist of n. i..dd. samples from as in the statement of Theorem C.I. Run OuterStage (Algorithm 6) on S and consider the moment when the sets 2 are added J. We have that, with probability least woow all of the following are true:
(i) UU| & (2c + Ow.
(ii) for E G. we have that (
nc: > (1 Wie O( 10 > (1
w wwn,
(ii)) for [[MI] (g: ( either | < Oww )n, at least half of the samples in
si") either adversarial samples or lie in U,
18

---

(iv) when the else statement is triggered, [S| > 0. o. then at least a 0.4-fraction of the samples are adversarial, or equivalently, |S| < 2.5mn. to J, corresponding to G, almost entirely contain C; Finally, (iii) describes the sets that do not correspond to any g.. i E G. These sets must either be small, or contain a significant amount of outlier points in the neighborhood. The proofs of Theorems B,6 and B.7 can be found in Appendix E.
Note that the else statement of OuterStago can only be triggered once, at the end of the execution. In words, Theorem B.7 (i) states that, for E G, samples from i-th cluster that remained in S after s(1) was removed, constitute a small (comparable with E) fraction. Further, (ii) states that the sets added
C Proof of Theorem 3.3
In this section, we state and prove a refined version of our main result, Theorem C.I, from which the statement of Theorem 3.3 directly follows.
C.1 General theorem statement
We define
(a) = { Vi(1/a))/+ ift < 2og l/a,
(C.1)
2e log 1/a else,
which captures tail decay of distribution with sub-Gaussian t-th central moments:
P PAND (xr ue u)* vs(a)) S a.
We now state our main result for list-decodable mixture learning. Recall that CRME defined in Assumption 3.1.
Theorem C.1 (Main mixture model result). Let dl E N., Whow E (0, 10- and be an even integer. For all i = k. let (14) be a d-dimensional distribution with mean μ4i E Id and Bub-Gaussian t-th central moments. Let 0 and, for all i I...., k. let wi E [Wlows 1}. such that Σk Wi + 1. Let X be the d-dimensional mixture distribution
X
w. wpps) +
where Q is unknown adversarial distribution that can depend on all the other parameters. Let AyLD and Ar satisfy Assumption 3.1. Further, suppose that [|p MUll > 10000e(wtoon ) ) 200 (wlow) for all i + [k].
Then there exists an algorithm poly(d, 1/W)ow) (NLD(W)OW) Nn NN(WWoo) )) i...d.
that, given samples from X, and given also d k. (Te(wrow)) and with probability at least 1 Vow outputs list L of size [T] & k + (E/ Wlow) such that, for each E [Rc], there exists such that:
(Algorithm
Wlow, and f, runs time poly 1/ s/ulow) (TLD
0(1)
l pill & ((v(((0110)) f(w:/10)). where w = ww/www + + w the relative weight of the i-th inlier cluster large, i.e., W SRME 2w then there exists f E L such that
A - mill < O(g(ū 3w)ow)).
Further, we assume whow E (o, 10,0000000, since this simplifies some of the proofs. We note that in mixture with I components we necessarily have Whow < 1/k. Furthermore, when Whow (1/10000, 1/2], then we obtain the same result by replacing Wlow with Whow /5000 throughout the statements and the proof. This would only affect both list size and error guarantees by at most multiplicative constant, which is absorbed the Big-O notation.
Proof of Theorem 3.3. Proof follows directly from Theorem C. by noticing that Assumption 3.2 allows to replace [(i by ( and g(ū; 3w by Cg (w:) for some constant > large enough.
19

---

C.2 Proof of Theorem C.1
We now show how to use the results on the inner and outer stage, Theorem B.2 and Theorem B.7 respectively, to arrive at the guarantees for the full algorithm Algorithm 2 in Theorem C.I. For simplicity of the exposition, we split the proof of Theorem C.1 into two separate parts, proving that (i) the output list contains an estimate with small error and that (ii) the size of the output list is small. In what follows we condition on the event E' from the proof of Theorem B.7.
(i) Proof of error statement We now prove that, conditioned on the event E, the list L output by Algorithm for each i [k] contains an estimate j E L, such that,
(1) A uill & (1vr((;:10) + f(w:/10)).
(2) if w > 1 CRME + +20fow then // - pell & Og((ū; 3wl
We start by showing that list-decoding error guarantees in (1) are achievable for all inlier clusters and proceed by improving the error to (2) with RME base learner. Recall that G is as defined in Eq. (B.1).
Proof (1) We now show how the output of the base learner and filtering procedure lead the error in (1). Fix i E [k:. Recall that C; denotes the set of win points from i-th inlier component with mean P..
If i
G, then on event E, we have $
c
>
(1
)wnn by Theorem B.7 (ii),
Eist g. n nCj & wfo n by Theorem B.6 (iv), and that the total number of adversarial points is at most (s + whow Wooo)n. )n.
Therefore, the fraction of points from C in Sg. is at least (1-w Ju which implies a > ú; as mi+e+
in Definition B.I. Then, by Theorem B.2, the InnerStage algorithm applied to T leads to error 2 - /4,1 & ((0g(10g/4) /4) + ((x)//)) Otherwise, if & G, when the OuterStage algorithm reaches the else statement, S contains at least (1 - (w C); samples from C₁ Indeed, since & G, each time remove points from S, remove most wfow" points from C₁ By Theorem B.6 (i), we do at most ([1/Wlo)) removals, so when the Outer algorithm reaches the else statement, S contains at least (1 O(w |C;| samples from CT
We showed that samples from C; make up at least (1 u Jw,n/[S] fraction of S. Based on this fact we can then use Theorem B.7 (iv) and the assumption on the range of w)o to conclude that |S| < 2.5sn and that the fraction of inliers is at least (1 - / )w; /w:/(2.) (2.5e). Therefore, S can be seen as containing samples from the corruption model cor-aLD with least (2.(2. > w;/(2.5(w; (w; + e)). Since S is added to T in the else statement, applying InnerStage yields the error bound as in (1).
Proof of (2): Next, we prove that for all inlier components with large weight, i.e., such that wy/(wq e) > 1 ERME, there exists a set T E T that consists of samples from the corruption model cor-aLD with a ? wi/ww; + E) 2 Then, running InnerStage, in particular the RME base learner, results in the error bound as in (2) by Theorem B.2 (ii). If E G, in the previous paragraph we showed that there exists T JJ such that the corresponding a > wi-e+w
2w We
an.
now prove by contradiction that the case & G does not occur. Now assume i i$ G so that before when the else statement is triggered, S contains at least (1 - Ow (wwr))))(C ))[C' samples from C₁.
argued
By Theorem B.6 (ii), for some m. E [[]]] we have that (()) nC > (1 Trow /2 O ))C7 and by Theorem B.6 (iv), s(2) contains at most wifnn n samples from other true clusters. Then, since
|s!! > 2| ( we have that | contains least
(1 noww Ow )) wfow n 2 (1 1.5mfo |C
adversarial samples. Therefore, E > (1 - (CT and using that |C > win woo n, we have E > (1 1.5wfow )w, Wlow However, this contradicts w;/ (w, + =) > 1 - ERME unless ERME > 1/2 2w which is prohibited by the assumptions in Theorem C.I. Therefore whenever wi/(w; + E) > 1- ERME we are in the case E G.
10
10
20

---

+ (ii) Proof of small list size We now prove that on the set E, we have that [L] < + ((E/ (oo/)/)...... Here, we need to carefully analyze iterations in the while loop where an inlier component "selected" for the first time in order to obtain a tight list size bound. Recall that 9i corresponds to the index R that first selected for the i-th inlier cluster.
First selection of a component: For any [K], if G, then Theorem B.7 (ii) implies that running InnerStage on Sg. produces a list of size at most 1 +((S)) (1loo n)). Then, over all i E G, these sets > contribute to the list size |L] at most + O (Ei 1s ((l/(
Furthermore, by Theorem B.6 (v), all these sets S are disjoint and each of them contains at most "Yow, samples from other true clusters. Therefore Σ == [s(2) A & en + O ).. Then the contribution to []] of all these S 's corresponding to true clusters is at most k+0 ((E + wlow) (ow)//joon //Joow) Note that if & w'o and Wlow is small enough, Algorithm 3 actually produces a list of size 1 in each rum considered above, so the contribution is exactly k; otherwise we can bound the contribution by k + (E/ /W
Samples left over from component: Next, all inlier samples that were not removed, i.e., constituting U. can be considered outlier points for the future iterations, which, by Theorem B.7 (i), only increases the outlier fraction to É = 35 + Ow For the same reason as above, without loss of generality, we can consider & > whow since otherwise, the corresponding list size overhead (for small enough w would again amount to zero.
Clusters of adversarial samples: For iterations where set S was added to the final list, which does not correspond some fi. G, Theorem B.7 (iii,, states that either (i) least half of the samples in s8² were adversarial, or (ii) the cardinality of the set on which Algorithm was executed is small. In both cases the set st2) contributes at most ( ((/////)) to the final list size [L]_
List size in the else statement: Finally, when the algorithm reaches the else statement, as argued in the first part, by Theorem B.7 (iv), at that iteration [S| < Og)).. Since Algorithm 3 always produces a list of size bounded by O([S) / (w]ow)) is bounded by O(=/wlow)
(see Remark B.4), the contribution to L at this iteration
Overall, we obtain the desired bound on L of le + O(0/0(E///w) wwww).
D Proof of Theorem B.2
(i) Proof of error statement of Algorithm 6,
We now prove that, with probability 1 - Wlow for the output list L
O(1)
1. there exists j E such that
1 n0ll & (1b((a/4) + f(a/4)),
2. if a > 1 -ERMES then there exists ja E such that
| f 1 < O(g(a - woo )).
By Lemma D.1 have |M| & 1/ 0(1) and, with probability at least 1 - who there exists (ń, 6) E M such that à 2 a/4 and / 1²ll & f(ā). Then Lemma D.2 implies that, with probability at least 1- - M 2w O(1) (f.âa â) will not be removed from M. Therefore, either (ū, á) L. or there exists (ūz â) E I. such that (i) ā 2 à and (ii) [| راl < 4,3(6.. The latter case implies that || n0 & 40v)((//4
001)
(f(4).
For the second part, set first Ā á. Then, in the 7th iteration, j moves away by at most (37 (3 Since Σ 1/22 & 1, the distance between ğ and j always bounded by 3r. Now, assume that indeed a ERME and l/ n=ll < r. Whenever ă & a, with high probability Ar produces some PRME such that [RRE 4²ll < g(ā) < $/2. Furthermore, as long as ā & a, at the moment
21

---

of the while statement check we have || 1 in later iterations it follows because f is the former PRME. Therefore the while statement check passes as long as Ō & (r.
|| < B: in the first iteration this is by assumption, and
There exists the possibility that the algorithm returns or breaks even though h & a. If the algorithm returns early, then the error r achieved by f is already within a factor of two of the optimal. If the algorithm breaks, either wiww > 1, case in which j already satisfies || - = & g(l w(ww) or else | 1e' is already within a factor of two of the optimal. Therefore these cases do not affect the error negatively.
Finally, let us consider what happens when ā > a and the while statement check continues to pass. The first time we reach some à > o, we must have | 1a I| < 3 & 2g(ax w Then, in later iterations, f can move from this estimate by distance of most 3B & 6g(a w by the same argument as the argument that || A < 3T. Overall, at the end we have
- ا & max(2y(1), (1), (1 - (o 8g(a)) < Sg(a w
The number of runs is at most 1/w/ow- so with probability 1 - WWoow
O(1) all runs of Ar succeed.
We showed that there exists (ji, à) E L such that à > a/4 and || - -=1| < 40y4 + 4f()). This error can increase by running Improve with 7 40))(() + 4f(a) to at most
A n²1 < (a) + 16f(a) = (v) + f(a)).
Furthermore, if b 1 min- this (á, à) L satisfies the conditions of ImproveWithRMEE, so with high probability the error is reduced by running ImproveWithRME with r = (0))(())((() to | μe 8g(a- w
(ii) Proof of list size We now prove that |4| < 1 + ((1 (a)/ui/nn
First, assume that a < 9/10. Since all å, > Ooow. we have that |4] < 10/ < 12(1-a)/au
For the rest of the proof we assume that > 9/10. We analyze sets J and T, for E J at the end of exccution of ListFilter. In particular, recall that L = [(p,, a;), i E J}. Also, at the end of Algorithm 4 we have the following expression for T3:
T = N tx S, s.t. 10]](0 - i=)1 & (())((
jEJ(()
where Viy are unit vectors in direction م. - Aa.. Select the s E JJ for which å₂ is maximized. By (i), with probability at least 1 "fo there exists hypothesis in J with â >/ a/4 > 0.2. Then we have that 6₂ > 0.2. In addition, for all hypotheses, âg & 1/3. Let j E J be such that j * 8. We will show that at least half of the points in T3 are adversarial, i.e., [T]] >> [T; C* If this indeed the case, we can treat all inlier points in all T3 as outliers, as it would at most double total number of outlier points in S.
Now, assume that for some and |C*| >> 0.9n, [T, n C* > 0.18n - 0.1n > 0.08n. Therefore
j * s, [T5 < 2 n C* Note that, because [T,] > 0.9 0.2n = 0.18m
H C", s.t. lu]](x (.)) < ((a,)) > 0.08 |C*).
Also note that Lemma H.2 for radius 10/2(1122) & 10xh (ā.)) implies that, with exponentially small failure probability,
KrECT s.t. 1e n²) < 3(a))) | 0.99|C"']
Since these two sets necessarily intersect, we can bound 1T (A. - n²))= < 25)))). implying that (1 |²) > 23(0,), since l/ū, الاll > 48(,,). Thus, if 10 (5)) < [(āz), then
|v, (2 - x²)) > B(ā,), implying that
(T,NC*) fo s.t. |. (r (-")==-)]] -=,))}((}}}}
(D.1)
However, Lemma H.2 tells us that with high probability only a small fraction of points in O* satisfies [x n²)l= 8(āz). ). In particular, applying the lemma with radius 10 we get that with exponentially small failure probability,
x E C*, s.t. [0T p²) < B(ag)) (1-
aj 50
|a
(D.2)
22

---

From eqs. (D.1) and (D.2) it follows that 1 n < â |C*| /550. Using that [T}] > 9 10 >>
96, |C11/10 /10 by the properties of ListFilter, we obtain
9ā, /C1 [Ty] < 2 n C*I < âj /25/
which is contradiction.
Therefore, for all j E J such that j * s, we have that [7,] > 2 CTT As we said in the beginning, by treating all inlier points in those Tj outliers we at most double total number of outlier points. Since there are at most (1 a + arw ) outlier points and the sets T3 are non-intersecting, we
get Σ [s)
[z)] < 2(1 - a + aww ).. The lower bound on the size [Ty] 9atown/ 10 implies
JJ/ [+]] & 2(1 pp m--10 and thus [T|] |J| < 1 3(1 o:) /low-
90 R
Note that in InnerStage set Olow min(aroww 1/100). Therefore, for the original Oows the list size is bounded by 1 + 240(1 - a)/alow.
Conclusion Combining the probabilities of success of all steps, get that the algorithm succeeds 0(1) for some large constant in the exponent. Our algorithm. ignoring with probability at least 1 - low
the calls to ALLD and Ag. has sample complexity and time complexity bounded by poly(d, 1/ 1/Wlow). which gives the desired sample and time complexity when taking ALLD and Ag into consideration. This completes the proof of the theorem.
D.1 Auxiliary lemmas and proofs
Lemma D.1 (List initialization). Let S, Ooow and a be as in cor-aLD model. If InnerStage (Algo- rithm 3) is run with S and aoww the size of M is at most 1/ 1/ all (ft, â) E M satisfy á < 1/3. and with probability at least 1 - w/ow (11) there exists (R, â) E M such that a/ & à & min(a, 1/3) and A| 1=1l & f(ā:).
0(1)
Proof. There are at most 1/alow choices for å, and for each of them the output of ALLD has size at 1 1//low runs. Then we are guaranteed to produce one & with a/4 4 & â & min(a, 1/3), and then ALLD is guaranteed to produce one corresponding with Í - 1='| < ((a).
most 1/m o(1) so MM| < 1/ With probability 1- ((11 .LLD succeeds in all up to
Lemma D.2 (Good hypotheses are not removed). Let S, alow and a be as in cor-aLD model. Run ListFilter (Algorithu 4) on S and Onow with M obtained InnerStage (Algorithm 3) and call a hypothesis (p, â') E M good if 2 a/4 and 1| - p²1l & f(a). Then, with probability at least |M [ 0(1) no good hypothesis is removed from from M (including in any of the reruns triggered by the algorithm).
Proof. Let & be arbitrary iteration of the outer for loop. Then, the beginning of the fth iteration,
1. T nT, = 0 for any j < s E J,
2. [Tyl > 0.96yn for any j E J.
3. []] < 10/(9åz).
Indeed, the second property follows directly from the algorithm.
For the first property, assume that for j < E J. there exists S, such that x E T3 n., This would imply that [o), - p.)) < 2,((a), so |l - A. |l & 28((.). However, in this case the first 'if' condition would pass and we would not add to J. Thus. 77 n T. 0.
For the third property, note that
n
Σ |T,
Σ jej
0.9ā,n 0.9 âm,
JEJ
which implies |J] & 19/4).
23

---

Now, let s be the index of hypothesis with å, > a/4 and A --=1| < f(ā)). If s was skipped in the 5th iteration (i.e., there exists j E J with B. close to j.), then (f,, (,) is trivially not removed from M. For the rest of the proof we assume that is not skipped.
For the sake of the analysis, we introduce the analogue of the sets T, which we call T., defined for points in the set C* (i.e., all inlier points before the adversarial removal), and show that (i) T is
large and (ii) Tg T. is small. In particular, let
T,
nn+ { { CO,, s.t. 10 -a)) < 3(a))} jEJ
where recall B().)) = (6,) f(,)). Note that [T.] T.. - |c | -c
T, wfow |0
Also, for any a' & åg applying Lemma H.2 with radius 10 (a'), ) using that 1| μ² < f(,,) $ f(a') and 2 2, we get that with exponentially small failure probability,
a'
1 E CC s.t. 10 T (x - -aa) > 8(a'))
& 50 |0"|
(D.3)
Consider the 5 iteration. Using union bound over |J| & 2/0 directions, and since all ã, 2 Olww we get that with exponentially small failure probability
T.. > 1-1
Σ HE s.t. 10 p&)l > B(a.)) > (1
â 50
(1]) 10 0.95 C*I,
where we used that and
||| 10/(9á.). This implies that
Tel
T w IC*l (0.95 w C"I > 0.92 0092|C*1
> 0.9an > 0.9
i.e. (Jis; (r.) is not removed from M during hh iteration.
The pair (ps, âg) could also removed during later iterations, when we recalculate TN by removing points along new directions. However, following a similar argument, we show that still, with high probability, [Tal > 0.9å, Assume that we are now in the 4t iteration of the outer cycle, where s. We define again T. and sets A, B:
f, =
n E" (EJ((a)
C", s.t. 1 - pa)1 max(
A =
N Ai for
A; = fx E C² s.t. [0] p.)l < ((ā.))
(<e,EJ
B =
B for
B; = f C*, s.t. | P.)) < ((a)))
so that T, An and again [T.) >
[T.] w |C*|. It is crucial that we have different right hand sides in the definitions of A; and B, (we wrote them in boldface to emphasize this).
Using union bound again, we write
7. |0
IC A
Σ
|C* Bil.
i<ANEJ
Using eq. (D.3), with exponentially small failure probability, for all i E J,
IC* A,l & (á./50) |C*| (for <) and |C* \B\BB < (á:/50) |C*| (for i > s).
Next, note that before the last element was added, we had that (i) T; nT; = 0 for any + j E J and (ii) [T:l > 0.9ā,n for any i E This implies that Σie, d; < 10/9 + dr < 19/9. where âlass corresponds to the element which was added last (it might happen that after addition of the last element, we have [Ti| < 0.9ámn for several E J). Therefore, as before, we obtain that
Ts >
1
Σ iCONEJ
(a./50)
E (a:/50) De,iEJ
> (1-10/055000) |0*|> 0.93 |C*),
24

---

therefore [Ta]]
T. wio
|C*1 > 0.92 [C > 0.9ā,n n and (Re, a,) will not be removed from M.
We established that in a single run of the algorithm a good hypothesis is removed with exponentially small probability. The number of good hypotheses is bounded by JM]. Furthermore, the number of runs of the algorithm is also bounded by [M,] since whenever the algorithm is rerun a hypothesis is removed from M. Then, by a union bound, we can bound the probability that any good hypothesis is removed in any run of the algorithm by M Wlow O(1)
E
Proof of outer stage algorithm guarantees in Appendix B.3
Recall that y 4t's (w and 7 160%/ (Wrow/ / /4) + 16f /4).
E.1 Proof of Theorem B.6
In what follows we condition on the event E' that the events under which the conclusions in Lem- mas H.2 and H.3 hold and that AsLD succeeds. This event holds with probability 1 -w wtow by Assumption 3.1, Remark B.3 and union bound (also see Appendix G).
O(1)
Proof of Theorem B.6 (i) The list size bound follows from the standard results on A,LD (see [3], Proposition B.I).
Proof of Theorem B.6 (ii) Guarantees of A&LD imply that there exists E M such that ||x
1Ill < r. By Lemma H.3. a (1 (1-wlow/2)- (2)=m/2))fraction of the samples in C' are y-close to μ along each direction fi with i * E [M]]] Then, the same (1 www (ttw:/2)-frctiie (2)-fraction of samples are (7 >closs to tu along each direction U,j, so they are included in s!
Proof of Theorem B.6 (iii) Suppose |S!²) n nC' w C*). Previous point implies that there exists (4, E M be such that || 1= < < Then at least an wit -racttoo of the samples in C* are (7 + 7'Cclose to μ4 direction μ4 pz. By Lemma H.2, μ² is also y-close in direction 14 - Pj more than (1 w ]-raction of the samples in C it is 7-close at least one sample in any w -fractiin of samples in C* Therefore μr" is also (2y + 7/)-close μ4 in direction μ4 py- Then |//4 M4l & 27 + 27' and ||44 μ=1l < 27 + 3/. Again, using Lemma H.3 we obtain that there exists wfow / -fr-ftat of the samples in C*, which is included in s(
C*| > "lo 1C then there exists By E M, such that at least an whww-fracc -faction of the samples in C* are (3y 3y')-close μs in direction
Proof of Theorem B.6 (iv) Similarly, if (5(00)
H4; Mý. By the same arguments as in previous paragraph, we obtain that ||m M5ll < 4y + 4y and
I|A: - --4l-111 4y + 5/
Then any other true cluster with mean (n*) and set of samples (C*y satisfies || - (n (I > 16y 167', || (1r*) > 12y 117 From guarantees of ALLD, there exists ní) E M such that 11m6 - (1* & 9. Then || 14-1/ > 12y + 10y'. By Lemma H.2, more than an w fraction of the samples from (C*y are 7-close to (n*) in direction μ4: - nly, so also (7 + 7/c-oss to uz in direction μ4 ndg, so also (11y + 9-')-far from μ4 in direction μ4 ptz. Then 5(2) selects at most a w fraction of the samples from (C*y. Overall, s((2) selects from all other true clusters at most w/ fno samples.
Proof of Theorem B.6 (v) Note that by the same argument, || - μ|| < 4y + 5y and I| (n*)1) & 47 + 5ny_ However, I|"² (1*)a| > 16y + 16 so also || - prll > 8y + Gy', so s(2) and ((2)) are disjoint by the condition that each selects only samples that are (3y + 3-')- along direction μ4 my to the respective means μi and pr.
(v6
25

---

E.2 Proof of Theorem B.7
In the sequel, for any E G, let my be the index in R after initialization that satisfies Theorem B.6 (ii). We condition the event E' that event E from the proof of Theorem B.6 holds and that both ||C?| - w.n| & 10 for all i E [k] and the number of adversarial points lies in the range En w By Hoeffding's inequality and the union bound, the probability of E' is least Wlow
Proof of Theorem B.7 (i) Let i E G, and consider the beginning of the iteration when Hg. is selected. Then, using that all previous iterations could have removed at most O (wwww) [C, samples from C,,, we have that
S U n0 > (1 - w2ww//2- (w ))(C7)-
Therefore at the iteration in which Mg, is selected, we still have m, E R. We now discuss two cases: | Then, because we selected Mg. E M and not Jmn, E M means that | > | (1 w/ow/ 2 (wwoow))) Note also by Theorem B.6 (iv), the number of samples from other true clusters in s(2) is at most Who n. Then the number of adversarial samples in s(2) least
First, consider the case that [ < 2|
[ |C Woo T2
> |s(2)
S Ow
10,1
4 Wlow > |S \ (5 - (w |.
Then, either
(2)
S9: Ow and |0A]
c(I)
O(w C+ or S consists of adversarial examples
9g
Sg.
(()) gg
wht CH, In the latter case, even if c(2)
only, then, since |
Sg |, Us contains at most double the number of adversarial examples in i.c. |U < 2V, where Vú denotes the number of adversarial examples in (!
S
Now consider the case that | > 2|S/111 By Theorem B.6 (iv), the number of samples from true clusters in !!? is at most + TV 1.02 |
the number W; of adversarial samples in s!?)
least W2 > | 1.02
! > 0.98 | 0.96|C;11 Then, |U4| (C; n (gg s
|C;1 2W,
Finally note that by Theorem B.6 (v), the sets s(2) and S are disjoint from any other sets S(?) and Smy that correspond another component Cj. Therefore, the number of adversarial examples in the s!?? in the second case and s(²) in the first case is smaller than the total number of adversarial examples, i.e.
<(2)
Σ
V
Σ
W4 & (E + w Jn.
( <2
s
(
>2
Therefore, we directly obtain
|U| < Σ (Ct n (
Σ
( ((2))) (S()
Σ
(C: n (()) s!
s <2 |
( >2 |
Σ
2V, +
Σ
2W: + Ow )n & (2s O( )mn.
SEG
EG >2
( mm
22
|
s
S()
Proof of Theorem B.7 (ii) Each iteration before di was selected, removed at most w C samples from Cf, so all previous iterations removed at most Ow samples from C.. Then, by Lemma B.6 (iii), s(?) contains at least (1 n2fow/2 Ou
(w))))))C I)C, samples from Cy. The statement follows then since the event E', we have w" w i < |C*| < w'n 1o
26

---

Proof of Theorem B.7 (iii) Here, either for all i E [k:], 15 n Ci < woo C or i E G and the algorithm had already selected in a previous iteration Mg; E M with | n C > w C
Consider a first case, in which |s n C < "fow | for all E [k]. Then the total number of
samples from true clusters in $ is at most "ow n. Using that | > 100 low n, it follows that more than half of the samples in s(1) are adversarial.
The second case is that |S]] n n > W/o [ for some i E for which in a previous iteration gi we had that | n C wfo [C Note that at most witw C/ the samples in S are not considered adversarial at this point (the ones that were outside S Also, by Theorem B.6 (iv), 5 contains at most W/w n samples from other true clusters. Therefore either more than half the samples in s are considered adversarial or
| < whn |C; + 2wffom & Ow
Proof of Theorem B.7 (iv) Suppose that when the algorithm reaches the else statement we have for some E [k]] that E R and | n C > 20mlool |- We have that |S!! n C is at most [Sm; Cij + IC; /2, where we use that by Theorem B.6 (ii), at most w/ow CC 1/2 samples can fail to be captured by S.a. By Theorem B.6 (iv), furthermore, the number of samples from other true clusters in S!?) is at most wh T.. Therefore, using that | 2| |. the number of adversarial
samples in s(2) is at least
| - ( nC; ww 12 low E 0.45| now > 0.44|
where in the last inequality we used that |s!:|| > 100 n.. Let V be the union, over all i E [k], of all sets S!? such that i R and | C > 20w C Theorem B.6 (v) gives that all such sets Si are disjoint. Therefore at least a 0.44-fraction of the samples in V are adversarial.
Consider now for some [k] how many samples from S SnC; can be outside V when the algorithm reaches the else statement. By Theorem B.6 (ii), Sm) can fail to capture at most w/ow C/ 1/2 samples from C and we have no guarantee that these samples
in V. Consider now the samples in S n C If E R, we may miss up to 20w |C;| of these samples if | n C < 20w
because in this case we do not include s!2) in V. On the other hand, if & R, there are at most 100w samples in Sin n nC; Then the total number of samples from S C outside V is at most I + 20t Jow |C;:| + 100wt n. Summed across all é E [k)], this makes up at most 21w samples.
Overall, the number of adversarial samples in S when the algorithm reaches the else statement is at least
0.44|V|+ + (IS) - |V| 21 n) = |S| - 0.56 - 21 n > 0.44[S) 21w > 0.4[S]
where in the last inequality we also used that |S| > 0.1
F Proof of Proposition 3.5
We now prove lower bounds for the case of Gaussian distributions and distributions with t-th sub- Gaussian moments.
F.1
Case b): For the Gaussian inliers
We first focus on the case when Di(ue) N(u,, I). The proof goes through efficient reduction from the problem considered by Proposition F, to the problem solved by algorithm A.
Proposition F.1 ([5), Proposition 5.11). Let 'D be the class of identity covariance Gaussians on Rd and let 0 < a & 1/2. Then any list list-decoding algorithm that learns the mean of an element of D with failure probability at most 1/2, given access to (1 ad-ddiiiively corrupted samples, must either have error bound 3 Ω( /log L/a) return min(20(d), (1/a)e(1)) many hypotheses.
27

---

First, we describe the means of the components in the input distribution to algorithm A. Let f1..... fig-1 E IRd be any set of k - 1 points with pairwise separation larger than 20 /lglog// 1 //loww Then let pt (iz, 0) E Rd+1 and μr (ūa, 2C / log //Wlow + 1) Rd+ for all E [K 1.. Then M1...., Mi also have pairwise separation larger than 2C' VVvVloog log 1/ 1/Woow
Then, given n points y1...... Us. E Fd as in the input to the problem in Proposition F.1 (i.e. (1 a)- additively corrupted samples), we generate n points that we give as imput to algorithm A as follows: let [1....,n}, n), and then for each of the n points, draw Unif(1,.... point as follows:
and generate the ...if ...
1. i E Ik 1]. sample the point from N (pr, la+1),
2. if = k. sample j S uniformly at random, remove j from S, sample و N(0, 1), and let the point be (v,.g) Rd+11
We note that this construction simulates an input sampled ii.d. according the mixture I N (mg. le+1) +... ( + NNxx Ia-1) + - Q' for some Q'. Then with success probability least 1/2 running A this input with Wlow T returns list L such that there cxists A E L with || - pxll & 3x. Note that this implies that [I()) f < 3x. Finally, we create pruned list L' as follows: initialize L' L and then for each
[k 1] remove all E L' such that A - pall & CVlog 1/Wlow- Then return L/ as the output for the original problem in Proposition F.1.
Let analyze now this output. The separation between the means ensures that any hypothesis E L that is Cylog 1/Wlow to ph is not removed in the pruning. Therefore L' contin- ues to contain a hypothesis is such that II()) - Till & fk. Then, 3 * 5 ((Vlog 1/a) and |Z|| < min(29(d) ((wx + =)//w))=01)) this reduction violates the lower bound of Proposition F.1. Therefore we must have either 3x- = St( (lVlog 1/a) or [L'| > min(2a(d) (1/ (1)))))))))
Finally, we show that these lower bounds on 3a and [z'] imply the desired lower bound for A. Consider first the case: B4 (2(( 1/a). Note that in the input to algorithm A we have Ty = Therefore 3e ( log 1/ax) corresponds the desired lower bound in the lemma statement. Consider second the case: [L'| > min/20(d) (1/Wx))(3) (0))), J. We note that, for each i E [k 1], the original list I. must contain some ji E T. such that || will & C Cvlog 1 1/Wlow- Furthermore, because the means μ4 have pairwise separation larger than 2C /log/ 1/wiow. the original list L must contain at least A- - 1 means of this kind. However, all of these means are removed in the pruning procedure, so |L] >> A bound in the lemma statement. (The choice to make the hidden mean the k-th mean was without loss of generality, the distribution is invariant to permutations of the components.)
+ [L',, so [L| k 1 + min (2 (1/úx) ) This matches the desired lower
F.2 Case a): For distributions with i-th sub-Gaussian moments
The proof for the case when Da( has aab-Gaussian 1-th central moments employs the same reduction scheme, but reduces from Proposition F.2.
Proposition F.2 ([5), Proposition 5.12). Let D be the class of distributions on Ed with bounded t-th central moments for some positive even integer I, and let 0 <a < 2-t-1, Then any list-decoding algorithm that learns the mean of an element of D with failure probability at most 1/2, given access (1 a.) -additivell corrupted samples, must either have error bound 12(a (1/)) or return a list of at least d hypotheses.
Furthermore, in [3], formal evidence of computational hardness obtained (see their Theorem 5.7, which gives a lower bound in the statistical query model introduced by [14]) that suggests obtaining error (2, (///...//// requires running time least d0(1) This was proved for Gaussian inliers and the running time matches ours up constant in the exponent.
28

---

G Stability of list-decoding algorithms
In this section we discuss two of the existing list-decodable mean estimation algorithms for identity- covariance Gaussian distributions and show that they also work when a -facttinctin of the inliers is adversarially removed.
First, we consider the algorithm in Theorem 3.1 in [3]. A central object in their analysis is an "a-good multiset", which a multiset of samples such that all are within distance O(vd) of each other and least a-fraction of them come from (1 (-faac-ftttioon of an i.i.d. set of samples from a Gaussian distribution N (n, Ta). Then their algorithm essentially works as long as the input contains a-good multiset. For our case, after the removal of -faw-ttat of inliers, the input essentially continues to contain (1 "aoowaaggoor good multiset, the algorithm continues work in our corruption model.
Second, we consider the algorithm in Theorem 6.12 in [5]. The main distributional requirement of their algorithm is that Exz.y--- [p2 - y)] & 2. [p²(g - h)] for all degree-(4/2) polynomials p. where S is the set of inliers. Concentration arguments give with high probability that h)]. Furthermore, the distribution over z, y ~ S can be seen as a (1 w )2 f-frrction of the distribution over I, y ~ C Then Fact G.I, which follows by standard probability calculations, also gives that any event under the former distribution can be bounded in terms of the second distribution:
Ce..>---lpp(e (x - y)] & 1.5.g...N(o...
Fact G.1. For any event
P
(A)
P 2.yaC-
(A)/(1
wwoow)
(G.1)
2y
where probabilities are taken over uniform sample from S and C* respectively.
Overall we obtain
S [p2(x - y)1 & 1.5/(1 - ho- -n., ,
-h]],
so for Wlow small enough we have Ex,y-s- (x²(x==)) < 2B M and their algorithm continues to work in our corruption model.
H
Concentration bounds
In this section we prove some concentration bounds essential to our analysis.
Lemma H.1. Let be d-dimensional distribution with mean μ² E Rd and aab-Gaussian t-th central moments with parameter 1. Fix unit vector E Rdd Then
Vt
11 ,², < R > a>D
P
1
R
Proof. We have that
E EL-D(I 1², 10,00, u)²
(t
1)!!
Vi
P 11 10,,)) R &
<
Rt
R
R
where we used that (t 1)!! & 2/2 Vt'.
Lemma H.2. Let D be d-dimensional distribution with mean μ.' Rd and Gau-Gaussian I-th central moments with parameter 1. Let C be a set of i.idd. samples drawn from D. Fix a unit vector
21
E Rd. Then with probability least exp -2|0*
R
Vt
[r E C*, s.l. 1000 n², .))l < R}}> >
1 1-2
R
Proof. The result follows by Lemma H.1 and Binomial tail bound.
29

---

Lemma H.3. Let D be d-dimensional distribution with mean μ. E R and sub-Gaussian t-th central moments with parameter 1. Let C* be set of i..dd samples drawn from D. Fix m unit
vectors U1y.... Um Rd. Then with probability at least 1 exp
(-2
v1.
n
(=ES" s.t. 1/0 n² vil R3
1 2m
|S
xE[m]
Proof. By Lemma H.1 and a union bound over the m directions, we get
f
z~D Plle - vv)l < R. Vi [m]] >
P
m
R
Then the result follows by Binomial tail bound.
I Experimental details
Adversarial line and adversarial clusters The following figure illustrates the adversarial distribu- tions used in Figure and further in this section.
True Cluster
Fake Cluster
Figure 4: Two variants of adversarial distribution: adversarial line (left) and adversarial clusters (right).
Data Distribution We consider mixture of k well-separated (1)s; - رلر > 40) d = 100 dimensional inlier clusters whose subgroup sizes range from 0.3 to 0.02. The experiments are conducted once using a Gaussian distribution and once using a heavy-tailed t-distribution with five degrees of freedom for both inlier and adversarial clusters. In Figure 6 the latter suggests that our algorithm works comparatively well even for mixture distributions which do not fulfill our assumptions. We set Wlow 0.02 and 0.12 so that it is larger than the smallest clusters but smaller than the largest ones and set the total number of data points to 10000. The Gaussian noise model simply computes the empirical mean and covariance matrix of the clean data and samples 1200 noisy samples from a Gaussian distribution with this mean and covariance. The adversarial cluster model and the adversarial model
depicted in Figure 4.
Attack distributions We consider three distinct adversarial models (see Figure for reference).
1. Adversarial clusters: After sampling the inlier cluster means, we choose the cluster with the smallest weight. Let μ4, denote its mean. Then, we sample random direction ee with ||v_|| = 10. After that, we sample three directions 01 U2 and v3 with || = 10. Then we put three additional (outlier) clusters with means μ4, + Ue Us. This roughly corresponds to the right picture in Figure 4. The samples for each adversarial cluster are drawn from distribution that matches the covariance of the inlier clusters, with the sample size being twice as large as of the affected inlier cluster.
2. Adversarial line: After sampling the inlier cluster means, we again choose the cluster with the smallest weight. Let μ. denote its mean. Then, we sample random direction oe with ||o_|| 10. We put three additional (outlier) clusters with means at μl, + Ves Ms + 2v, and '4 + 3v., which form a line shown in Figure 4. The samples are drawn similarly to the adversarial clusters, with the difference that the covariance is scaled by factor of in the direction of the line.
30

---

Kmeans
Robust Kmeans
DBScan
LD-ME
Ours
30
Worst Estimation Ener
50
25
20
30-
15
20
10-
10
Attack
Models
Noise Models
Figure 5: Comparison of five algorithms with three adversarial noise models. On the left we show worst estimation error of algorithms with constrained list size and on the right the smallest list size with constrained error guarantee. We plot the median of the metrics with the error bars showing 25th and 75th percentile. We observe that our method consistently outperforms prior works in terms list size and worst estimation error, with the exception of DBSCAN, which performs similiar level.
Kmeans
Robust Kmeans
DBScan
LD-ME
Ours
Worst Estimation Enrrr
So
25
20
30
15
20
10
Attack 1
Attack Noise Models
Attacck
Attack
Attack 2
Attrakk
Noise Models
Figure 6: Worst estimation error and list size comparison for the case where inlier distributions are ttiled. We can observe numerical stability of our approach.
3. Gaussian adversary: Here we simply introduce noise matching the empirical mean and covariance of all inlier data (i.e., as if all inlier clusters generated from the same Gaussian distribution).
Note that in the first and second attack, the adversary creates clusters that do respect the separation assumption of the true inlier clusters: either adversarial clusters are placed around the smallest inlier cluster (Adversarial Cluster), or the adversarial clusters form a line, pointing out in some fixed direction (Adversarial Line).
Implementation details We implement the list-decodable mean estimation base learner in our InnerStage algorithm (Algorithm 3) based on [8]. It leverages an iterative multi-filtering strategy and one-dimensional projections. particular,
the simplified gaussian version of the algorithm. It is designed for distributions sampled from a Gaussian but also shows promising results for the experiments involving heavy-tailed t-distribution as depicted in Figure 6. The robust mean estimator used to improve the mean hypotheses for large clusters is omitted in our implementation.
alyeer-parameter search and experiment execution The parame-arameters of our algorithm tuned beforehand based on the experimental setup. For the comparative algorithms, hyper- parameter searches are conducted within each experiment after initial tuning. For our algorithm, key parameters include the pruning radius used in the OuterStage routine (Algorithm 6) and 3 used in the InnerStage (Algorithm 4). In addition, parameters for the LD-ME base learner, such as the cluster concentration threshold, also require careful selection, resulting in total of 7 parameters. The tuning for these was performed using a grid search comparing about different configurations. Similarly, we independently tune the vanilla LD-ME algorithm, which run with Wlow as weight parameter. For
31

---

Attack
Attack
Worst Estimation Error
KEARE LOnl
Worst Estimation Enor
Krarre Loel
Attack
Worst Estimation Error
Cinass OBSoan
Ust Size
Figure 7: Scatter plot of all results for one iteration of the experiment using three adversarial noise models.
DBSCAN, we optimize the list size and error metrics by searching over range of 100 values for which controls the maximum distance between samples considered in the same neighbourhood. The minimum samples threshold, which validates the density based clusters, is pretuned beforehand and adjusted based on Woow For k-means and its robust version, utilizing a median-of-meant weighting scheme, we explore 21 values for k including the true number of clusters. Fach parameter setting is executed 100 times to account for stochastic variations in the algorithmic procedures, such as k-means initialization. The list size and worst estimation error for each list of clusters obtained is visualized exemplarily for one iteration of the experiment in Figure 7. The plot provides insight into how the different algorithms perform and vary with different list sizes.
Evaluation details Note that we have two sources randomness: the data is random and also the algorithms themselves random (except DBSCAN). For a clear comparison, one dataset for each attack model. we plot the performance of 100 runs of each algorithm for each parameter setting, each time recording the returned list size together with the worst estimation error max minger. r. I,l; - ji|l- Then we either (i) report the worst estimation error for all runs with constrained list size (we pick the list size most frequently returned by our algorithm, specifically or 10 in our experiments) (see Figure 5, left), or (ii) report the smallest list size required to achieve the same or smaller worst estimation eπror (we pick the 75th quantile of errors of our algorithm for a threshold) (see Figure 5, right). Under size constraint (i), the bar plots correspond to the median over the runs, with error bars indicating the 25th and 75th quantiles. Under error constraint (ii), the bar plots represent the minimum list size for which the median over the runs falls below the threshold, while the error bars show the minimum list size for which the 25th and 75th quantiles meet the constraint. Note that "n/a" indicates that, within the scope of our parameter search, no list size achieves an error below the specified constraint.
sample and fix
In Figure 6 we study the numerical stability of our approach. In particular, whether the performance degrades when inlier distribution does not satisfy required assumptions. We observe that if one uses our meta-algorithm with base learner designed for Gaussian inliers, we still obtain stable results even in the case of ttaved inlier distribution.
L.1 Variation of Wlow
To study the effect of varying Wlow input on the performance of our approach and LD-ME, we introduce a new noise model. As illustrated in Figure 8, we consider a mixture of = well- separated clusters: one small cluster with weight of 0.045 and two large clusters, each with weight of 0.2. We place two adversarial clusters (see paragraph on attack distributions for details): one near the small cluster and another near one of the large clusters. Furthermore, uniform noise is introduced,
32

---

True Cluster
Fake Cluster
Uniform noise
Figure 8: Setup for Wlow variation experiment with clusters contaminated by an adversarial cluster and uniform noise. Lower color intensities indicate smaller cluster weights.
Worst Estimation Error
Worst Extimation Error
0.7
ME
LD
0.6
0.5
0.4
Winn
Winn
50-
Dur LD-VE
Figure 9: Comparison of list size and estimation error for small and large inlier clusters for varying Whow inputs. The experimental setup is illustrated in Figure 8. The plot on the top left shows the estimation error for the small cluster and the plot the top right shows the error for the large cluster. We plot the median values with error bars indicating 25th and 75th quantiles. As Wlow decreases, our algorithm maintains a roughly constant estimation error for the large cluster, while the error for LD-ME increases.
spanning the range of the data generated by the inlier and its nearby outlier cluster and accounting for 10% of the data in this region. Overall, 0.56 and we draw 22650 samples from this mixture distribution.
For both algorithms the weight of the largest inlier cluster. In Figure 9, we plot the median estimation error with error bars showing the 25th and 75th quantiles for the small cluster (top left) and the large cluster near the outlier cluster (top right). As expected from our theoretical results, we observe that our algorithm performs roughly constant in estimating the mean of the large cluster, regardless of the initial Whow- Meanwhile, the estimation error of LD-ME increases as W)ow decreases further below the true cluster weight. Furthermore, the plots show that our approach does consistently outperform LD-ME in terms of both worst estimation error and list size. Figure 10 also compares the performance of the clustering algorithms in this experimental setup with results similar the ones obtained in the previous experimental settings.
100 seeds for each Wlow ranging from 0.02 to 0.2, which corresponds to
I.2 Computational resources
Our implementation of the algorithm and experiments leverages multi-threading. It utilizes CPU resources of an internal cluster with 128 cores, which results in a execution time of about minutes for single run of the experiment for one noise model with 10000 samples. We remark that classic
33

---

Estimation
List Size
Kmeans
Robust Kmeans
DBScan
LD-ME
Size
1/0
0//
Figure 10: Worst estimation error and list size comparison for the setup used in the Wlow variation experiment.
approaches like k-means and DBSCAN perform fast and the most time-consuming part is the execution of the LD-ME base learner. Given experimental setup with three noise models, it takes about 15 minutes to reproduce all our results for one data distribution.
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We summarized our contributions in Table in the introduction, and all the claims made there (including more general results) appear in Section 3 and Appendix C.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of theoretical results in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
35

---

Our assumptions are stated in Sections 2 and 3, in particular Assumption 3.1. The complete proof is given in Appendix C.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide experimental details, including explanation of the adversarial noise distribution in Appendix I.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
36

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We uploaded zip archive containing the code together with instructions on how to reproduce the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
wtaeeeeeeeoooeeeeaaeeieiiiiooeee onoolicy))yy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /ttpppcc/ppulliieee htt//uubicggguue weaicccgguee//eeeee htt////ooSuumssseeeeeeeeee ceiooomissiooooooooioooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide short version of experimental details Section and more detailed one in Appendix I.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: As described in Appendix I, we plot the median of the metric (error or list size) accompanied by the 25% and 75% percentiles, acting error bars. The statistics was collected over 100 reruns of all algorithms under comparison.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
37

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide experimental details, including computational resources, in Ap- pendix
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We reviewed the NeurlPS Code of Ethics and confirm that our paper respects
it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Main focus our result is to deepen our theoretical understanding of funda- mental problems in statistics, such mixture learning.
Guidelines:
38

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: To the best of our judgement, our paper does not pose misuse risks, as it has theoretical focus.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our work does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
39

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddataees has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work does not use release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
40

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
41


Reviews:
[{"review_id": "aQqRBegwML", "reviewer": "Reviewer_izza", "summary": "The paper studies the problem of estimating the means of a mixture model in the presence of outliers. More specifically, each component has unknown weight $w_i$ that is lower bounded by a known quantity $w_{\\mathrm{low}}$, each component is assumed to be (sub)-Gaussian, and the mixture also includes an adversarially selected distribution (outliers) with weight $\\epsilon$, which can in general be larger than $w_{\\mathrm{low}}$, meaning that the outliers can form entire clusters on their own. Correctly estimating the means of all true components is impossible and thus the goal here is to instead output a small list of candidate means. Since the $w_i$’s are unknown, naive applications of existing list-decoding algorithms would result in estimation errors and list size guarantees that are a function of $w_{\\mathrm{low}}$ only. The contribution of this paper is to show that it is indeed possible to obtain more fine-grained guarantees where the error for the $i$-th component scales with $w_i$ instead of $w_{\\mathrm{low}}$ and the list size is equal to the true number of components plus a small overhead $O(\\epsilon/w_{\\mathrm{low}})$. Regarding the list-size, $\\epsilon/w_{\\mathrm{low}}$ is the number of extra components that the outliers can form, thus this term is unavoidable in the list size. The paper provides information-theoretic error lower-bounds justifying that the precise error rates achieved are qualitatively tight. The regimes where the final algorithm has qualitatively best-possible performance includes the cases where the means are pairwise separated as well as without that assumption, and also the case where $\\epsilon \\ll w_0$ for separated mixtures (where it matches existing qualitatively optimal algorithms).\n\nThe algorithm (for the separated components case) in based on the following parts shown in the paper: First, there is a way to obtain list-decodable mean estimation algorithms that do not need knowledge of the fraction of inliers. This works by collecting the answers of a list-decodable mean estimator for multiple candidate values for the fraction of inliers and carefully pruning the results to keep only hypothesis with a large number of points close to them. Second, the paper proposes a procedure that splits the dataset into (not too many) parts where each part includes at most one (almost entire) cluster of inliers, so that calling the agnostic list-decodable mean estimation of the previous sentence can produce the improved error guarantees. Finally, for the case where $\\epsilon \\ll w_{\\mathrm{low}}$, existing robust mean estimation algorithms can be employed to further improve the error.\n\nOverall, the paper closes a gap in the literature. The result is non-trivial and a useful addition to the literature, thus I am recommending acceptance.", "questions": "* The algorithm that gets errors all the way down to $O(\\sqrt{\\log(1/w_i})$ has super-polynomial complexity. Does the existing SQ lower bound from list-decodable mean estimation in [3] justify this via some easy reduction? If so, it would be good to include.\n\n* Is the optimal separation for the bounded moments case indeed $O(1/w_{\\mathrm{low}}^{4/t})$? I just want to make sure that there is no typographical error in the exponent, since for bounded second moments usually things scale with square root of $w_\\mathrm{low}$.\n\n* Also see first point in \"weaknesses\".", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* A positive point of the algorithm is that it is a meta-algorithm, in the sense that only performs calls to existing algorithms (for list-decoding and robust mean estimation), and performs computationally simple processing of the dataset based on the outputs of these algorithms. The algorithm is thus efficient and takes advantage of computational efficiency of the base learners.\n\n* The paper contains some experiments to demonstrate practical performance advantages.", "weaknesses": "* The contamination model of eq (2.1) requires that corruptions come i.i.d. from some distribution. Since the base learners can also handle some adversarial corruptions why can’t the final algorithm work for fully adversarial contamination?\n\n* On presentation: The result about non-separated mixtures is not discussed in the main body. It would be good to at least provide the main ideas regarding why similar error can be achieved for the non-separated case, since the algorithm discussed in the main body seems to use crucially the separation of components. Another slightly confusing point is that the introduction talks about Gaussianity a lot while Theorem 3.3 works even for bounded second moment distributions. Existing black box learners work for these settings too but for some reason the existence of black box learners is emphasized only for the Gaussian case (line 193) in Section 3.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and for the feedback which will help to improve it. Below, we address specific comments and questions.\n\n> The contamination model of eq (2.1) requires that corruptions come i.i.d. from some distribution. Since the base learners can also handle some adversarial corruptions why can’t the final algorithm work for fully adversarial contamination?\n\n\nThank you for the question, please see our general rebuttal response (first part).\n\n> On presentation: The result about non-separated mixtures is not discussed in the main body. It would be good to at least provide the main ideas regarding why similar error can be achieved for the non-separated case, since the algorithm discussed in the main body seems to use crucially the separation of components. \n\nThank you for the suggestion, we will mention the result on non-separated mixtures in the main text in the revised version. \n\n> Another slightly confusing point is that the introduction talks about Gaussianity a lot while Theorem 3.3 works even for bounded second moment distributions. Existing black box learners work for these settings too but for some reason the existence of black box learners is emphasized only for the Gaussian case (line 193) in Section 3.1.\n\nThank you for the suggestion, we will extend the discussion on the results for the bounded moment distributions in the revised version.\n\n> The algorithm that gets errors all the way down to $𝑂(\\sqrt{\\log⁡(1/w_i)})$ has super-polynomial complexity. Does the existing SQ lower bound from list-decodable mean estimation in [3] justify this via some easy reduction? If so, it would be good to include.\n\nYes, there is a simple reduction of SQ lower bounds (same as IT lower bounds), we mentioned it in the Appendix (lines 1001-1004). We will move the paragraph to the main text in the revised version.\n\n> Is the optimal separation for the bounded moments case indeed $O\\left(\\left(\\frac{1}{w_{\\text{low}}}\\right)^{4/t}\\right)$? I just want to make sure that there is no typographical error in the exponent, since for bounded second moments usually things scale with square root of $w_{\\text{low}}$.\n\nThank you for raising this point. Yes, there is no typographical error (please see our general rebuttal response, second part).", "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": "", "extra_scores": {}}, {"review_id": "zN1ZFs3oSI", "reviewer": "Reviewer_fDjD", "summary": "This submission considers the problem of list-decoding the means of a mixture of $k$ sub-Gaussian components, under adversarial *additive* contamination which can have size $\\epsilon n$ larger than the smallest-weight component. Instead of only yielding guarantees scaling with the known component weight lower bound $\\alpha_{low}$, the (meta-)algorithm in this paper achieves error that depends directly on $w_i$, the weight of that particular component, and decays also with $\\epsilon$. Furthermore, the size of the output list is guaranteed $k + O(\\epsilon/\\alpha_{low})$ instead of the more common and weaker $O(1/\\alpha_{low})$ guarantee.\n\nNote: this is an emergency review, so I did not read the paper as closely and carefully as I'd like.", "questions": "- Any intuition for why $w_{low}^2$ is the right quantity to compare with $w_i$ and $\\epsilon$? Is it a necessity of the problem setting or is it just an artifact of the algorithmic construction?\n\n- Definition 2.1 is essentially assuming boundedness compared to the identity covariance Gaussian. For mixtures where the components have, say, covariance bounded by $c$ times identity, does the algorithm need to know $c$, or can $c$ be estimated easily in this context?\n\n- How hard is it to go beyond the corruption model of (2.1), to get *adaptive* additive corruption? That is, the corruption isn't just drawn from a fixed $Q$, but that the corrupted points can depend directly on the drawn inlier samples?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "To me, the main strength of the paper lies in identifying the regimes where much stronger guarantees (e.g. mean estimation error dependence on actual component weight and not just $\\alpha$) can be made compared to prior works, which are worst-case optimal in some sense of the phrase. The (meta-)algorithmic ideas are also simple enough to be implemented (which I consider a plus and not a minus).", "weaknesses": "- The introduction claims results even when there is no separation between mixture components, but Theorem 3.3 makes a separation assumption? Did I miss something?\n\n====\n\nBelow are hopefully some constructive feedback that the authors can use to improve the paper:\n\n- These guarantees seem possible only because of the distance separation vs concentration assumption (both depend on \"$t$\"), and I think there needs to be more discussion of the intuition on the quantitative tradeoff in the main body.\n\n- The contexualization in prior work seems incomplete to me. I have two related complaints, both (roughly) related to finite covariance assumption setting.\n\n1. The $\\epsilon \\gg \\min_i w_i$ regime seems to me *almost* covered by the standard setting of learning the means of finite covariance mixtures: the contamination distribution $Q$ can always be trimmed a little bit to get finite covariance, and just be regarded as part of the mixture. Upon googling, it seems that there is more recent work by Diakonikolas, Kane, Lee and Pittas (Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation) which does handle such mixtures, and in fact components with different covariance sizes. I guess the caveat is that, under the above modelling, the mean of $Q$ might not be sufficiently bounded away from the genuine components. Is my understanding correct? I think a comparison to finite-covariance mixture learning literature, from the framework perspective, would be helpful.\n\n2. The intro of this submission really focuses on the sub-Gaussian mixture case ($t \\approx \\log 1/w_{low}$), but the general result applies also to $t = 2$. So I think a direct comparison to the technical results of the above paper as well as DKKLT22 is needed. For example, the separation assumption in this submission is much larger ($1/w_{low}^2$) than these prior works ($1/\\sqrt{w_{low}}$). In general, I think it'd be very useful to clarify the results in this paper with respect to these DKKLT22 and DKLP papers (and other related works).\n\n- Writing: Section 3.1 was quite dense to read (though possibly because I have to read it quickly for the emergency review). It might be better to present the Gaussian case and the relation to prior work, before presenting the full result in generality and explaining precisely the generalizations.\n\n- Minor thing in line 114: I'm not sure it's strictly true that \"in most robust estimation problems, the fractions of inliers and outliers are usually provided to the algorithm\". Doesn't filtering work even if the number of outliers is unknown, as long as the inlier variance is known? One could keep filtering until the remaining data set has small-enough covariance?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and for the feedback which will help to improve it. Below, we address specific comments and questions.\n\n> The introduction claims results even when there is no separation between mixture components, but Theorem 3.3 makes a separation assumption? Did I miss something?\n\nThank you for the comment. Yes, we also obtain a result for the non-separated case. See lines 241-243 in the main text, and Corollary C.4 in the Appendix. In the revised version we will move the corollary statement to the main text.\n\n> These guarantees seem possible only because of the distance separation vs concentration assumption (both depend on $t$), and I think there needs to be more discussion of the intuition on the quantitative tradeoff in the main body.\n\nIndeed, this trade-off is inevitable and is present in prior works too. Please also see our discussion on the separation assumption in the general rebuttal (second part). \n\n> Upon googling, it seems that there is more recent work by Diakonikolas, Kane, Lee and Pittas (Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation) which does handle such mixtures, and in fact components with different covariance sizes. I guess the caveat is that, under the above modelling, the mean of $Q$ might not be sufficiently bounded away from the genuine components. Is my understanding correct? I think a comparison to finite-covariance mixture learning literature, from the framework perspective, would be helpful.\n\nYour understanding is correct, after the trimming operation, $Q$ is not guaranteed to be separated from the other components. This does not allow to model $Q$ as a part of the mixture. \nWe will add a comparison with the DKLP work in the revised version (also see general rebuttal response).\n\n> The intro of this submission really focuses on the sub-Gaussian mixture case ($t \\approx \\log⁡ 1 / w_{\\text{low}}$), but the general result applies also to $t = 2$. So I think a direct comparison to the technical results of the above paper as well as DKKLT22 is needed. For example, the separation assumption in this submission is much larger $1 / w_{\\text{low}}^2$ than these prior works $1 / \\sqrt{w_{\\text{low}}}$. In general, I think it'd be very useful to clarify the results in this paper with respect to these DKKLT22 and DKLP papers (and other related works).\n\nThank you for the comment, please see our discussion on the separation assumption in the general rebuttal (second part), where we also compare with [DKLP23]. We will extend the comparison with prior work in the revised version.\n\n> It might be better to present the Gaussian case and the relation to prior work, before presenting the full result in generality and explaining precisely the generalizations.\n\nThank you for your suggestion, we will take this into consideration for the revised version.\n\n> I'm not sure it's strictly true that \"in most robust estimation problems, the fractions of inliers and outliers are usually provided to the algorithm\". Doesn't filtering work even if the number of outliers is unknown, as long as the inlier variance is known? One could keep filtering until the remaining data set has small-enough covariance?\n\nThank you for your comment, this was indeed an imprecise choice of words.\nWe were mostly referring to the list decoding setting, where algorithms are provided with inlier proportion (see, e.g., [1, 2]). Here, the extension to the unknown inlier proportion seems challenging for the following two reasons:  \nFirst, e.g., for the filtering technique, in order to obtain optimal error, one needs to filter with the ‘correct’ polynomial degree, and this degree depends on the fraction of inliers.  \nSecond, in order to obtain a list of predictions, a lower bound on the size of inlier sets is required, in order to decide when to ‘discard’ too small subsets.  \nOverall, we argue that it is not straightforward to extend prior methods to unknown component weights, and this extension is one of our contributions.\n\n> Any intuition for why $w_{\\text{low}}^2$ is the right quantity to compare with $w_i$ and $\\varepsilon$?\n\t\nThank you for the question. First, we would like to note that it is generally not possible to obtain guarantees depending only on $w_i / (w_i + \\varepsilon)$, since there are always samples from other components which are effectively ‘outliers’ for a fixed component. For example, consider the Gaussian case with $\\varepsilon = 0$, and $w_i / (w_i + \\varepsilon) = 1$, but the approximation error is clearly greater than $0 = \\sqrt{\\log (w_i + \\varepsilon) / w_i)}$. \n\nFurther, the specific value $w_{\\text{low}}$ connects to the separation assumption (see discussion on the necessity of the separation assumption in the general response): if the components are $\\Omega\\left(\\left(1 / w_{\\text{low}}\\right)^{4/t}\\right)$ separated, only an $O(w_{\\text{low}}^4)$ fraction of samples from one mixture component may lie in the vicinity of another, so in total $O(w_{\\text{low}}^3) \\leq w_{\\text{low}}^2$ points from other components. We also remark that $w_i$ always dominates $w_{\\text{low}}^2$.  \n\n\n> Definition 2.1 is essentially assuming boundedness compared to the identity covariance Gaussian. For mixtures where the components have, say, covariance bounded by 𝑐 times identity, does the algorithm need to know 𝑐, or can 𝑐 be estimated easily in this context?\n\nWe assume that the algorithm knows at least a valid upper bound (and obtain guarantees depending on this upper bound). We leave the question of unknown covariances for future work (the main challenge here is to still obtain a small list size $k + O(\\varepsilon / w_{\\text{low}})$, while correctly ‘guessing’ the covariance).\n\n> How hard is it to go beyond the corruption model of (2.1), to get adaptive additive corruption?\n\nThank you for the question, please see our general rebuttal response (first part).\n\n---------\nFor references [1, 2], please see the main rebuttal response.", "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": "", "extra_scores": {}}, {"review_id": "IM6ODVxPc5", "reviewer": "Reviewer_w5FP", "summary": "The authors investigate the problem of mean estimation for a well-separated mixture in the presence of arbitrary outliers introduced by an adversary. They propose a meta-algorithm that leverages robust mean estimation algorithms as base learners, each with a set of prescribed properties. The authors provide an error guarantee of $\\mathcal{O}(\\sqrt{\\log \\frac{\\epsilon}{w_i}})$ for a list size of $k + \\mathcal{O}(\\frac{\\epsilon}{w_{low}})$, where $k$ is the total number of inlier groups, $\\epsilon$ is the proportion of outliers, and $w_i$ is the proportion of inlier group $i$. Additionally, their approach is capable of handling cases where some $w_i \\leq \\epsilon$.", "questions": "Please see above.", "limitations": "The limitations are adequately addressed.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The main contribution of the paper lies in developing the meta-algorithm (Algorithm B.1) which first creates clever partitions of the original set (Algorithm D.1) and then uses the appropriate base learners on the partitioned sets (Algorithm C.1). While I have not gone through the mathematical details very carefully, the results seem very interesting and match the error guarantees of base learners run with the full information on the weight proportion of each inlier group separately. The paper is written well and the ideas and corresponding arguments are presented clearly in the main paper with technical details deferred to the appendix.", "weaknesses": "The paper makes significant contributions, and I did not identify any particular weaknesses. While I possess general knowledge of the research area, I am not an expert, and my review should be considered within that context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work.", "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": "", "extra_scores": {}}, {"review_id": "ApMgf7BQcj", "reviewer": "Reviewer_hCCi", "summary": "This paper addresses the problem of estimating the means of well-separated mixtures in the presence of adversarial outliers, a scenario where traditional algorithms may fail. The authors introduce the concept of list-decodable mixture learning (LD-ML), which is particularly relevant when outliers can outnumber smaller inlier groups.", "questions": "1. Have you considered validating your algorithm on real-world datasets? If so, could you provide details on these experiments? If not, what were the main obstacles?It would be beneficial to include results from real-world datasets to demonstrate the practical utility and robustness of your method.\n\n2. How does your algorithm perform when the assumption of well-separated mixture components does not hold? Have you tested its robustness in such scenarios?  \n\n3. Can you provide a detailed analysis of the computational complexity of your algorithm? How does it scale with the number of dimensions and mixture components? \n\n4. How does your algorithm compare to other state-of-the-art robust learning methods in terms of practical performance metrics like runtime and ease of implementation?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a new problem formulation (LD-ML) and a creative combination of existing ideas (base learners for adversarial corruptions) to solve it. This originality addresses significant limitations in prior work, enhancing the robustness and applicability of mixture learning algorithms. The research quality is high, with rigorous theoretical analysis and well-designed experiments. The thoroughness of the proofs and the clarity of the theoretical contributions reflect a strong understanding of the subject matter.", "weaknesses": "The paper did not include real-world datasets and additional robust learning methods for comparison. It would be great if the impact of the assumptions can be clarified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and for the feedback which will help to improve it. Below, we address specific comments and questions.\n\n**Experimental evaluation**\n\n> The paper did not include real-world datasets and additional robust learning methods for comparison. [...] Have you considered validating your algorithm on real-world datasets? If so, could you provide details on these experiments? If not, what were the main obstacles? It would be beneficial to include results from real-world datasets to demonstrate the practical utility and robustness of your method. [...] How does your algorithm perform when the assumption of well-separated mixture components does not hold? Have you tested its robustness in such scenarios?\n\nWe would like to emphasize that the focus of our work is to first introduce the LD-ML framework and prove theoretical guarantees in this setting for an efficient algorithm. We agree that for the purpose of properly evaluating the effectiveness of the algorithm in practice we would need a much more extensive experimental setup that would be out of scope for this paper and we leave it for future work. \n\nHaving said that, it would be great if the reviewer could point to the specific robust learning methods (beyond the ones considered in the paper) they have in mind. For our experimental results, we opted for comparing our algorithm with 1) baselines that have provable guarantees in our setting (list decoding algorithm) and 2) three commonly used in practice clustering algorithms: (k-Means, robust k-Means and DBSCAN).\n\n>  It would be great if the impact of the assumptions can be clarified. [...] How does your algorithm perform when the assumption of well-separated mixture components does not hold? Have you tested its robustness in such scenarios?\n\n\nWe will clarify the assumptions (in particular, we have a result which does not require well-separateness assumption) in the revised version. For example, Corollary C.4 answers the question about the impact of the well-separateness assumption, by showing the guarantees when the components are non-separated. We can move it to the main text so that the impact is more explicit in the main text.\n\nFurthermore, in our experimental design we effectively included the setting where clusters are not separated (by inserting 'adversarial' clusters in the vicinity of the inlier component). Therefore, results in Figure 2 can also be interpreted as results for non-separated clusters (by assuming that the inserted clusters around the smallest cluster are part of the mixture). \n\n> Can you provide a detailed analysis of the computational complexity of your algorithm? How does it scale with the number of dimensions and mixture components?\n\nThank you for your suggestion. Please see our general rebuttal response (third part) for the detailed analysis of the computational complexity.", "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": "", "extra_scores": {}}, {"review_id": "HYYficeKaA", "reviewer": "Reviewer_TTHY", "summary": "In this paper, the authors introduce the list-decodable mixture learning problem, which can be considered as the extension of the list-decodable mean estimation problem. In such case, data is drawn from a weighted mixture of $k$ inlier distributions and an adversarial outlier distribution. A notable aspect of this paper’s problem setting is that the fraction of outlier $\\varepsilon$ can exceed the  fraction of certain inlier clusters $w_i$s. As a result, the required list size is at least $k+\\varepsilon/\\min w_i$. In this paper, The primary objective of this study is to compute a compact list $L$ of means such that for any $\\mu_i$ of an inlier group, there exists $\\hat{\\mu}\\in L$ with a sufficiently small $\\| \\hat{\\mu}-\\mu_i \\|$. The only known knowledge is $w_{low}$, a lower bound of all $w_i$s.\n\nThe algorithm proposed by the author is meta in the sense that it uses other algorithms (Robust Mean Estimation and List-Decodable Mean Estimation) as base components. It comprises two stages outlined as follows:\n\n1. outer stage: Iteratively separates the inlier clusters from each other and from the outliers. This stage produces the collection of sets $\\mathcal{T}$ satisfying certain properties. Then for every $T\\in \\mathcal{T}$, run the inner stage.\n2. Inner stage: uses the cor-kLD algorithm to derive the cor-aLD algorithm that restricts access to the $\\alpha_{low}$ s.t. $\\alpha_{low}\\leq \\alpha$. In this stage, for every $T\\in \\mathcal{T}$, a refined list of mean estimates is produced.", "questions": "- The paper lacks a presentation of the time complexity, and the experimental part also fails to provide results from this aspect. It would be beneficial to include information regarding the time complexity of the proposed algorithm to provide a comprehensive understanding of its computational efficiency.", "limitations": "not applicable", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This study is interesting. It appears to be the first one to address the challenge of mixture learning in cases where outliers overwhelm small inlier groups\n- The problem setting of this paper is practical. The algorithm is designed to work with limited information, only having access to the lower bound of inlier group fractions.\n- The paper presents theoretical lower bounds for the error. Remarkably, the proposed meta-algorithm achieves a matching lower bound.", "weaknesses": "- The two stage meta-algorithm can be time-consuming.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and for the feedback which will help to improve it. Below, we address specific comments and questions.\n\n> The two stage meta-algorithm can be time-consuming. [...] The paper lacks a presentation of the time complexity, and the experimental part also fails to provide results from this aspect. It would be beneficial to include information regarding the time complexity of the proposed algorithm to provide a comprehensive understanding of its computational efficiency.\n\nThank you for your comment. We provided a detailed analysis of the time complexity in the general rebuttal response (third part). In particular, our meta-algorithm has a small overhead complexity compared to base learners. We will include this discussion in the revised version.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their valuable feedback and comments, which help to improve our manuscript. Below, we focus on three main concerns, which were raised by several reviewers.

**Adaptive contamination**.  
We prove robustness of our algorithm in the non-adaptive contamination model, where $\varepsilon$ proportion of data are i.i.d. samples from an adversarial distribution $Q$. The reviewers asked whether our results can be applied to adaptive (non-i.i.d.) contaminations, or whether this is a limitation of our method.  
The proof of Theorem 3.3 only uses the concentration of inlier samples, and thus generalizes to the case of adaptive contaminations. However, recall that the guarantees of our meta-algorithm depend on the base learner guarantees. Therefore, as long as both base learners (RME and LD-ME) have guarantees under adaptive contaminations, so does our meta-algorithm.  

For RME, state-of-the-art methods are indeed robust against adaptive adversaries. However, to the best of our knowledge, results for LD-ME (see, e.g., [1, 2]) are generally only stated for the non-adaptive contamination model. This limits our result to only i.i.d. contaminations.


**Optimality of separation requirements.**  
In our paper, we present two sets of results: for non-separated (in the Appendix, Corollary C.4) and separated mixtures (Theorem 3.3, Corollary 3.4). In the former case, we note that for the smallest component, our algorithm has optimal guarantees. In particular, it is impossible to achieve asymptotically smaller error (even when $\varepsilon = 0$) unless the algorithm outputs an exponentially larger list size (see lines 238 - 243).  
For separated components, we discuss the Gaussian distribution and distributions with sub-Gaussian $t$-th central moments separately.
For the case of Gaussian components, our separation requirements are $\Omega\left(\sqrt{\log 1 / w_{\text{low}}}\right)$, matching the information-theoretical lower bound for the separation (see [1]).  

For general $t$, we require separation $\Omega\left(\left(1 / w_{\text{low}}\right)^{4 / t}\right)$ and the reviewers are correct in pointing out that there exist recent prior works on clustering of mixture models which require only separation $\Omega\left(\left(1 / w_{\text{low}}\right)^{1 / t}\right)$ (see, e.g., [3]). However, e.g., in [3], this comes at the expense of a larger list size $O(1 / w_{\text{low}})$ (see Theorem 3.1 in [3]).  
Next, we provide intuition why, for a desired short list size $k + O(\varepsilon / w_{\text{low}})$, obtaining results under separation $\Omega\left(\left(1 / w_{\text{low}}\right)^{1 / t}\right)$ is challenging:  
Note that at this separation, only a constant fraction of initial mass of the cluster stays ‘close’ to the cluster mean; the other constant fraction will be further away from the mean than $O\left(\left(1 / w_{\text{low}}\right)^{1 / t}\right)$. For our goal to prove the list size bound $k + O\left(\varepsilon / w_{\text{low}}\right)$, we require that such ‘left-over’ samples are not misinterpreted by the algorithm as separate clusters (see lines 674 - 697, the proof of Lemma B.7). Otherwise, we cannot guarantee list size better than $O\left(1 / w_{\text{low}}\right)$, which can be much larger than $k + O\left(\varepsilon / w_{\text{low}}\right)$.  

Overall, the reason for our separation requirements is that 
1. We consider the setting with a large adversarial part, which was not present in the literature before,
2. We guarantee optimal list size $k + O\left(\varepsilon / w_{\text{low}}\right)$.

We will add a detailed discussion on the separation assumption in the revised version and leave the very interesting question of relaxing the separation assumption for future work.

**Time complexity.**  
Several reviewers asked for a detailed exposition of the computational complexity of our meta-algorithm. We would like to highlight that the main purpose of our work is to show the existence of a (quasi-)polynomial-time meta-algorithm with the proven performance guarantees. Our meta-algorithm uses RME and LD-ME base learners, thus it depends on their time complexity, and we did not optimize for the particularly fast and iteration-efficient implementation of our algorithm.  
For the rebuttal we provide the following upper bounds on the time complexity (ignoring the RME base learner, which is generally faster than LD-ME learner): 
$$\text{Inner stage:} \quad \tilde O\left(\left(\frac{1}{w_{\text{low}}}\right) T(n, w_{\text{low}}) + \left(\frac{1}{w_{\text{low}}}\right)^3 n\right),$$ where $T(n, w_{\text{low}})$ is the time for LD-ME base learner to run on a dataset with $n$ samples and $w_{\text{low}}$ fraction of inliers.
$$\text{Outer stage:} \quad O\left( T(n, w_{\text{low}}) + \left(\frac{1}{w_{\text{low}}}\right)^2 n\right).$$
$$\text{Full algorithm:} \quad \tilde O\left(\left(\frac{1}{w_{\text{low}}}\right) T(n, w_{\text{low}}) + \left(\frac{1}{w_{\text{low}}}\right)^4 n\right).$$
We leave the question of more efficient implementations for future work.

[1] Diakonikolas, Ilias, et al. "List-decodable robust mean estimation and learning mixtures of spherical gaussians." Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018.  
[2] Cherapanamjeri, Yeshwanth, et al. "List decodable mean estimation in nearly linear time." 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2020.  
[3] Diakonikolas, Ilias, et al. "Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation." arXiv preprint arXiv:2312.11769 (2023).

Meta-review: This paper provides novel algorithmic guarantees for an appropriate notion of clustering mixtures of separated structured distributions, including Gaussians. The work can handle the outlier-robust case where the fraction of outliers can be larger than the smallest cluster, at the expense of outputting a list of candidates for the means of the clusters. Overall, the reviewers agreed that this is an interesting contribution. Detailed discussion with a couple of reviewers revealed that additional comparison (and missing citations) to prior work would make the contributions of this work more transparent. The authors are encouraged to address these points in the revised version of their paper.
Decision: Accept (poster)