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
eth  zurich
t u munich
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:48:25

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.

Main paper: 
 introduction: 
 Estimating the mean of a 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 of interest that is often not precisely measurable. In practical applications, data frequently originates from a mixture of multiple groups (also called subpopulations) and a natural goal is to estimate the distinct means of each group separately. For example, we might like to use representative individuals to study how a complex decision or 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 a list of 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 to find good mean estimates for all inlier groups even when the proportion of such additive adversarial contaminations is larger than some smaller groups that we want to properly represent. The central open question that motivates our work is thus:What is the cost of efficiently recovering small groups that may be outnumbered by outliers?More specifically, consider a scenario where the practitioner would like to recover the means of small but significant enough inlier groups which constitute at least w low ∈ (0, 1) proportion of the (corrupted) data. If k is the number of such inlier groups, for all i ∈ [k], we then denote by w i ⩾ w low the unknown weight of the i-th group with mean µ i . Further, we use ε to refer to the proportion of additive contamination -the data that comes from an unknown adversarial distribution. The goal is to estimate the unknown means µ i for all i ∈ [k].Existing works on robust mixture learning such as [3, 4] consider the problem when the fraction of additive adversarial outliers is smaller than the weight of the smallest subgroup, i.e. ε < w low . However, for large outlier proportions where ε ⩾ w low , these algorithms are not guaranteed to recover small clusters with w i ⩽ ε. 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 (LD-ML), following the footsteps of a long line of work on list-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 a 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 at least |L| ⩾ k + ε mini wi . Here, ε mini wi can be interpreted as the minimal list-size overhead that is necessary due to "caring" about groups with weight smaller than ε. 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 wi , while being agnostic to w i aside from the knowledge of w low . Furthermore, we are interested in computationally efficient algorithms for LD-ML, especially when dealing with high-dimensional data.To the best of our knowledge, the only existing efficient algorithms that are guaranteed to recover inlier groups with weights w i ⩽ ε 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 α ⩽ 1/2 and 1 -α respectively. Provided with the weight parameter α, 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 i are not known and we would have to use LD-ME algorithms with w low as weight estimates for each group. This leads to 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 i , by design it would treat inlier points from other components also as outliers, unnecessarily inflating the fraction of outliers to 1 -w i instead of ε.Contributions In this paper, we 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 a 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 to 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 w j ⩽ ε and the inlier components are well-separated, i.e., ∥µ i -µ j ∥ ≳1 log 1 w low , where µ i '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 1 w low ) for a list size of O( 1 : For a mixture of Gaussian components N(µi, I d ), we show upper and lower bounds for the error of the i-component given a output list L (of the respective algorithm) min μ∈L ∥μ -µi∥. When the error doesn't depend on i, all means have the same error 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 k + O( ε w low ). Remarkably, we obtain the same error guarantees as if an oracle would run LD-ME on each inlier group with the correct weight w i separately (with outliers). Hence, the only cost for recovering small groups is the increased list-size overhead of order O( ε w low ). Further, a sub-routine in our meta-algorithm 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-theoretic (IT) lower bounds for LD-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 to the only prior method with guarantees, while being comparable or better than popular clustering methods such as k-means and DBSCAN for various attack models. 
