Title: On Learning Parallel Pancakes with Mostly Uniform Weights Show Chinese title

Title: 关于主要具有均匀权重的平行煎饼学习

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 full generality. To circumvent this exponential lower bound on the number of components, research has focused on learning families of GMMs satisfying additional structural properties. A natural assumption posits that the component weights are not exponentially small and that the components have the same unknown covariance. Recent work gave a $d^{O(\log(1/w_{\min}))}$-time algorithm for this class of GMMs, where $w_{\min}$ is the minimum weight. Our first main result is a Statistical Query (SQ) lower bound showing that this quasi-polynomial upper bound is essentially best possible, even for the special case of uniform weights. Specifically, we show that it is SQ-hard to distinguish between such a mixture and the standard Gaussian. We further explore how the distribution of weights affects the complexity of this task. Our second main result is a quasi-polynomial upper bound for the aforementioned testing task when most of the weights are uniform while a small fraction of the weights are potentially arbitrary. Show Chinese abstract

Abstract: 我们研究了在$\mathbb{R}^d$上学习$k$-混合高斯分布（$k$-GMMs）的复杂性。此任务在完全一般情况下已知具有$d^{\Omega(k)}$的复杂度。为了绕过对组件数量的指数下界，研究集中于学习满足额外结构特性的GMM族。一个自然的假设认为组件权重不是指数小的，并且组件具有相同的未知协方差。近期的工作为此类GMM提供了一个运行时间为$d^{O(\log(1/w_{\min}))}$的算法，其中$w_{\min}$是最小权重。我们的第一个主要结果是统计查询（SQ）下界，表明这个准多项式上界本质上是最好的，即使对于均匀权重的特殊情况也是如此。具体来说，我们证明了区分这种混合与标准高斯分布是SQ困难的。我们进一步探讨了权重分布如何影响此任务的复杂性。我们的第二个主要结果是当大多数权重是均匀的而一小部分权重可能是任意时，针对上述测试任务的准多项式上界。