论文标题
学习（非常）简单的生成模型很难
Learning (Very) Simple Generative Models Is Hard
论文作者
论文摘要
在最新生成模型的最新经验成功的推动下，我们研究了以下无监督学习问题的计算复杂性。对于未知的神经网络$ f：\ mathbb {r}^d \ to \ mathbb {r}^{d'} $，让$ d $是$ \ mathbb {r}^{r}^{d'} $上的分布，通过推动标准高斯$ \ m m ianscal \ nat} $ _________________d $ {id。给定I.I.D. $ d $的样品是在统计距离内输出接近$ d $的任何分布。我们在统计查询（SQ）模型下显示，即使$ f $的输出坐标是具有$ \ log（d）$神经元的一个隐藏层的relu网络，也没有多项式时间算法可以解决此问题。以前，此问题的最佳下限是从下限进行监督学习的，并且需要至少两个隐藏层和$ \ mathrm {poly}（d）$ neurons [daniely-vardi '21，chen-gollakota-klivans-klivans-meka '22]。我们证明的关键要素是基于ode的构造，可用于紧凑的，分段线性的函数$ f $ f $，带有多项式遇到的斜坡，以便在$ \ mathcal {n}（n}（0,1）$ f $下的pushforward pushforward pushforward use $ f $ pu $匹配所有低度的$ \ \ \ mathcal {n} $的低度时刻。
Motivated by the recent empirical successes of deep generative models, we study the computational complexity of the following unsupervised learning problem. For an unknown neural network $F:\mathbb{R}^d\to\mathbb{R}^{d'}$, let $D$ be the distribution over $\mathbb{R}^{d'}$ given by pushing the standard Gaussian $\mathcal{N}(0,\textrm{Id}_d)$ through $F$. Given i.i.d. samples from $D$, the goal is to output any distribution close to $D$ in statistical distance. We show under the statistical query (SQ) model that no polynomial-time algorithm can solve this problem even when the output coordinates of $F$ are one-hidden-layer ReLU networks with $\log(d)$ neurons. Previously, the best lower bounds for this problem simply followed from lower bounds for supervised learning and required at least two hidden layers and $\mathrm{poly}(d)$ neurons [Daniely-Vardi '21, Chen-Gollakota-Klivans-Meka '22]. The key ingredient in our proof is an ODE-based construction of a compactly supported, piecewise-linear function $f$ with polynomially-bounded slopes such that the pushforward of $\mathcal{N}(0,1)$ under $f$ matches all low-degree moments of $\mathcal{N}(0,1)$.
