  We study the complexity of learning mixtures of separated Gaussians with
common unknown bounded covariance matrix. Specifically, we focus on learning
Gaussian mixture models (GMMs) on $\mathbb{R}^d$ of the form $P= \sum_{i=1}^k
w_i \mathcal{N}(\boldsymbol \mu_i,\mathbf \Sigma_i)$, where $\mathbf \Sigma_i =
\mathbf \Sigma \preceq \mathbf I$ and $\min_{i \neq j} \| \boldsymbol \mu_i -
\boldsymbol \mu_j\|_2 \geq k^\epsilon$ for some $\epsilon>0$. Known learning
algorithms for this family of GMMs have complexity $(dk)^{O(1/\epsilon)}$. In
this work, we prove that any Statistical Query (SQ) algorithm for this problem
requires complexity at least $d^{\Omega(1/\epsilon)}$. In the special case
where the separation is on the order of $k^{1/2}$, we additionally obtain
fine-grained SQ lower bounds with the correct exponent. Our SQ lower bounds
imply similar lower bounds for low-degree polynomial tests. Conceptually, our
results provide evidence that known algorithms for this problem are nearly best
possible.