settings: 
 We now introduce the learning settings that appear in the paper. Let d ∈ N + be the ambient dimension of the data and k ∈ N + be the number of mixture components (inlier groups/clusters).We focus on mixtures that consist of distributions that are sufficiently bounded in the following sense. Definition 2.1. Let t ∈ N + be even and let D(µ) be a distribution on R d with mean µ. We say that D(µ) has sub-Gaussian t-th central moments if for all even s ⩽ t and for every v ∈ R d with ∥v∥ = 1, E x∼D ⟨x -µ, v⟩ s ⩽ (s -1)!!.This class of distributions is closely related to commonly studied distributions in the literature (see, e.g., [5] ) with bounded t-th moment. Our requirement for the boundedness of all moments s ⩽ t stems from the fact that our algorithm should adapt to unknown and possibly non-uniform mixture weights.We assume that we are given samples from a corrupted d-dimensional mixture of k inlier distributions D i (µ i ) satisfying Definition 2.1, where the mixture is defined asEQUATIONandk i=1 w i + ε = 1, where for all i = 1, . . . , k, it holds that w i ⩾ w low . Further, an ε > 0 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 i (µ i ) constitute the i th inlier cluster. The goal in mixture learning under corruptions as in Eq. (2.1), is to design an algorithm that takes in i.i.d. samples from X and outputs a list L, such that for each i ∈ [k], there exists μ ∈ L with small estimation error ∥µ i -μ∥.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 ε ⩾ min i w i and the goal is to achieve small estimation errors while the list size |L| 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 i of the mixture and the fraction of outliers ε are unknown. Instead, by definition in Eq. (2.1), we assume knowledge of a valid lower bound w low ⩽ min i w i .Note that when ε ≲ min i w i , the problem is known as robust mixture learning and can be solved with list size |L| = k as discussed in [3, 4, 7] . However, algorithms for robust mixture learning fail when the fraction of outliers becomes comparable to the inlier group size. In the presence of "spurious" adversarial clusters, it is information-theoretically impossible to output a list L, such that (i) |L| = k and (ii) L contains precise estimate for each true mean.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 k = 1, the fraction of inliers α = w 1 and the fraction of outliers ε = 1 -α.The mean estimation algorithms we use to solve LD-ML with w low need to exhibit guarantees under a stronger adversarial model, where the adversary can also replace a small fraction (depending on w low ) of the inlier points; see details in Definition B.1. 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 α we use black-box learners that solve corresponding regime when provided with α.Robust mean estimation When the majority of points are inliers, we are in the RME setting. Robust statistics has studied this setting with different corruption models and efficient algorithms are known to achieve information-theoretically 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 a single estimate. We refer to this setting as cor-kLD (corrupted known list-decoding). For mixture learning, α is usually unknown and we need to solve the cor-aLD (corrupted agnostic list-decoding) problem (i.e., α is not provided, but instead a lower bound α low ∈ [w low , α] is given to the algorithm). Finally, when only additive adversarial contamination is present, as in Eq. (2.1), we recover the standard list-decoding setting studied in prior works (see Section 5) that we call sLD (simple list-decoding). In Appendix G we show that two algorithms designed for sLD also exhibit guarantees for cor-kLD for any w low .i ∈ [k], if w i ⩾ 1 -ε RME , then there exists μ ∈ L such that ∥μ -µ i ∥ ⩽ O(g(w i -w 2 low )).Proof. Proof follows by applying Theorem B.2 to X with α low = w low and treating each component as a corresponding inlier distribution with α = w i . This gives error upper bound for all inlier components, furthermore, since α low = w low , list size can be bounded as|L| ⩽ 1 + O((1 - α)/α low ) = O(1/w low ).In the outer stage, presented in Algorithm 6, we make use 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 ease of notation, when it's clear from the context, we drop the indices and refer to elements µ j ∈ M for some j ∈ [|M |] as µ and their corresponding sets S(1)EQUATIONj , as defined in lines 6-7 in Algorithm 6, as S (1) , S (2) . Further, for i ∈ [k], let C * i denote the set of points corresponding to the i-th inlier component, also called the i-th inlier cluster. 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.1. Run OuterStage (Algorithm 6) on S and consider the first iteration of the while-loop and for each µ ∈ M , denote the corresponding sets as S (1) , S (2) . Then, with probability at least 1 -w for all i ∈ R do 6:EQUATIONEQUATIONj ′ ∩C * i ′ | ⩾ w 4 low |C * i ′ |, then S (2) j ∩ S (2) j ′ = ∅.S (1) i ← j∈[|M |],j̸ =i x ∈ S, s.t. |v ⊤ ij (x -µ i )| ⩽ γ + γ ′ 7: S (2) i ← j∈[|M |],j̸ =i x ∈ S, s.t. |v ⊤ ij (x -µ i )| ⩽ 3γ + 3γ ′ 8:remove all i ∈ R for which |S(1)EQUATIONi | thenEQUATIONi | for which |Si | is largest 12:EQUATIONS ← S \ S j 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 T, a collection of sets that is the output of Algorithm 6, we defineG := i ∈ [k], such that there exists T = S (2) j ∈ T with S (1) j ∩ C * i ⩾ w 4 low |C * i | , for some j . (B.1)In words, it is 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 indexi ∈ G, several j ∈ [|M |] satisfy S (2) j ∈ T and S (1) j ∩ C * i ⩾ w 4 low |C * i |. We define g i ∈ [|M |] to denote the index of the first such set S (2)gi added to T.EQUATIONgi to be the set of inlier points from the i-th component, which were not removed from S at the iteration corresponding to g i . Let U := ∪ i∈G U i denote the union of such 'left-over' inlier points. Theorem B.7 (Outer stage guarantees, during execution). Let S consist of n i.i.d. samples from X as in the statement of Theorem C.1. Run OuterStage (Algorithm 6) on S and consider the moment when the sets S(2) i are added to T. We have that, with probability at least 1 -wO(1)low , all of the following are true:EQUATION⩽ O(w 2 low )n, or at least half of the samples in S(1) j are either adversarial samples or lie in U , (iv) if when the else statement is triggered, |S| ⩾ 0.1w low n, then at least a 0.4-fraction of the samples in S are adversarial, or equivalently, |S| ⩽ 2.5εn.Note that the else statement of OuterStage can only be triggered once, at the end of the execution. In words, Theorem B.7 (i) states that, for i ∈ G, samples from i-th cluster that remained in S after S(1) gi was removed, constitute a small (comparable with ε) fraction. Further, (ii) states that the sets added to T, corresponding to i ∈ G, almost entirely contain C * i . Finally, (iii) describes the sets that do not correspond to any g i , i ∈ 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.In this section, we state and prove a refined version of our main result, Theorem C.1, from which the statement of Theorem 3.3 directly follows.We defineψ t (α) = √ t(1/α) 1/t if t ⩽ 2 log 1/α, 2e log 1/α else, (C.1)which captures a tail decay of a distribution with sub-Gaussian t-th central moments:P x∼D ⟨x -µ, v⟩ t ⩾ ψ t (α) ≲ α.We now state our main result for list-decodable mixture learning. Recall that ε RME is defined in Assumption 3.1.Theorem C.1 (Main mixture model result). Let d, k ∈ N + , w low ∈ (0, 10 -4 ], and t be an even integer. For all i = 1, . . . , k, let D i (µ i ) be a d-dimensional distribution with mean µ i ∈ R d and sub-Gaussian t-th central moments. Let ε > 0 and, for all i = 1, . . . , k, letw i ∈ [w low , 1], such that k i=1 w i + ε = 1. Let X be the d-dimensional mixture distribution X = k i=1 w i D i (µ i ) + εQ,where Q is an unknown adversarial distribution that can depend on all the other parameters. Let A kLD and A R satisfy Assumption 3.1. Further, suppose that ∥µi -µ j ∥ ⩾ 200ψ t (w 4 low )+200f (w low ) for all i ̸ = j ∈ [k].Then there exists an algorithm (Algorithm 2) that, given poly(d, 1/w low ) • (N LD (w low ) + N R (w low )) i.i.d. samples from X, and given also d, k, w low , and t, runs in time poly(d, 1/w low ) • (T LD (w low ) + T R (w low )) and with probability at least1 -w O(1) low outputs a list L of size |L| ⩽ k + O(ε/w low ) such that, for each i ∈ [k], there exists μ ∈ L such that: ∥μ -µ i ∥ ⩽ O(ψ t ( wi /10) + f ( wi /10)),where wi = w i /(w i + ε + w 2 low ). If the relative weight of the i-th inlier cluster is large, i.e., wi ⩾ 1 -ε RME + 2w 2 low , then there exists μ ∈ L such that ∥μ -µ i ∥ ⩽ O(g( wi -3w 2 low )). Further, we assume w low ∈ (0, 1/10000], since this simplifies some of the proofs. We note that in a mixture with k components we necessarily have w low ⩽ 1/k. Furthermore, when w low ∈ (1/10000, 1/2], then we obtain the same result by replacing w low with w low /5000 throughout the statements and the proof. This would only affect both list size and error guarantees by at most a multiplicative constant, which is absorbed in the Big-O notation.Proof of Theorem 3.3. Proof follows directly from Theorem C.1, by noticing that Assumption 3.2 allows to replace f ( wi /10) by Cf ( wi ) and g( wi -3w 2 low ) by Cg( wi ) for some constant C > 0 large enough.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.1. 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 2 for each i ∈ [k] contains an estimate μ ∈ L, such that,(1) ∥μ -µ i ∥ ⩽ O(ψ t ( wi /10) + f ( wi /10)), (2) if wi ⩾ 1 -ε RME + 2w 2 low , then ∥μ -µ i ∥ ⩽ O(g( wi -3w 2 low )).We start by showing that list-decoding error guarantees as 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 of (1) We now show how the output of the base learner and filtering procedure lead to the error in (1) . Fix i ∈ [k]. Recall that C i denotes the set of w i n points from i-th inlier component with mean µ i .If i ∈ G, then on event E, we have S(2)EQUATIONgi ∩ C * j ⩽ w 4 low n by Theorem B.6 (iv), and that the total number of adversarial points is at most (ε + w 4 low )n.Therefore, the fraction of points fromEQUATIONgi is at least Based on this fact we can then use Theorem B.7 (iv) and the assumption on the range of w low to conclude that |S| ⩽ 2.5εn and that the fraction of inliers is at least (1 -w 2 low )w i /(2.5ε). Therefore, S can be seen as containing samples from the corruption model cor-aLD with α at least w i /(2.5ε) ⩾ w i /(2.5(w i + ε)). 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 i with large weight, i.e., such that w i /(w i + ε) ⩾ 1 -ε RME , there exists a set T ∈ T that consists of samples from the corruption model cor-aLD with α ⩾ w i /(w i + ε) -2w 2 low . Then, running InnerStage, in particular the RME base learner, results in the error bound as in (2) by Theorem B.2 (ii). If i ∈ G, in the previous paragraph we showed that there exists T ∈ T, such that the corresponding α ⩾ wi wi+ε+w 3 low ⩾ wi wi+ε -2w 2 low . We now prove by contradiction that the case i / ∈ G does not occur. Now assume i / ∈ G so that as we argued before when the else statement is triggered, S contains at least (1 -O(w w i /(w i + ε) ⩾ 1 -ε RME unless ε RME ⩾ 1/2 -2w 2low , which is prohibited by the assumptions in Theorem C.1. Therefore whenever w i /(w i + ε) ⩾ 1 -ε RME we are in the case i ∈ G.(ii) Proof of small list size We now prove that on the set E, we have that |L| ⩽ k + O(ε/w low ). Here, we need to carefully analyze iterations in the while loop where an inlier component is "selected" for the first time in order to obtain a tight list size bound. Recall that g i corresponds to the index in R that is first selected for the i-th inlier cluster.For any i ∈ [k], if i ∈ G, then Theorem B.7 (ii) implies that running InnerStage on S (2)gi produces a list of size at most 1 + O((|S(2) gi \ C * i |)/(w low n)).Then, over all i ∈ G, these sets S Samples left over from a 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 ε = 3ε + O(w 2 low ). For the same reason as above, without loss of generality, we can consider ε > w 2 low since otherwise, the corresponding list size overhead (for small enough w 2 low ) would again amount to zero.Clusters of adversarial samples: For iterations where a set S(2) j was added to the final list, which does not correspond to some g i , i ∈ G, Theorem B.7 (iii), states that either (i) at least half of the samples in S(2) j were adversarial, or (ii) the cardinality of the set on which Algorithm 3 was executed is small. In both cases the set S ∥μ -µ * ∥ ⩽ O(ψ t (α/4) + f (α/4)), 2. if α ⩾ 1 -ε RME , then there exists μ ∈ L such that ∥μ -µ * ∥ ⩽ O(g(α -w 2 low )).By Lemma D.1 we have |M | ⩽ 1/w O(1)low and, with probability at least 1 -wO(1)low , there exists (μ, α) ∈ M such that α ⩾ α/4 and ∥μ -µ * ∥ ⩽ f (α). Then Lemma D.2 implies that, with probability at least1 -|M | 2 w O(1)low , (μ, α) will not be removed from M . Therefore, either (μ, α) ∈ L, or there exists (μ, α) ∈ L such that (i) α ⩾ α and (ii) ∥μ -μ∥ ⩽ 4β(α). The latter case implies that ∥μ -µ * ∥ ⩽ 40ψ t (α/4) + 4f (α/4).For the second part, set first μ = μ. Then, in the i th iteration, μ moves away by at most (3τ /2)/2 i-1 . Since ∞ i=1 1/2 i ⩽ 1, the distance between μ and μ is always bounded by 3τ . Now, assume that indeed α ⩾ 1 -ε RME and ∥μ -µ * ∥ ⩽ τ . Whenever α ⩽ α, with high probability A R produces some µ RME such that ∥µ RME -µ * ∥ ⩽ g(α) ⩽ β/2. Furthermore, as long as α ⩽ α, at the moment of the while statement check we have -µ * ∥ ⩽ β: in the first iteration this is by assumption, and in later iterations it follows because μ is the former µ RME . Therefore the while statement check passes as long as α ⩽ α.There exists the possibility that the algorithm returns or breaks even though α ⩽ α. If the algorithm returns early, then the error τ achieved by μ is already within a factor of two of the optimal. If the algorithm breaks, either α + w 2 low > 1, case in which μ already satisfies ∥μ -µ * ∥ ⩽ g(1 -w 2 low ), or else ∥μ -µ * ∥ 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 α > α and the while statement check continues to pass. The first time we reach some α > α, we must have ∥μ -µ * ∥ ⩽ β ⩽ 2g(α -w 2 low ). Then, in later iterations, μ can move from this estimate by a distance of most 3 β ⩽ 6g(α -w 2 low ), by the same argument as the argument that ∥μ -μ∥ ⩽ 3τ . Overall, at the end we have∥μ -μ∥ ⩽ max(2g(1), g(1 -w 2 low ), 8g(α)) ⩽ 8g(α -w 2 low). The number of runs is at most 1/w 2 low , so with probability 1 -wO(1)low all runs of A R succeed. We showed that there exists (μ, α) ∈ L such that α ⩾ α/4 and ∥μ -µ * ∥ ⩽ 40ψ t (α) + 4f (α). This error can increase by running ImproveWithRME with τ = 40ψ t (α) + 4f (α) to at most ∥μ -µ * ∥ ⩽ 160ψ t (α) + 16f (α) = O(ψ t (α) + f (α)).Furthermore, if α ⩾ 1 -τ min , this (μ, α) ∈ L satisfies the conditions of ImproveWithRME, so with high probability the error is reduced by running ImproveWithRME with τ = 40ψ t (α) + 4f (α) to ∥μ -µ * ∥ ⩽ 8g(α -w 2 low ).(ii) Proof of list size We now prove that|L| ⩽ 1 + O((1 -α)/α low ).First, assume that α ⩽ 9/10. Since all αs ⩾ α low , we have that |L| ⩽ 10/(9α low ) ⩽ 12(1-α)/α low .For the rest of the proof we assume that α > 9/10. We analyze sets J and T i for i ∈ J at the end of execution of ListFilter. In particular, recall that L = {(μ i , αi ), i ∈ J}. Also, at the end of Algorithm 4 we have the following expression for T i :T i = j∈J\{i} {x ∈ S, s.t. |v ⊤ ij (x -μi )| ⩽ max(β(α i ), β(α j ))},where v ij are unit vectors in direction μi -μj . Select the s ∈ J for which αs is maximized. By (i), with probability at least 1 -w 60 low , there exists a hypothesis in J with α ⩾ α/4 ⩾ 0.2. Then we have that αs ⩾ 0.2. In addition, for all hypotheses, αs ⩽ 1/3. Let j ∈ J be such that j ̸ = s. We will show that at least half of the points in T j are adversarial, i.e., |T j | ⩾ 2 |T j ∩ C * |. If this is indeed the case, we can treat all inlier points in all T j as outliers, as it would at most double total number of outlier points in S.j ̸ = s, |T j | < 2 |T j ∩ C * |. Note that, because |T s | ⩾ 0.9 • 0.2n = 0.18n and |C * | ⩾ 0.9n, |T s ∩ C * | ⩾ 0.18n -0.1n ⩾ 0.08n. Therefore x ∈ C * , s.t. |v ⊤ sj (x -μs )| ⩽ β(α s ) ⩾ 0.08 |C * | .Also note that Lemma H.2 for radius 10ψ t (1/2) ⩽ 10ψ t ( αs ) implies that, with exponentially small failure probability,x ∈ C * , s.t. |v ⊤ sj (x -µ * )| ⩽ β(α s ) ⩾ 0.99 |C * | . Since these two sets necessarily intersect, we can bound |v ⊤ sj (μ s -µ * )| ⩽ 2β(α s ), implying that |v ⊤ sj (μ j -µ * )| ⩾ 2β(α j ), since ∥μ s -μj ∥ ⩾ 4β( αj ). Thus, if |v ⊤ sj (x -μj )| ⩽ β(α j ), then |v ⊤ sj (x -µ * )| > β( αj ), implying that (T j ∩ C * ) ⊆ x ∈ C * , s.t. |v ⊤ sj (x -µ * )| > β(α j ) .(D.1) However, Lemma H.2 tells us that with high probability only a small fraction of points in C * satisfies |v ⊤ sj (x -µ * )| > β( αj ). In particular, applying the lemma with radius 10ψ t (α j ), we get that with exponentially small failure probability, x ∈ C * , s.t. |v ⊤ sj (x -µ * )| ⩽ β(α j ) ⩾ 1 - αj 50 |C * | . (D.9α j |C * | /10 ⩽ |T j | ⩽ 2 |T j ∩ C * | ⩽ αj |C * | /25,which is a contradiction.Therefore, for all j ∈ J such that j ̸ = s, we have that|T j | ⩾ 2 |T j ∩ C * |.As we said in the beginning, by treating all inlier points in those T j as outliers we at most double total number of outlier points.Since there are at most (1 -α + αw = |J| ⩽ 1 + 3(1 -α)/α low .Note that in InnerStage we set α low = min(α low , 1/100). Therefore, for the original α low , the list size is bounded by 1 + 240(1 -α)/α low .Combining the probabilities of success of all steps, we get that the algorithm succeeds with probability at least 1 -wO(1)low for some large constant in the exponent. Our algorithm, ignoring the calls to A kLD and A R , has sample complexity and time complexity bounded by poly(d, 1/w low ), which gives the desired sample and time complexity when taking A kLD and A R into consideration. This completes the proof of the theorem. Proof. Let ℓ be an arbitrary iteration of the outer for loop. Then, at the beginning of the ℓ th iteration, 1. T j ∩ T s = ∅ for any j < s ∈ J, 2. |T j | ⩾ 0.9α j n for any j ∈ J, 
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 information-theoretic 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 a two-stage process. The outer stage (Algorithm 6) reduces the problem to mean estimation by leveraging the mixture structure and splitting the data into a small collection T of sets T . Each set T ∈ 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 at most O(εn). We then run the inner stage (Algorithm 3) on sets T , which outputs a mean estimate for the inlier cluster in T . First, a cor-aLD algorithm identifies the weight of the inlier cluster and returns the result of a 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. 1) that with probability at least 1/2 contains some μ with ∥μ -µ * ∥ ⩽ f (α), where f is non-increasing. (b) for α ∈ [1 -ε RME , 1], with 0 ⩽ ε RME ⩽ 1/2 -2w 2low in the RME regime, there exists an RME algorithm A R that uses N R (α) samples and T R (α) time to output with probability at least 1/2 some μ with ∥μ -µ * ∥ ⩽ g(α), where g is non-increasing. Note that the sample and time-complexity functions such as N LD and T LD , might depend on t, for example growing as d t . We emphasize that (i) the guarantees of our meta-algorithm depend on the guarantees of the base learners and (ii) we only require the base learners to work in the wellstudied setting with known fraction of inliers. Corollary 3.4 uses known base learners for Gaussian distributions achieving information-theoretically optimal error bounds. There also exists base learners for distributions beyond Gaussians, such as bounded covariance or log-concave distributions, see, e.g. [9] .Key quantities that appear in our error bounds are the relative proportion of inliers wi and outliers εi :EQUATIONThese quantities reflect that each set T in the inner stage contains at most one inlier cluster and a small (≲ w 2 low ) fraction of points from other inlier clusters. We now present a simplified version of our main result in Theorem 3.3 (see Theorem C.1 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 as defined in Assumption 3.1. For some C > 0, we assume (i)ε RME ⩾ 0.01, (ii) ∀x ∈ (0, 1/3], f (x/2) ⩽ Cf (x), and (iii) ∀x ∈ [0.99, 1], g(x -(1 -x) 2 ) ⩽ Cg(x).We are now ready to state the main result of the paper. Theorem 3.3. Let d, k ∈ N + , w low ∈ (0, 1/2], and t be an even integer. Let X be a d-dimensional mixture distribution following Eq. (2.1). Let A kLD and A R satisfy Assumptions 3.1 and 3.2 for some even t. Further, suppose that ∥µ i -µ j ∥ ≳ √ t(1/w low ) 4/t + f (w low ) for all i ̸ = j ∈ [k].Then there exists an algorithm that, given poly(d, 1/w low ) • (N LD (w low ) + N R (w low )) i.i.d. samples from X as well as d, k, w low , and t, runs in timepoly(d, 1/w low ) • (T LD (w low ) + T R (w low ))and with probability at least 1 -wO(1) low outputs a list L of size |L| ⩽ k + O(ε/w low ) where, for each i ∈ [k], there exists μ ∈ L such that ∥μ -µ i ∥ = O min 1⩽t ′ ⩽t √ t ′ (1/ wi ) 1/t ′ + f (min( wi , 1/3)) .If the relative weight of the i-th cluster is large, i.e., εi ⩽ 0.001, then the error is further bounded by∥μ -µ i ∥ = O (g( wi )) .The proof together with a more general statement, Theorem C.1, can be found in Appendix C.Note that for a mixture setting with k ⩾ 2, the assumption w low ⩽ 1/k ⩽ 1/2 is automatically fulfilled. Also, for large weights wi such that log(1/ wi ) ≪ t, the t ′ that minimizes √ t ′ (1/ wi ) 1/t ′ is smaller than t, and for small weights the minimizer is t ′ = t.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, k, w low and t be as in Theorem 3.3. Let X be as in Eq. (2.1) with D i (µ i ) = N(µ i , I d ) with µ i 's satisfying ∥µ i -µ j ∥ ≳ log 1/w low for all i ̸ = j ∈ [k]. There exists an algorithm that for t = O(log 1/w low ), given N = poly(d t , (1/w low ) t ) i.i.d. samples from X and w low , runs in poly(N ) time and outputs a list L such that with high probability |L| = k + O(ε/w low ) and, for all i ∈ [k], there exists μ ∈ L such that ∥μ -µ i ∥ = O log 1/ wi .If the relative weight of the i-th cluster is large, i.e. εi ⩽ 0.001, then the error is further bounded by∥μ -µ i ∥ = O εi log 1/ε i .Proof. Theorem 6.12 from [5] provides an LD-ME algorithm A kLD achieving errorf (α) ⩽ O( √ t ′ (1/α) 1/t ′ ) for all t ′ ⩽ t.The sample and time complexity scale as poly(d t , (1/α) t ). Also, Theorem 5.1 from [10] provides a robust mean estimation algorithm A R such that for a small enough constant fraction of outliers ε = 1 -α it achieves error g(α) = O((1 -α) log 1/(1 -α)) with sample complexity Ω(d/ε 2 ). Using these A kLD and A R , we recover the desired bounds.We now compare our result with the only previous method that can achieve guarantees in the LD-ML setting with unknown w i . As discussed in [3] , algorithms for the simple list-decoding model with α = w low can be used for LD-ML by viewing a 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(1/w low ) ≫ k + O(ε/w low ) and error O( log 1/w low ), this approach has two drawbacks that manifest in the suboptimal guarantees: 1) For larger clusters i with w i ≫ w low , LD-ME only achieves an error O log 1/w low .Our result, even without separation assumption, achieves a sharper error bound O log 1/w i . 2) When the mixture is separated, LD-ME cannot exploit the structure since it still models the data as w low N(µ i , I d ) + (1 -w low )Q for each i, so that the algorithm inevitably treats all other true components as outliers. This results in the error O log 1/w low ≫ O log 1/ wi = O(1) (when ε ∼ w i ≪ 1). We refer to Appendix A for further illustrative examples. As a simple example, consider the uniform inlier mixture with ε = w i = 1/(k + 1), where k is large. In this case, previous results have error guarantees O( √ log k), while we obtain error O(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 ∥µ i -µ j ∥ ≳ √ t(1/w low ) 4/t , which we believe to be sub-optimal for the case of finite t. In cases when ε is small (namely ε ≲ w low ), there exist prior works on clustering allowing smaller separation. Specifically, when t = 2, a recent work [13] only requires ∥µ i -µ j ∥ ≳ 1/ √ w low . For a general t ⩾ 4, [9] succeeds under separation(1/w low ) 2/t . We leave the possible relaxation of the separation requirement in the case of general t and large ε for the future work.In the Gaussian case we require separation ∥µ i -µ j ∥ ≳ log 1/w low , which is optimal in the uniform (w i = 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 Ω( log 1/w i ). In Corollary B.5, we prove that the inner stage (Algorithm 3) of our algorithm, without knowledge of w i and separation assumption, achieves with high probability matching error guarantees O( log 1/w i ) with list size bounded by O(1/w low ).Next, we present information-theoretical lower bounds for list-decodable mixture learning on wellseparated 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). EQUATIONEQUATIONif for all μ, |SEQUATIONμ | then add X to T and update L ← ∅ 6:EQUATIONEQUATIONadd Sμ to T 9:X ← X \ S(1) μ10: return T Proposition 3.5 (Information-theoretic lower bounds). Let A be an algorithm that, given access to X, outputs a list L that, with probability ⩾ 1/2, for each i∈ [k] contains μ ∈ L with ∥μ -µ i ∥ ⩽ β i .(a) Consider the case with ∥µ i -µ j ∥ ≳ (1/w low ) 4/t for i ̸ = j ∈ [k], D i (µ i ) having t-th bounded sub-Gaussian central moments andβ i ⩽ C(1/w low ) 1/t for each i ∈ [k]. If for some s ∈ [k] it holds that w s ⩽ ε, then algorithm A must either have error bound β s = Ω((1/ wi ) 1/t ) or |L| ⩾ k + d -1. (b) Consider the case with ∥µ i -µ j ∥ ≳ log 1/w low for i ̸ = j ∈ [k], D i (µ i ) = N(µ i , I d ) and β i ⩽ C log 1/w low for each i ∈ [k]. If for some s ∈ [k] it holds that w s ⩽ ε, then algorithm A must either have error bound β s = Ω( log 1/ wi ) or |L| ⩾ k + min{2 Ω(d) , (1/ wi ) ω(1) }.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 sub-Gaussian moments, [3] obtains information-theoretically (nearly-)optimal 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 Ω t ((1/ ws ) 1/t ) requires running time at least d Ω(t) . This was proved for Gaussian inliers and the running time matches ours up to a constant in the exponent.Indeed, the second property follows directly from the algorithm.For the first property, assume that for j < s ∈ J, there exists x ∈ S, such that x ∈ T j ∩ T s . This would imply that |v ⊤ js (μ j -μs )| ⩽ 2β(α s ), so ∥μ j -μs ∥ ⩽ 2β(α s ). However, in this case the first 'if' condition would pass and we would not add s to J. Thus, T j ∩ T s = ∅.For the third property, note that n ⩾ j∈J |T j | ⩾ j∈J 0.9 αj n ⩾ 0.9 |J| αℓ n, which implies |J| ⩽ 10/(9α ℓ ). Now, let s be the index of a hypothesis with αs ⩾ α/4 and s -µ * ∥ ⩽ f ( αs ). If s was skipped in the s th iteration (i.e., there exists j ∈ J with μj close to μs ), then (μ s , αs ) is trivially not removed from M . For the rest of the proof we assume that s is not skipped.For the sake of the analysis, we introduce the analogue of the sets T s , which we call Ts , defined for points in the set C * (i.e., all inlier points before the adversarial removal), and show that (i) Ts is large and (ii) Ts \ T s is small. In particular, letTs = j∈J x ∈ C * , s.t. |v ⊤ js (x -μs )| ⩽ β(α s ) ,where we recallβ(α s ) = 10ψ t (α s ) + f (α s ). Note that |T s | ⩾ Ts -|C * \ S * | ⩾ Ts -w 2 low |C * |.Also, for any α ′ ⩽ αs , applying Lemma H.2 with radius 10ψ t (α ′ ), using that ∥μ s -µ * ∥ ⩽ f (α s ) ⩽ f (α ′ ) and t ⩾ 2, we get that with exponentially small failure probability,x ∈ C * , s.t. |v ⊤ (x -μs )| > β(α ′ ) ⩽ α ′ 50 |C * | . (D.3)Consider the s th iteration. Using a union bound over |J| ⩽ 2/α low directions, and since all αs ⩾ α low , we get that with exponentially small failure probabilityTs ⩾ |C * | - i∈J x ∈ C * , s.t. |v ⊤ is (x -µ s )| > β(α s ) ⩾ 1 - αs 50 |J| |C * | ⩾ 0.95 |C * | ,where we used that and |J| ⩽ 10/(9 αs ). This implies that|T s | ⩾ Ts -w 2 low |C * | ⩾ (0.95 -w 2 low ) |C * | ⩾ 0.92 |C * | ⩾ 0.9αn ⩾ 0.9α s n,i.e., (μ s , αs ) is not removed from M during s th iteration.The pair (μ s , αs ) could also be removed during later iterations, when we recalculate T s by removing points along new directions. However, following a similar argument, we show that still, with high probability, |T s | ⩾ 0.9 αs n. Assume that we are now in the k th iteration of the outer cycle, where k > s. We define again Ts and sets A, B:Ts := i∈J\{s} x ∈ C * , s.t. |v ⊤ is (x -μs )| ⩽ max(β(α s ), β(α i )) , A := i<s,i∈J A i , for A i := x ∈ C * , s.t. |v ⊤ is (x -μs )| ⩽ β( αs ) , B := i>s,i∈J B i , for B i := x ∈ C * , s.t. |v ⊤ is (x -μs )| ⩽ β( αi ) , so that Ts = A ∩ B and again |T s | ⩾ Ts -w 2 low |C * |.It is crucial that we have different right hand sides in the definitions of A i and B i (we wrote them in boldface to emphasize this).Ts ⩾ |C * | - i<s,i∈J |C * \ A i | - i>s,i∈J |C * \ B i | .Using eq. (D.3), with exponentially small failure probability, for all i ∈ J,|C * \ A i | ⩽ ( αs /50) |C * | (for i < s) and |C * \ B i | ⩽ (α i /50) |C * | (for i > s).Next, note that before the last element was added, we had that (i) T i T j = ∅ for any i ̸ = j ∈ J and (ii) |T i | ⩾ 0.9α i n for any i ∈ J. This implies that i∈J αi < 10/9 + αlast < 19/9, where αlast corresponds to the element which was added last (it might happen that after addition of the last element, we have |T i | < 0.9α i n for several i ∈ J). Therefore, as before, we obtain thatTs ⩾   1 - i<s,i∈J ( αs /50) - i>s,i∈J (α i /50)   |C * | ⩾ (1-10/(9•50)-19/(9•50)) |C * | ⩾ 0.93 |C * | , therefore |T s | ⩾ Ts -w low |C * | ⩾ 0.92 |C * | ⩾ 0.9α s n and (μ s , αs ) 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 |M |. 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 | 2 w O(1)low .E Proof of outer stage algorithm guarantees in Appendix B.3Recall that γ = 4ψ t (w 4 low ) and γ ′ = 160ψ t (w low /4) + 16f (w low /4).In what follows we condition on the event E that the events under which the conclusions in Lemmas H. Proof of Theorem B.6 (i) The list size bound follows from the standard results on A sLD (see [3] , Proposition B.1).Proof of Theorem B.6 (ii) Guarantees of A sLD imply that there existsµ i ∈ M such that ∥µ i - µ * ∥ ⩽ γ ′ . By Lemma H.3, a (1 -w 2 low /2)-fraction of the samples in C * are γ-close to µ * along each direction v ij with i ̸ = j ∈ [|M |]. Then, the same (1 -w 2 low /2)-fraction of samples are (γ + γ ′ )-close to µ i along each direction v ij , so they are included in S (1) i . Proof of Theorem B.6 (iii) Suppose |S (1) i ∩ C * | ⩾ w 4 low |C * |.Previous point implies that there exists µ j ∈ M be such that ∥µ j -µ * ∥ ⩽ γ ′ . Then at least an w 4 low -fraction of the samples in C * are (γ + γ ′ )-close to µ i in direction µ i -µ j . By Lemma H.2, µ * is also γ-close in direction µ i -µ j to more than a (1 -w 4 low )-fraction of the samples in C * , so it is γ-close to at least one sample in any w 4 low -fraction of samples in C * . Therefore µ * is also (2γ + γ ′ )-close to µ i in direction µ i -µ j . Then ∥µ i -µ j ∥ ⩽ 2γ + 2γ ′ and ∥µ i -µ * ∥ ⩽ 2γ + 3γ ′ . Again, using Lemma H.3 we obtain that there exists a (1 -w 2 low /2)-fraction of the samples in C * , which is included in Si .Proof of Theorem B.6 (iv) Similarly, if |S∩ C * | ⩾ w 4 low |C * |, then there exists µ j ∈ M , such that at least an w 4 low -fraction of the samples in C * are (3γ + 3γ ′ )-close to µ i in direction µ i -µ j . By the same arguments as in previous paragraph, we obtain that ∥µ i -µ j ∥ ⩽ 4γ + 4γ ′ and ∥µ i -µ * ∥ ⩽ 4γ + 5γ ′ .Then any other true cluster with mean (µ * ) ′ and set of samples EQUATIONselects from all other true clusters at most w 4 low n samples.Proof of Theorem B.6 (v) Note that by the same argument,EQUATIONi ′ are disjoint by the condition that each selects only samples that are (3γ + 3γ ′ )-close along direction µ i -µ i ′ to the respective means µ i and µ i ′ .In the sequel, for any i ∈ G, let i be the index in R after initialization that satisfies Theorem B.6 (ii). We condition on the event E ′ that event E from the proof of Theorem B.6 holds and that both ||C * i |-w i n| ⩽ w 10 low n for all i ∈ [k] and the number of adversarial points lies in the range εn±w 10 low n. By Hoeffding's inequality and the union bound, the probability ofE ′ is at least 1 -w O(1) low .Proof of Theorem B.7 (i) Let i ∈ G, and consider the beginning of the iteration when µ gi is selected. Then, using that all previous iterations could have removed at most O(w 3 low )|C * i | samples from C * i , we have that|S (1) mi ∩ C * i | ⩾ (1 -w 2 low /2 -O(w 3 low ))|C * i |.Therefore at the iteration in which µ gi is selected, we still have m i ∈ R. We now discuss two cases: First, consider the case that |S(2)EQUATIONmi |. Then, because we selected µ gi ∈ M and notµ mi ∈ M it means that |S (1) gi | ⩾ |S (1) mi | ⩾ (1 -w 2 low /2 -O(w 3 low ))|C * i |.Note also by Theorem B.6 (iv), the number of samples from other true clusters in S gi is at least|S (2) gi | -|C * i | -w 4 low n ⩾ |S (2) gi \ S (1) gi | -O(w 2 low )|C * i | -w 4 low n ⩾ |S (2) gi \ S (1) gi | -O(w 2 low )|C * i |.Then, either Sgi \ S(1) gi= O(w 2 low )|C * i | and |U i | ⩽ S (2) gi \ S (1) gi = O(w 2 low )|C * i |, or S (2) gi \ S (1) gi ≫ w 2 low |C * i |.In the latter case, even if Sgi \ Sgi consists of adversarial examples only, then, since |SEQUATIONgi |, U i contains at most double the number of adversarial examples in S mi |, so the number W i of adversarial samples in S(2) miEQUATIONmi | ⩾ 0.98|SEQUATIONFinally note that by Theorem B.6 (v), the sets Sgi and Smi are disjoint from any other sets Sgj and S m i |⩽2|S (1) m i | V i + i∈G |S (2) m i |>2|S (1) m i | W i ⩽ (ε + w 10 low )n.Therefore, we directly obtain|U | ⩽ i∈G (C * i ∩ S (2) gi ) \ S (1) gi = i∈G |S (2) m i |⩽2|S (1) m i | (C * i ∩ S (2) gi ) \ S (1) gi + i∈G |S (2) m i |>2|S (1) m i | (C * i ∩ S (2) gi ) \ S (1) gi ⩽ i∈G |S (2) m i |⩽2|S (1) m i | 2V i + i∈G |S (2) m i |>2|S (1) m i | 2W i + O(w 2 low )n ⩽ (2ε + O(w 2 low ))n.Proof of Theorem B.7 (ii) Each iteration before g i was selected, removed at most w j | ⩽ w 2 low |C * i | + 2w 4 low n ⩽ O(w 2 low )n.Proof of Theorem B.7 (iv) Suppose that when the algorithm reaches the else statement we have for some Overall, the number of adversarial samples in S when the algorithm reaches the else statement is at leasti ∈ [k] that i ∈ R and |S (1) mi ∩ C * i | ⩾ 20w 2 low |C * i |. We have that |S (2) mi ∩ C * i | is at most |S (1) mi ∩ C * i | + w 2 low |C * i |/2,EQUATION0.44|V | + (|S| -|V | -21w 2 low n) = |S| -0.56|V | -21w 2 low n ⩾ 0.44|S| -21w 2 low n ⩾ 0.4|S| where in the last inequality we also used that |S| ⩾ 0.1w low n.We now prove lower bounds for the case of Gaussian distributions and distributions with t-th sub-Gaussian moments.We first focus on the case when D i (µ i ) = N(µ i , I). The proof goes through an efficient reduction from the problem considered by Proposition F.1 to the problem solved by algorithm A. Proposition F.1 ([5], Proposition 5.11). Let D be the class of identity covariance Gaussians on R d and let 0 < α ⩽ 1/2. Then any list-decoding algorithm that learns the mean of an element of D with failure probability at most 1/2, given access to (1 -α)-additively corrupted samples, must either have error bound β = Ω( log 1/α) or return min (2 Ω(d) , (1/α) w( 1) ) many hypotheses.In this we discuss two of the existing list-decodable mean estimation algorithms for identitycovariance Gaussian and show that they also work when a w 2 low -fraction 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 "α-good multiset", which is a multiset of samples such that all are within distance O( √ d) of each other and at least an α-fraction of them come from a (1 -Ω(α))-fraction of an i.i.d. set of samples from a Gaussian distribution N (µ, I d ). Then their algorithm essentially works as long as the input contains an α-good multiset. For our case, after the removal of a w 2 low -fraction of inliers, the input essentially continues to contain a (1 -w 2 low )α-good multiset, so the algorithm continues to 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 E x,y∼S * [p 2 (x -y)] ⩽ 2E g,h∼N (0,I d ) [p 2 (g -h)] for all degree-(t/2) polynomials p, where S * is the set of inliers. Concentration arguments give with high probability that E x,y∼C * [p (x -y)] ⩽ 1.5E g,h∼N (0,I d ) [p 2 (g -h)]. Furthermore, the distribution over x, y ∼ S * can be seen as a (1 -w 2 low ) 2 -fraction of the distribution over x, y ∼ C * . Then Fact G.1, which follows by standard probability calculations, also gives that any event under the former distribution can be bounded in terms of the second distribution: Fact G.1. For any event A,P x,y∼S * (A) ⩽ P x,y∼C * (A)/(1 -w 2 low ) 2 , (G.1)where probabilities are taken over a uniform sample from S * and C * respectively.Overall we obtainE x,y∼S * [p 2 (x -y)] ⩽ 1.5/(1 -w 2 low ) 2 E g,h∼N (0,I d ) [p 2 (g -h)], so for w low small enough we have E x,y∼S * [p 2 (x-y)] ⩽ 2E g,h∼N (0,I d ) [p 2 (g-h)] and their algorithm continues to work in our corruption model.In this section we prove some concentration bounds essential to our analysis. Lemma H.1. Let D be a d-dimensional distribution with mean µ * ∈ R d and sub-Gaussian t-th central moments with parameter 1. Fix a unit vector v ∈ R d . ThenP x∼D [|⟨x -µ * , v⟩| ⩽ R] ⩾ 1 - √ t R t .Proof. We have thatP x∼D [|⟨x -µ * , v⟩| > R] ⩽ E x∼D ⟨x -µ * , v⟩ t R t ⩽ (t -1)!! R t ⩽ √ t R t ,where we used that (t -1)!! ⩽ t P x∼D [|⟨x -µ * , v i ⟩| ⩽ R, ∀i ∈ [m]] ⩾ 1 -m √ t R t .Then the result follows by a Binomial tail bound.Adversarial line and adversarial clusters The following figure illustrates the adversarial distributions used in Figure 2 and further in this section. Data Distribution We consider a mixture of k = 7 well-separated (∥µ i -µ j ∥ ⩾ 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 w low = 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 are as depicted in Figure 4 .Fake ClusterWe consider three distinct adversarial models (see Figure 4 for reference).1. Adversarial clusters: After sampling the inlier cluster means, we choose the cluster with the smallest weight. Let µ s denote its mean. Then, we sample a random direction v c with ∥v c ∥ = 10. After that, we sample three directions v 1 , v 2 and v 3 with ∥v i ∥ = 10. Then we put three additional (outlier) clusters with means at µ s + v c + v i . This roughly corresponds to the right picture in Figure 4 . The samples for each adversarial cluster are drawn from a 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 µ s denote its mean. Then, we sample a random direction v c with ∥v c ∥ = 10. We put three additional (outlier) clusters with means at µ s + v c , µ s + 2v c and µ s + 3v c , which form a line as shown in Figure 4 . The samples are drawn similarly to the adversarial clusters, with the difference that the covariance is scaled by a factor of 5 in the direction of the line. 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 are generated from the same Gaussian distribution).Note that in the first and second attack, the adversary creates clusters that do not 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).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. In particular, we use 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 a 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.Hyper-parameter search and experiment execution The hyper-parameters of our algorithm are 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 β 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 a total of 7 parameters. The tuning for these was performed using a grid search comparing about 250 different configurations. Similarly, we independently tune the vanilla LD-ME algorithm, which we run with w low as weight parameter. For DBSCAN, we optimize the list size and error metrics by searching over a 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 w low . For k-means and its robust version, utilizing a median-of-means weighting scheme, we explore 21 values for k, including the true number of clusters. Each 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 of randomness: the data is random and also the algorithms themselves are random (except DBSCAN). For a clear comparison, we sample and fix 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 i∈[k] min μ∈L ∥µ i -μ∥. 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 7 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 error (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.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 heavy-tailed inlier distribution.To study the effect of varying w low 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 k = 3 wellseparated clusters: one small cluster with a weight of 0.045 and two large clusters, each with a weight of 0. We plot the median values with error bars indicating 25th and 75th quantiles. As w low 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 we run 100 seeds for each w low ranging from 0.02 to 0.2, which corresponds to 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 w low . Meanwhile, the estimation error of LD-ME increases as w low 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 to the ones obtained in the previous experimental settings.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 5 minutes for a single run of the experiment for one noise model with 10000 samples. We remark that classic approaches like k-means and DBSCAN perform fast and the most time-consuming part is the execution of the LD-ME base learner. Given our experimental setup with three noise models, it takes about 15 minutes to reproduce all our results for one data distribution.• 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 or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are 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. 
algorithm sketch: 
 We now sketch our meta-algorithm specialized to the case of separated Gaussian components N(µ i , I d ) 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/ wi ) for each mean when ε ≳ min i w i . We refer to Appendix D for how to achieve the refined error guarantee of O(ε i log 1/ε i ) when εi is small.As discussed in Section 3.1, running an out-of-the-box LD-ME algorithm for the sLD problem on our input with parameter α = w low would give sub-optimal guarantees. In contrast, our twostage Algorithm 2, equipped with the appropriate cor-kLD and RME base learners as 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.We now describe how to use a black-box cor-kLD algorithm to obtain a list-decoding algorithm A aLD for the cor-aLD mean-estimation setting with access only to α low ⩽ α. A aLD is used in the proof of Corollary B.5 and plays a 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 α from the input samples is impossible by nature. Indeed, we cannot distinguish between potential outlier clusters of arbitrary proportion ⩽ 1-α and the inlier component.Underestimating the size of a large component would inevitably lead to a suboptimal error guarantee. We now show how to overcome this challenge and achieve an error guarantee O( log 1/α) for a list size 1 + O((1 -α)/α low ) for the cor-aLD setting. Here we only outline our algorithm and refer to Appendix D for the details.Algorithm 3 first produces a large list of estimates corresponding to many potential values of α and then prunes it while maintaining a good estimate in the list. In particular, for each α ∈ A := {α low , 2α low , . . . , ⌊1/(3α low )⌋α low }, we run A kLD with parameter α to obtain a list of means. We append α to each mean in the list and obtain a list of pairs (μ, α). We concatenate these lists of pairs for all α and obtain a list L of size O(1/α 2 low ). By design, one element of A is close to the true α, so the list L contains at least one μ that is O( log 1/α)-close -the error guarantee that we aim forand there is indeed at least an α-fraction of samples near μ. We call such a hypothesis "nearby".Finally, we prune this concatenated list by verifying for each μ whether there is indeed an α-fraction of samples "not too far" from it. This is similar to pruning procedures with known α proposed in prior work (see Proposition B.1 in [3] ). Our procedure (i) never discards a "nearby" hypothesis, and outputs a list where (ii) every hypothesis contains a sufficient number of points close to it and (iii) all hypotheses are separated. Property (i) implies that the final error is O( log 1/α) and properties (ii) and (iii) imply list size bound 1 + O((1 -α)/α low ). Note that when α < α low , the list size can be simply upper bounded by O(1/α low ), see Remark B.4.Even though we could run A aLD on the entire dataset with α low = w low , we would only achieve an error for the i th inlier cluster mean of O( log 1/w i ) -which can be much larger than O( log 1/ wi ) -for a list of size O(1/w low ). While A aLD takes into account the unknown weight of the clusters, it still treats other inlier clusters as outliers. We now show that if the outer stage Algorithm 1 of our meta-algorithm Algorithm 2 separates the samples into a not-too-large collection T of sets with certain properties, running A aLD 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: We now informally describe the outer stage that produces the collection of sets T with the desiderata described in Section 4.2, leaving the details to Appendix E. The main steps are outlined in pseudocode in Algorithm 1.Given a set X of N = poly(d t , 1/w low ) 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 1 on X and w low with ∆ = O( log 1/w low ). Algorithm 1 runs an sLD algorithm on the samples and produces a (large) list of estimates L such that, for each mean, at least one estimate is O( log 1/w low )-close to it. It then add sets to T that correspond to these estimates via a dynamic "two-scale" process.Specifically, for each μ ∈ L, we construct two sets Sμ ⊆ Sμ consisting of samples close to μ. By construction, we guarantee that if S (1) μ contains a non-negligible fraction of samples from any inlier cluster C * , then S(2) μ 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, as long as there exists some μ with |S μ contains (almost) all of C * , so we add to T a set that contains (almost) all of C * ; otherwise, when we remove S(1) μ we remove (almost) no points from C * , so (almost) all the points from C * remain in play. For property (2), we merely note that whenever we add S μ |/2. The proof of the properties uses some additional arguments of a similar flavor, and we defer it to Appendix E. 
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 a popular approach for robustly learning the mean of a distribution when the majority of the samples are outliers. A 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] [23] [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 of 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 ε ≪ min i w i and aims to output exactly k vectors with an accurate estimate for the population mean of each component [3, 4, 7, 9, 11, 13, 29, 30] . These algorithms do not enjoy error guarantees for clusters with weights w i < ε. To the best of our knowledge, our algorithm is the first to achieve non-trivial guarantees in this larger noise regime. [31] also addresses the presence of small fractions of outliers in a 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. 
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 a plug-and-play meta-algorithm (cf. Figure 1 ) that inherits guarantees of the black-box cor-kLD algorithm A kLD and RME algorithm A R , which it uses as 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 unsupervised real-world data are hard to come by, we provide preliminary experiments on synthetic data. Specifically, we generate data from a separated k-Gaussian mixture with additive contaminations as in Eq. (2.1) and different types of adversarial distributions (see detailed description in Appendix I). We focus on the regime ε ∼ w i where our algorithms shows the largest theoretical improvements. The experimental setup is illustrated in Appendix I. We plot the median values with error bars showing 25th and 75th quantiles. As w low decreases, we observe a roughly constant estimation error for our algorithm while the error for LD-ME increases. Further, the decrease in list size is much more severe for LD-ME than for our algorithm.We then compare the output of our algorithm with the vanilla LD-ME algorithm from [8] with w low = 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 to also perform well in practice in noisy settings. In Figure 2 (left), we fix the list size to 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 a given list size and list sizes that algorithms require to achieve a given worst-case estimation error. In Figure 2 (right), we fix the error and plot the minimal list size at which competing algorithms reach the same or smaller worst estimation error. Further details on the experiments are provided in Appendix I. In a different experiment (see Figure 3 and Appendix I.1 for details), we observe that our approach outperforms LD-ME when w low 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 not allow conclusive statements about the improvement of our algorithm for mixture learning for real-world data, they do provide encouraging evidence that effort could be well-spent on follow-up empirical and theoretical work building on our results. For example, it would be interesting to conduct a 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 scaled covariances in an agnostic manner.[ k inlier cluster, c outlier clusters. One tricky adversarial distribution is the Gaussian mixture model itself. In particular, we considerX c = k k + c k i=1 1 k N(µ i , I) + c k + c c i=1 1 c N(μ i , I), (A.1)where the first k Gaussian components are inliers and Q is a GMM with c components, which we call fake clusters. Since all inlier cluster weights are identical, we denote w := w i = 1/(k + c). Assume that 1 ≪ c ≪ k, which corresponds to ε ≫ w. Then, relative weights are w = 1/(c + 1) ≈ 1/c. Due to large adversary, previous results on learning GMMs cannot be applied, leaving vanilla listdecodable learning. However, the latter also cannot guarantee anything better that Ω( √ tk 1/t ) even with the knowledge of k, as long as list size is O(k +c), which can be much worse than our guarantees of O( √ tc 1/t ) for the same list size.Their drawback is that they do not utilize separation between true clusters, i.e., for each i, they model the data asX = 1 k + c N(µ i , I) + 1 - 1 k + c Q.where Q can be "arbitratily adversarial" for recovering µ i .Big + small inlier clusters Consider the mixtureX b = (1 -w -ε) N(µ 1 , I d ) + wN(µ 2 , I d ) + εQ, (A.2)where ∥µ 1 -µ 2 ∥ = Ω( log 1/w), w ≪ ε ≪ 1, and Q is chosen adversarially. In this example we have two inlier clusters, one with large weight ≈ 1 and another with small weight w. Adversarial distribution Q has large weight relative to the small cluster, but still negligible weight compared to the large one.Previous methods would either (i) recover large cluster with optimal error O(ε) (see, e.g., [35] ) but miss out small cluster or (ii) recover both clusters using list-decodable mean estimation with known α = w, but with suboptimal errors O( log 1/w) and list size O(1/w). In contrast, Corollary 3.4 guarantees list size at most 1 + O(ε/w), error O( log ε/w) for the small cluster, and error O(ε log 1/ε) for the larger. In general, we achieve (i) optimal errors for both clusters and (ii) optimal (up to constants) list size.Our meta-algorithm Algorithm 2 assumes black-box access to a list-decodable mean estimation algorithm and a robust mean estimation algorithm for sub-Gaussian (up to the t th moment) distributions. From these we obtain stronger mean estimation algorithms when the fraction of outliers is 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 black-box learners achieve the guarantees for their corresponding mean estimation setting. In this section we discuss the corruption model and inner and out stage of the meta-algorithm in detail and prove properties needed for the proof of the main Theorem 3.3.In order to achieve these guarantees, our black-box algorithms need to work under a model in which an adversary is allowed to remove a small fraction of the inliers and to add arbitrarily many outliers. In our proofs, for simplicity of exposition, we require the algorithms to have mean estimation guarantees for a small adversarially removed fraction of w 2 low . Formally, the corruption model as defined as follows. Add the elements of the returned list to L. 6: return L. add the pair (μ, α) to M for each output μ 6: Let L be the output of ListFilter (Algorithm 4) run on S, α low , and M 7: for (μ, α) ∈ L do • An adversary is allowed to arbitrarily remove ⌊w 2 low n 1 ⌋ samples from C * . We refer to the resulting set as S * with size n 2 = |S * |.Input: Samples S = {x 1 , . . . , x n } , α low ∈ [w low , 1], A kLD ,• An adversary is allowed to add n -n 2 arbitrary points to S * . We refer to the resulting set as S adv with size n 3 = |S adv |.• If n 3 < n, pad S adv with n -n 3 arbitrary points and call the resulting set S.• Return S.We call cor-kLD the model when w low and α are given to the algorithm and cor-aLD the model when w low and lower bound α low ⩾ w low are given to the algorithm, such that α ⩾ α low . Note that α is not provided in cor-aLD model. if exists j ∈ J, such that ∥μ i -μj ∥ ⩽ 4β(α i ) then continue 6: add i to J 9:T i ← j∈J {x ∈ S, s.t. |v ⊤ ij (x -μi )| ⩽ β(α i )}. 7: if |T i | < 0.9α i n then remove (μ i , αi ) from M andfor j ∈ J \ {i} do 10:T j ← T j x ∈ S, s.t. |v ⊤ ij (x -μj )| ⩽ β(α i ) 11:if |T j | < 0.9α j n then:12:remove (μ j , αj ) from M 13:rerun ListFilter (Algorithm 4) with the new M 14: return {(μ i , αi ), for i ∈ J}Input: Samples S = {x 1 , . . . , x n }, vector μ, threshold τ , and A R Output:A vector μ ∈ R d 1: β ← τ 2: let α be the smallest value in [1 -ε RME , 1] that satisfies g(α) ⩽ β/2.If none exists, return μ 3: μ ← μ and let µ RME be the output of A R run on S with inlier fraction set to α. 4: while ∥μ -µ RME ∥ ⩽ 3 β/2 do 5: μ ← µ RME 6: β ← g(α)∥μ -µ * ∥ ⩽ O(ψ t (α/4) + f (α/4)). 2. If α ⩾ 1 -ε RME , then there exists μ ∈ L such that ∥μ -µ * ∥ ⩽ O(g(α -w 2 low )).Proof of Theorem B.2 can be found in Appendix D. Remark B.3. For any r ∈ N, we can increase probabilities of success of A kLD and A R from 1/2 to 1 -2 -r in the following way: we increase number of samples by a factor of r, randomly split S into r subsets of equal size, apply A kLD and A R to these subsets and concatenate their outputs. In the proofs we assume that the success probabilities are 1 -w C low for large enough constant C. This increases the size of the list returned by A kLD , the number of samples, and the running time by a factor O(log(1/w low )). In particular, we assume that the size of the list returned by A kLD is 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 on set T with almost no inliers, i.e., α < α low . We note that from the analysis (see Appendix D, or [3] , Proposition B.1), we always have upper bound |L| = O(1/α low ).An immediate consequence of Theorem B.2 are the following guarantees of directly applying Algorithm 3 to the mixture learning case with no separation. Here we present upper bounds for Algorithm 3, when no separation assumptions are imposed. Corollary B.5. Let d, k ∈ N + , w low ∈ (0, 10 -4 ], and t be an even integer. For all i = 1, . . . , k, let D i (µ i ) be a d-dimensional distribution with mean µ i ∈ R d and sub-Gaussian t-th central moments. Let ε > 0 and, for all i = 1, . . . , k, letw i ∈ [w low , 1], such that k i=1 w i + ε = 1. Let X be the d-dimensional mixture distribution X = k i=1 w i D i (µ i ) + εQ,where Q is an unknown adversarial distribution that can depend on all the other parameters. Let A kLD and A R satisfy Assumption 3.1.Then there exists an algorithm that, given poly(d, 1/w low )• (N LD (w low ) + N R (w low )) i.i.d.samples from X, and given also d, k, w low , and t, runs in time poly(d, 1/w low ) • (T LD (w low ) + T R (w low )) and outputs a list L of size |L| = O(1/w low ), such that, with probability at least 1 -wO(1) low : 1. For each i ∈ [k], there exists μ ∈ L such that ∥μ -µ i ∥ ⩽ O(ψ t (w i /4) + f (w i /4)). 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We provide experimental details, including computational resources, in Appendix I.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: We reviewed the NeurIPS Code of Ethics and confirm that our paper respects it.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 of our result is to deepen our theoretical understanding of fundamental problems in statistics, such as mixture learning.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or 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 a 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
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 to 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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.We adopt the following standard notation: f ≲ g, f = O(g), and g = Ω(f ) mean that f ⩽ Cg for some universal constant C > 0. O-notation hides polylogarithmic terms. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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).

The 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.

Overall, 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.
strength_weakness: strength_weakness: * 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?

* 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.
questions: 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.

* 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}$.

