Abstract
We study the complexity of learning $k$-mixtures of Gaussians ($k$-GMMs) on$\mathbb{R}^d$. This task is known to have complexity $d^{\Omega(k)}$ in fullgenerality. To circumvent this exponential lower bound on the number ofcomponents, research has focused on learning families of GMMs satisfyingadditional structural properties. A natural assumption posits that thecomponent weights are not exponentially small and that the components have thesame unknown covariance. Recent work gave a $d^{O(\log(1/w_{\min}))}$-timealgorithm for this class of GMMs, where $w_{\min}$ is the minimum weight. Ourfirst main result is a Statistical Query (SQ) lower bound showing that thisquasi-polynomial upper bound is essentially best possible, even for the specialcase of uniform weights. Specifically, we show that it is SQ-hard todistinguish between such a mixture and the standard Gaussian. We furtherexplore how the distribution of weights affects the complexity of this task.Our second main result is a quasi-polynomial upper bound for the aforementionedtesting task when most of the weights are uniform while a small fraction of theweights are potentially arbitrary.