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