We give a new algorithm for learning mixtures of $k$ Gaussians (with identity
covariance in $\mathbb{R}^n$) to TV error $\varepsilon$, with quasi-polynomial
($O(n^{\text{poly log}\left(\frac{n+k}{\varepsilon}\right)})$) time and sample
complexity, under a minimum weight assumption. Unlike previous approaches, most
of which are algebraic in nature, our approach is analytic and relies on the
framework of diffusion models. Diffusion models are a modern paradigm for
generative modeling, which typically rely on learning the score function
(gradient log-pdf) along a process transforming a pure noise distribution, in
our case a Gaussian, to the data distribution. Despite their dazzling
performance in tasks such as image generation, there are few end-to-end
theoretical guarantees that they can efficiently learn nontrivial families of
distributions; we give some of the first such guarantees. We proceed by
deriving higher-order Gaussian noise sensitivity bounds for the score functions
for a Gaussian mixture to show that that they can be inductively learned using
piecewise polynomial regression (up to poly-logarithmic degree), and combine
this with known convergence results for diffusion models. Our results extend to
continuous mixtures of Gaussians where the mixing distribution is supported on
a union of $k$ balls of constant radius. In particular, this applies to the
case of Gaussian convolutions of distributions on low-dimensional manifolds, or
more generally sets with small covering number.

给出了一个新的学习高斯混合模型的算法，其目标是通过扩散模型中的得分函数以及多项式回归来高效学习混合高斯分布，对于具有最小权重假设的情况下，计算出来的误差和时间复杂度具有准多项式级别的优势，并扩展到具有支持在常数半径范围内的多个球的混合高斯的情况。

使用扩散模型学习高斯混合模型

Learning Mixtures of Gaussians Using Diffusion Models

We study the problem of overcoming exponential sample complexity in
differential entropy estimation under Gaussian convolutions. Specifically, we
consider the estimation of the differential entropy $h(X+Z)$ via $n$
independently and identically distributed samples of $X$, where $X$ and $Z$ are
independent $D$-dimensional random variables with $X$ subgaussian with bounded
second moment and $Z\sim\mathcal{N}(0,\sigma^2I_D)$. Under the absolute-error
loss, the above problem has a parametric estimation rate of
$\frac{c^D}{\sqrt{n}}$, which is exponential in data dimension $D$ and often
problematic for applications. We overcome this exponential sample complexity by
projecting $X$ to a low-dimensional space via principal component analysis
(PCA) before the entropy estimation, and show that the asymptotic error
overhead vanishes as the unexplained variance of the PCA vanishes. This implies
near-optimal performance for inherently low-dimensional structures embedded in
high-dimensional spaces, including hidden-layer outputs of deep neural networks
(DNN), which can be used to estimate mutual information (MI) in DNNs. We
provide numerical results verifying the performance of our PCA approach on
Gaussian and spiral data. We also apply our method to analysis of information
flow through neural network layers (c.f. information bottleneck), with results
measuring mutual information in a noisy fully connected network and a noisy
convolutional neural network (CNN) for MNIST classification.

研究高斯卷积下微分熵估计的样本复杂性问题，通过使用主成分分析方法解决了在数据维度指数级增长时估计微分熵的缺陷，并提出在深度神经网络中使用低维度 PCA 方法对信息流进行研究的应用，对噪声卷积神经网络的 MNIST 分类问题进行了实验验证。