Learning Distributions Generated by One-Layer ReLU Networks
Learning Distributions Generated by One-Layer ReLU Networks
复制标题
DOI：
--
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Shanshan Wu;A. Dimakis;Sujay Sanghavi
中科院分区：
文献类型：
--
作者：
Shanshan Wu;A. Dimakis;Sujay Sanghavi
我们考虑了从i.i.d样本估计$d$维整流高斯分布参数的问题。通过一层ReLU神经网络传递一个标准高斯分布，定义了一个整流高斯分布。我们给出了一个简单的算法来估计参数（即，ReLU神经网络的权重矩阵和偏置向量），使用$\widetilde{O}(1/\eps^2)$样本和$\widetilde{O}(d^2/\eps^2)$时间（为了简单起见，忽略对数因素）达到一个误差$\eps\norm{W}_F$。这意味着我们可以使用$\widetilde{O}(\kappa^2d^2/\eps^2)$样本估计到总变异距离$\eps$的分布，其中$\kappa$是协方差矩阵的条件数。我们唯一的假设是偏置向量是非负的。在没有这个非负性假设的情况下，我们表明在任何误差范围内估计偏置向量需要的样本数量至少在偏置向量的无穷范数中呈指数级。我们的算法是基于矢量范数和两两角度可以分开估计的关键观察。我们使用了截断样本学习的最新结果。我们还证明了两个样本复杂度下界：估计误差至$\eps$的参数需要$\Omega(1/\eps^2)$样本，而估计总变异距离至$\eps$的分布需要$\Omega(d/\eps^2)$样本。第一个下界意味着我们的算法对于参数估计是最优的。最后，我们展示了学习两层生成模型和非负矩阵分解之间的有趣联系。实验结果支持了我们的分析。
We consider the problem of estimating the parameters of a $d$-dimensional rectified Gaussian distribution from i.i.d. samples. A rectified Gaussian distribution is defined by passing a standard Gaussian distribution through a one-layer ReLU neural network. We give a simple algorithm to estimate the parameters (i.e., the weight matrix and bias vector of the ReLU neural network) up to an error $\eps\norm{W}_F$ using $\widetilde{O}(1/\eps^2)$ samples and $\widetilde{O}(d^2/\eps^2)$ time (log factors are ignored for simplicity). This implies that we can estimate the distribution up to $\eps$ in total variation distance using $\widetilde{O}(\kappa^2d^2/\eps^2)$ samples, where $\kappa$ is the condition number of the covariance matrix. Our only assumption is that the bias vector is non-negative. Without this non-negativity assumption, we show that estimating the bias vector within any error requires the number of samples at least exponential in the infinity norm of the bias vector. Our algorithm is based on the key observation that vector norms and pairwise angles can be estimated separately. We use a recent result on learning from truncated samples. We also prove two sample complexity lower bounds: $\Omega(1/\eps^2)$ samples are required to estimate the parameters up to error $\eps$, while $\Omega(d/\eps^2)$ samples are necessary to estimate the distribution up to $\eps$ in total variation distance. The first lower bound implies that our algorithm is optimal for parameter estimation. Finally, we show an interesting connection between learning a two-layer generative model and non-negative matrix factorization. Experimental results are provided to support our analysis.