Robust Mixture Learning when Outliers Overwhelm Small Groups

We thank the reviewer for their appreciation of our work and for the feedback which will help to improve it. Below, we address specific comments and questions.

The two stage meta-algorithm can be time-consuming. [...] The paper lacks a presentation of the time complexity, and the experimental part also fails to provide results from this aspect. It would be beneficial to include information regarding the time complexity of the proposed algorithm to provide a comprehensive understanding of its computational efficiency.

Thank you for your comment. We provided a detailed analysis of the time complexity in the general rebuttal response (third part). In particular, our meta-algorithm has a small overhead complexity compared to base learners. We will include this discussion in the revised version.

We thank the reviewer for their appreciation of our work and for the feedback which will help to improve it. Below, we address specific comments and questions.

Experimental evaluation

The paper did not include real-world datasets and additional robust learning methods for comparison. [...] Have you considered validating your algorithm on real-world datasets? If so, could you provide details on these experiments? If not, what were the main obstacles? It would be beneficial to include results from real-world datasets to demonstrate the practical utility and robustness of your method. [...] How does your algorithm perform when the assumption of well-separated mixture components does not hold? Have you tested its robustness in such scenarios?

We would like to emphasize that the focus of our work is to first introduce the LD-ML framework and prove theoretical guarantees in this setting for an efficient algorithm. We agree that for the purpose of properly evaluating the effectiveness of the algorithm in practice we would need a much more extensive experimental setup that would be out of scope for this paper and we leave it for future work.

Having said that, it would be great if the reviewer could point to the specific robust learning methods (beyond the ones considered in the paper) they have in mind. For our experimental results, we opted for comparing our algorithm with 1) baselines that have provable guarantees in our setting (list decoding algorithm) and 2) three commonly used in practice clustering algorithms: (k-Means, robust k-Means and DBSCAN).

It would be great if the impact of the assumptions can be clarified. [...] How does your algorithm perform when the assumption of well-separated mixture components does not hold? Have you tested its robustness in such scenarios?

We will clarify the assumptions (in particular, we have a result which does not require well-separateness assumption) in the revised version. For example, Corollary C.4 answers the question about the impact of the well-separateness assumption, by showing the guarantees when the components are non-separated. We can move it to the main text so that the impact is more explicit in the main text.

Furthermore, in our experimental design we effectively included the setting where clusters are not separated (by inserting 'adversarial' clusters in the vicinity of the inlier component). Therefore, results in Figure 2 can also be interpreted as results for non-separated clusters (by assuming that the inserted clusters around the smallest cluster are part of the mixture).

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?

Thank you for your suggestion. Please see our general rebuttal response (third part) for the detailed analysis of the computational complexity.

We thank the reviewer for their appreciation of our work.

We thank the reviewer for their appreciation of our work and for the feedback which will help to improve it. Below, we address specific comments and questions.

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?

Thank you for the comment. Yes, we also obtain a result for the non-separated case. See lines 241-243 in the main text, and Corollary C.4 in the Appendix. In the revised version we will move the corollary statement to the main text.

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.

Indeed, this trade-off is inevitable and is present in prior works too. Please also see our discussion on the separation assumption in the general rebuttal (second part).

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.

Your understanding is correct, after the trimming operation, $Q$ is not guaranteed to be separated from the other components. This does not allow to model $Q$ as a part of the mixture. We will add a comparison with the DKLP work in the revised version (also see general rebuttal response).

The intro of this submission really focuses on the sub-Gaussian mixture case ($t \approx \log⁡ 1 / w_{\text{low}}$), but the general result applies also to $t = 2$. So I think a direct comparison to the technical results of the above paper as well as DKKLT22 is needed. For example, the separation assumption in this submission is much larger $1 / w_{\text{low}}^2$ than these prior works $1 / \sqrt{w_{\text{low}}}$. In general, I think it'd be very useful to clarify the results in this paper with respect to these DKKLT22 and DKLP papers (and other related works).

