研究高维高斯混合模型的高效学习，发现均匀权重下仍存在本质困难。
On Learning Parallel Pancakes with Mostly Uniform Weights
- 提出统计查询下界，证明均匀权重时学习复杂度不可突破
- 在多数权重均匀时，给出准多项式时间算法
- 揭示权重分布对学习难度的关键影响，适合理论学习者参考
我们研究在 $\mathbb{R}^d$ 上学习 $k$-高斯混合模型（$k$-GMM）的复杂性。该任务在一般情况下具有 $d^{Ω(k)}$ 的复杂度下界。为规避此指数下界，研究聚焦于满足额外结构假设的 GMM 类。一种自然假设是成分权重不呈指数级小，且所有成分共享未知协方差。近期工作给出了 $d^{O(\log(1/w_{\min}))}$ 时间算法，其中 $w_{\min}$ 为最小权重。我们的第一个主要结果是统计查询（SQ）下界，表明即使在均匀权重情形下，该准多项式上界也几乎最优——区分此类混合与标准高斯是 SQ 难题。我们进一步探究权重分布对学习复杂性的影响。第二个主要结果是：当大多数权重均匀而少数权重可任意时，该测试任务仍存在准多项式上界。
原文摘要 · Abstract (English)
We study the complexity of learning $k$-mixtures of Gaussians ($k$-GMMs) on $\mathbb{R}^d$. This task is known to have complexity $d^{Ω(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。