Consider the following fundamental learning problem: given input examples $x
\in \mathbb{R}^d$ and their vector-valued labels, as defined by an underlying
generative neural network, recover the weight matrices of this network. We
consider two-layer networks, mapping $\mathbb{R}^d$ to $\mathbb{R}^m$, with $k$
non-linear activation units $f(\cdot)$, where $f(x) = \max \{x , 0\}$ is the
ReLU. Such a network is specified by two weight matrices, $\mathbf{U}^* \in
\mathbb{R}^{m \times k}, \mathbf{V}^* \in \mathbb{R}^{k \times d}$, such that
the label of an example $x \in \mathbb{R}^{d}$ is given by $\mathbf{U}^*
f(\mathbf{V}^* x)$, where $f(\cdot)$ is applied coordinate-wise. Given $n$
samples as a matrix $\mathbf{X} \in \mathbb{R}^{d \times n}$ and the (possibly
noisy) labels $\mathbf{U}^* f(\mathbf{V}^* \mathbf{X}) + \mathbf{E}$ of the
network on these samples, where $\mathbf{E}$ is a noise matrix, our goal is to
recover the weight matrices $\mathbf{U}^*$ and $\mathbf{V}^*$.
In this work, we develop algorithms and hardness results under varying
assumptions on the input and noise. Although the problem is NP-hard even for
$k=2$, by assuming Gaussian marginals over the input $\mathbf{X}$ we are able
to develop polynomial time algorithms for the approximate recovery of
$\mathbf{U}^*$ and $\mathbf{V}^*$. Perhaps surprisingly, in the noiseless case
our algorithms recover $\mathbf{U}^*,\mathbf{V}^*$ exactly, i.e., with no
error. To the best of the our knowledge, this is the first algorithm to
accomplish exact recovery. For the noisy case, we give the first polynomial
time algorithm that approximately recovers the weights in the presence of
mean-zero noise $\mathbf{E}$. Our algorithms generalize to a larger class of
rectified activation functions, $f(x) = 0$ when $x\leq 0$, and $f(x) > 0$
otherwise.

该研究提出了一种基于高斯分布假设的算法，可以在多项式时间内准确地恢复两层神经网络的权重矩阵，即使在存在噪声的情况下。

在多项式时间内学习两层修正线性单元神经网络

Learning Two Layer Rectified Neural Networks in Polynomial Time

In this paper we investigate the performance of different types of rectified
activation functions in convolutional neural network: standard rectified linear
unit (ReLU), leaky rectified linear unit (Leaky ReLU), parametric rectified
linear unit (PReLU) and a new randomized leaky rectified linear units (RReLU).
We evaluate these activation function on standard image classification task.
Our experiments suggest that incorporating a non-zero slope for negative part
in rectified activation units could consistently improve the results. Thus our
findings are negative on the common belief that sparsity is the key of good
performance in ReLU. Moreover, on small scale dataset, using deterministic
negative slope or learning it are both prone to overfitting. They are not as
effective as using their randomized counterpart. By using RReLU, we achieved
75.68\% accuracy on CIFAR-100 test set without multiple test or ensemble.

本文通过评估不同类型的修正线性单元 rectified activation functions（包括：标准修正线性单元（ReLU），泄漏修正线性单元（Leaky ReLU），参数修正线性单元（PReLU）以及随机泄漏修正线性单元（RReLU））在图像分类任务中的表现，结论表明，对修正激活单元中的负部分引入非零斜率可以始终改善结果，从而推翻了稀疏性是 ReLU 良好性能的关键的常见信念。另外，在小规模数据集上，使用确定性的负斜率或学习固定斜率都容易过拟合，使用随机斜率则更为有效。通过使用 RReLU，我们在 CIFAR-100 测试集上实现了 75.68％的准确度（无多次测试或集合）。