Thank you for the comment, please see our discussion on the separation assumption in the general rebuttal (second part), where we also compare with [DKLP23]. We will extend the comparison with prior work in the revised version.

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.

Thank you for your suggestion, we will take this into consideration for the revised version.

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?

Thank you for your comment, this was indeed an imprecise choice of words. We were mostly referring to the list decoding setting, where algorithms are provided with inlier proportion (see, e.g., [1, 2]). Here, the extension to the unknown inlier proportion seems challenging for the following two reasons:
First, e.g., for the filtering technique, in order to obtain optimal error, one needs to filter with the ‘correct’ polynomial degree, and this degree depends on the fraction of inliers.
Second, in order to obtain a list of predictions, a lower bound on the size of inlier sets is required, in order to decide when to ‘discard’ too small subsets.
Overall, we argue that it is not straightforward to extend prior methods to unknown component weights, and this extension is one of our contributions.

Any intuition for why $w_{\text{low}}^2$ is the right quantity to compare with $w_i$ and $\varepsilon$?

Thank you for the question. First, we would like to note that it is generally not possible to obtain guarantees depending only on $w_i / (w_i + \varepsilon)$, since there are always samples from other components which are effectively ‘outliers’ for a fixed component. For example, consider the Gaussian case with $\varepsilon = 0$, and $w_i / (w_i + \varepsilon) = 1$, but the approximation error is clearly greater than $0 = \sqrt{\log (w_i + \varepsilon) / w_i)}$.

Further, the specific value $w_{\text{low}}$ connects to the separation assumption (see discussion on the necessity of the separation assumption in the general response): if the components are $\Omega\left(\left(1 / w_{\text{low}}\right)^{4/t}\right)$ separated, only an $O(w_{\text{low}}^4)$ fraction of samples from one mixture component may lie in the vicinity of another, so in total $O(w_{\text{low}}^3) \leq w_{\text{low}}^2$ points from other components. We also remark that $w_i$ always dominates $w_{\text{low}}^2$.

Definition 2.1 is essentially assuming boundedness compared to the identity covariance Gaussian. For mixtures where the components have, say, covariance bounded by 𝑐 times identity, does the algorithm need to know 𝑐, or can 𝑐 be estimated easily in this context?

We assume that the algorithm knows at least a valid upper bound (and obtain guarantees depending on this upper bound). We leave the question of unknown covariances for future work (the main challenge here is to still obtain a small list size $k + O(\varepsilon / w_{\text{low}})$, while correctly ‘guessing’ the covariance).

How hard is it to go beyond the corruption model of (2.1), to get adaptive additive corruption?

Thank you for the question, please see our general rebuttal response (first part).

For references [1, 2], please see the main rebuttal response.

We thank the reviewer for their appreciation of our work and for the feedback which will help to improve it. Below, we address specific comments and questions.

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?

Thank you for the question, please see our general rebuttal response (first part).

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.

Thank you for the suggestion, we will mention the result on non-separated mixtures in the main text in the revised version.

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.

Thank you for the suggestion, we will extend the discussion on the results for the bounded moment distributions in the revised version.

The algorithm that gets errors all the way down to $𝑂(\sqrt{\log⁡(1/w_i)})$ has super-polynomial complexity. Does the existing SQ lower bound from list-decodable mean estimation in [3] justify this via some easy reduction? If so, it would be good to include.

Yes, there is a simple reduction of SQ lower bounds (same as IT lower bounds), we mentioned it in the Appendix (lines 1001-1004). We will move the paragraph to the main text in the revised version.

Is the optimal separation for the bounded moments case indeed $O\left(\left(\frac{1}{w_{\text{low}}}\right)^{4/t}\right)$? I just want to make sure that there is no typographical error in the exponent, since for bounded second moments usually things scale with square root of $w_{\text{low}}$.

Thank you for raising this point. Yes, there is no typographical error (please see our general rebuttal response, second part).

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.