* Also see first point in "weaknesses".
limitations: limitations: -
paper_summary: paper_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.

Note: this is an emergency review, so I did not read the paper as closely and carefully as I'd like.
strength_weakness: strength_weakness: - 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?

====

Below are hopefully some constructive feedback that the authors can use to improve the paper:

- 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.

- The contexualization in prior work seems incomplete to me. I have two related complaints, both (roughly) related to finite covariance assumption setting.

1. 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.

2. 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).

- 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.

- 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?
questions: 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?

- 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?

- 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: limitations: Yes
paper_summary: paper_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$.
strength_weakness: strength_weakness: 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.
questions: questions: Please see above.
limitations: limitations: The limitations are adequately addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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.

2. How does your algorithm perform when the assumption of well-separated mixture components does not hold? Have you tested its robustness in such scenarios?  

3. 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? 

4. 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: limitations: NA
paper_summary: paper_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.

The 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:

1. 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.
2. 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.
strength_weakness: strength_weakness: - The two stage meta-algorithm can be time-consuming.
questions: 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: limitations: not applicable

Comments: comment: Thank you for the clarifications. I am keeping my positive score.
Thank you for the response. I am happy to raise my score considering all the discussions.
Thank you for the additional analysis. The authors have answered my question and I would like to keep my postive score.
Thanks for the responses. I'm happy with this discussion and hope the authors will incorporate this into the final paper. I've raised my score accordingly.
Thank you for your comment. Indeed, our main case of study is the possibly non-uniform mixture with $\varepsilon \gtrsim w_{\text{low}}$, where we obtain novel results. We will clarify the connections and differences from the prior works in the revised version.
> Re: $1 / w_{\text{low}}^{4/t}$. For the $1 / \sqrt{w_{\text{low}}}$ kind of separation, for bounded covariance mixtures, there is a simple intuition of Chebyshev's inequality to see that it is indeed necessary (and hence tight up to constants). Is there any analogously intuitive explanation for $1 / w_{\text{low}}^{4/t}$? That's what I was hoping for. The overall response doesn't quite get at that level of intuition.

Thank you for the comment. It is true that when $t=2$ and $\varepsilon \lesssim w_{\text{low}}$ the optimal separation is $O(1 / w_{\text{low}}^{1/t})$ (we note that this was achieved with optimal list size only last year). However, as far as we can tell, this separation is currently known to be achievable only when $t = 2$ and $\varepsilon \lesssim w_{\text{low}}$. In particular, 
1. When $t \geq 4$, to the best of our knowledge, the best mixture learning algorithm needs separation $1 / w_{\text{low}}^{2/t}$, even when there are no outliers [e.g., Kothari-Steinhardt-Steurer’18, Theorem 2.7]. This is still better than ours, but larger than $1 / w_{\text{low}}^{1/t}$.

2. When $\varepsilon \gg w_{\text{low}}$, as far as we can tell, nothing is known about the separation required to obtain optimal error and list-size. Our paper is the first in this setting.

Our goal was to obtain an algorithm that works when $\varepsilon \gg w_{\text{low}}$, and we focused on $t$-sub-Gaussian moments to show the generality of our result (importantly, with an application to clustering Gaussians). In this setting it is unclear that separation $O(1 / w_{\text{low}}^{1/t})$ is possible, given the observations in (1) and (2). It is possible that a much tighter analysis of our techniques may allow separation $O(1 / w_{\text{low}}^{2/t})$; we did not consider this kind of optimization essential to our paper, but acknowledge that it would be important future work to gain an even deeper understanding of the problem. 

On a high level, the separation is currently used in our proof for the following technical reason:
a separation of $1 / w_{\text{low}}^{1/t}$ suffices to show that the samples from a component are concentrated well when projected on a given direction. Our analysis needs such a property to hold along $1/w_{\text{low}}^2$ directions (between all pairs of components). In particular, in Lemma G.2, when applied for number of directions $m = 1 / w_{\text{low}}^2$, we need the separation $R$ to be at least $1 / w_{\text{low}}^{2/t}$ for a union bound to be applicable. Furthermore, to prove a technical Lemma D.6 we end up needing separation $1 / w_{\text{low}}^{4/t}$.

> On the comparison of $w_{\text{low}}^2$ with $w_i$ and $\varepsilon$, it seems from the explanation that it is slightly arbitrary (it could've been anything bigger than $w_{\text{low}}^3$?). In that case, it might be worth pointing out in the paper, for intuition for the reader.

Indeed, the reviewer is correct that, assuming separation $1 / w_{\text{low}}^{4/t}$, anything larger than $C w_{\text{low}}^3$, for some constant $C > 0$ could be used. We will add this clarification to the revised version.


[Kothari-Steinhardt-Steurer’18] Kothari, Pravesh K., Jacob Steinhardt, and David Steurer. "Robust moment estimation and improved clustering via sum of squares." Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018.
I skimmed the (intro of the) DKKLT22 and DKLP23 papers again. The latter seems to have some special-case results where they return a list of exactly $k$ components too, under extra assumptions like weight-uniformity or something about "no large sub-clusters". So it seems that this present submission vs these other works are making different assumptions and getting different results, and this work doesn't subsume the other works as the rebuttal seems to suggest. This is absolutely fine, of course, but it should be clearly explained in the revised submission given the connections between the different lines of work.
Thanks for your response. More comments from me:

- Re: $1/w_{low}^{4/t}$. For the $1/\sqrt{w_{low}}$ kind of separation, for bounded covariance mixtures, there is a simple intuition of Chebyshev's inequality to see that it is indeed necessary (and hence tight up to constants). Is there any analogously intuitive explanation for $1/w_{low}^{4/t}$? That's what I was hoping for. The overall response doesn't quite get at that level of intuition.

- On the comparison of $w_{low}^2$ with $w_i$ and $\epsilon$, it seems from the explanation that it is slightly arbitrary (it could've been anything bigger than $w_{low}^3$?). In that case, it might be worth pointing out in the paper, for intuition for the reader.

I'll reply to the overall rebuttal thread for my comments on the comparison with bounded-covariance mixture clustering works.