深度学习中的身份很重要

摘要

深度学习中的一个新兴设计原则是深度人工神经网络的每一层都应该能够轻松地表达恒等变换。 这个想法不仅激发了各种标准化技术，例如批量标准化，而且也是残差网络取得巨大成功的关键。

在这项工作中，我们将身份参数化的原理置于更坚实的理论基础上，同时取得了进一步的实证进展。 我们首先给出一个非常简单的证明，证明任意深度的线性残差网络没有虚假的局部最优值。 线性前馈网络在其标准参数化中的相同结果要微妙得多。 其次，我们表明，具有 ReLu 激活的残差网络具有通用的有限样本表达能力，只要模型的参数多于样本大小，网络就可以表示其样本的任何函数。

直接受到我们理论的启发，我们尝试了一种极其简单的残差架构，仅包含残差卷积层和 ReLu 激活，但没有批量归一化、dropout 或最大池。 我们的模型在 CIFAR10、CIFAR100 和 ImageNet 分类基准上比之前的全卷积网络有了显着改进。

1简介

用于图像分类的传统卷积神经网络，例如 AlexNet ([13])，其参数化方式为：当所有可训练权重均为 $0$ 时，卷积层表示 $0$-映射。 此外，权重围绕 $0.$ 对称初始化 这种标准参数化使得使用随机梯度方法训练的卷积层保留已经很好的特征变得非常重要。 换句话说，这样的卷积层在训练时不能轻易收敛到恒等变换。

[9] 通过批量归一化观察到并部分解决了这个缺点，即使用学习的均值和协方差对输入进行逐层白化。 但这个想法仍然有些隐含，直到残差网络([6];[7])明确引入了卷积层的重新参数化，这样当所有可训练的权重都是$0,$层代表恒等函数。 形式上，对于输入 $x,$，每个残差层的形式为 $x+h(x),$ 而不是 $h(x).$ 这种简单的重新参数化允许更深层次的架构，很大程度上避免了梯度消失（或爆炸）的问题。 从那时起，残差网络以及使用相同参数化的后续架构在各种计算机视觉基准（例如 CIFAR10 和 ImageNet）上始终取得了最先进的结果。

1.1 我们的贡献

在这项工作中，我们从理论角度考虑恒等参数化，同时将我们的一些理论见解转化为实验。 宽松地说，我们的第一个结果强调了身份参数化如何使优化变得更容易，而我们的第二个结果表明对于表示来说也是如此。

线性残差网络。

由于一般的非线性神经网络超出了当前优化理论方法的范围，因此我们将深度线性网络的情况视为简化模型。 线性网络将任意线性映射表示为矩阵序列 $A_{\mathrm{\ell }}\mathrm{\cdots }{A}_2{A}_1.$ 目标函数为 $𝔼{\Vert y-A_{\mathrm{\ell }}\mathrm{\cdots }{A}_{1}x\Vert }^2$，其中 $y=Rx$ 用于某些未知的线性变换，$R$ 和 $x$ 是从分布中得出的。 近年来，人们对这种线性网络进行了积极的研究，作为通向一般非线性情况的垫脚石（参见1.2节）。 尽管 $A_{\mathrm{\ell }}\mathrm{\cdots }{A}_1$ 只是一个线性映射，但因子变量 $(A_{\mathrm{\ell }},\mathrm{\dots },A_1)$ 的优化问题是非凸的。

与残差网络类似，我们将目标函数参数化为

$$\underset{A_1,\mathrm{\dots },A_{\mathrm{\ell }}}{\min }𝔼{\Vert y-(I+A_{\mathrm{\ell }})\mathrm{\cdots }(I+A_1)x\Vert }^2.$$ (1.1)

直观地说，当深度 $\mathrm{\ell }$ 足够大时，我们可以希望目标函数 $R$ 具有因子表示，其中每个矩阵 $A_i$ 具有较小的矩阵规范。 例如，任何对称正半inite 矩阵 $O$ 都可以写成乘积 $O=O_{\mathrm{\ell }}\mathrm{\cdots }{O}_1,$，其中每个 $O_i=O^{1/\mathrm{\ell }}$ 对于大的 $\mathrm{\ell }$ 都非常接近同一性，因此 $A_i=O_i-I$ 具有较小的谱规范。 我们首先证明类似的主张对于所有具有正行列式的线性变换 $R$ 都是正确的. 具体来说，我们证明对于每个具有 $det(R)>0$ 的线性变换 $R$，都存在一个 (1.1) 的全局优化器 $(A_1,\mathrm{\dots },A_{\mathrm{\ell }})$，使得足够大的深度$\mathrm{\ell },$

$$\underset{1\le i\le \mathrm{\ell }}{\max }\Vert A_i\Vert \le O(1/\mathrm{\ell }).$$ (1.2)

这里，$\Vert A\Vert$表示$A.$的谱范数 常数因子取决于$R.$的条件。我们在定理2.1中给出了正式的陈述。 该定理有一个有趣的结果，即随着深度的增加，存在较小的范数解，因此正则化可能会抵消参数的增加。

确定了小范数解的存在性后，我们对线性残差网络的主要结果表明，当所有矩阵都具有足够小的范数时，目标函数 (1.1) 实际上很容易优化。 更正式地说，让 $A=(A_1,\mathrm{\dots },A_{\mathrm{\ell }})$ 和 $f(A)$ 表示 (1.1) 中的目标函数，我们可以证明仅当 $f(A)=0$ 时梯度才消失> 前提是${\max }_i\Vert A_i\Vert \le O(1/\mathrm{\ell }).$ 参见定理2.2。 这个结果意味着线性残差网络除了全局最优之外没有临界点。 相比之下，对于标准线性神经网络，通过[12]的工作，我们只知道这些网络除了全局最优之外没有局部最优，但并不排除其他临界点。 事实上，设置 $A_i=0$ 总是会导致标准参数化中出现错误的临界点。

通用有限样本表达能力。

回到具有 ReLU 激活的非线性残差网络，我们可以问：仅基于具有 ReLU 激活的残差层的深度神经网络的表达能力如何？ 为了回答这个问题，我们给出了一个非常简单的结构，表明这种残差网络具有完美的有限样本表达能力。 换句话说，具有 ReLU 激活的残差网络可以轻松表达大小为 $n,$ 的样本的任何函数，只要它具有足够多于 $n$ 的参数。 请注意，这个要求在实践中很容易满足。 例如，在 CIFAR 10 ($n=50000$) 上，成功的残差网络通常具有多个 ${10}^6$ 个参数。 更正式地说，对于大小为 $n$ 且具有 $r$ 类的数据集，我们的构造需要 $O(n\log n+r^2)$ 参数。 定理3.2给出了正式的陈述。

我们构造中的每个残差层的形式为 $x+V\mathrm{ReLU}(Ux),$，其中 $U$ 和 $V$ 是线性变换。 这些层比标准残差层简单得多，标准残差层通常具有两个 ReLU 激活以及两个批量归一化实例。

全卷积残差网络的强大功能。

直接受到我们表达性结果的简单性的启发，我们在 CIFAR10、CIFAR100 和 ImageNet 数据集上尝试了非常相似的架构。 我们的架构只是一系列卷积残差层，每个层都有一个 ReLU 激活，但没有标准架构中常见的批量归一化、丢失或最大池化。 最后一层是未经训练的固定随机投影。 根据我们的理论，卷积权重在 $0,$ 附近初始化，主要使用高斯噪声作为对称破坏器。 唯一的正则化器是标准权重衰减(${\mathrm{\ell }}_2$-正则化），并且不需要 dropout。 尽管很简单，我们的架构在 CIFAR10 基准（使用标准数据增强）上达到了 $6.38\%$ top-$1$ 分类错误。 这与[6]中报告的最佳残差网络具有竞争力，后者实现了$6.43\%$。 此外，它还改进了之前由 [15] 实现的最佳全卷积网络 $7.25\%$ 的性能。 与我们的不同，之前的全卷积架构还需要对整个数据集进行 dropout 和非标准预处理（ZCA）。 我们的架构还显着改进了 Cifar100 和 ImageNet 上的 [15]。

1.2相关工作

自从残差网络([6];[7])出现以来，大多数最先进的图像分类网络都采用了卷积网络的残差参数化层。 [8] 报告了残差网络变体（称为密集网络)的进一步令人印象深刻的改进。 这些网络不是将原始输入添加到卷积层的输出，而是直接通过串联保留原始特征。 在此过程中，密集网络还能够轻松地在更高维空间中对身份嵌入进行编码。 看看我们的理论结果是否也适用于这种残差网络变体将会很有趣。

尽管全面的答案仍然难以捉摸，但在理解神经网络的优化领域方面最近取得了进展。 [5]和[4]中的实验表明，训练目标具有有限数量的具有较大函数值的不良局部最小值。 [3] 的工作在神经网络的优化景观与物理学中的自旋玻璃模型的优化景观之间进行了类比 ([1])。 [14]表明$2$层神经网络没有不好的可微局部最小值，但他们没有证明一个好的可微局部最小值确实存在。 [2]和[12]表明线性神经网络没有坏的局部极小值。 相比之下，我们表明深度线性残差网络的优化景观没有坏的临界点，这是一个更强、更理想的特性。 我们的证明也明显更简单，说明了重新参数化优化的力量。 我们的结果还表明，与较浅的网络相比，更深的网络可能具有更理想的优化景观。

2 线性残差网络的优化景观

考虑从噪声测量 $y=Rx+\xi ,$ 学习线性变换 $R:{ℝ}^d\to {ℝ}^d$ 的问题，其中 $\xi \in 𝒩(0,I_d)$ 是 $d$ 维球形高斯向量。 用$𝒟$表示输入数据$x,$的分布，令$\mathrm{\Sigma }={𝔼}_{x\sim 𝒟}[x{x}^{\top }]$为其协方差矩阵。

当然，有很多方法可以解决这个经典问题，但我们的目标是深入了解神经网络，特别是残差网络的优化领域。 因此，我们通过一系列权重矩阵 $A_1,\mathrm{\dots },A_{\mathrm{\ell }}\in {ℝ}^{d\times d}$ 来参数化我们的学习模型，

$h_0$ $=x,h_j=h_{j-1}+A_j{h}_{j-1},\widehat{y}=h_{\mathrm{\ell }}.$ (2.1)

这里 $h_1,\mathrm{\dots },h_{\mathrm{\ell }-1}$ 是 $\mathrm{\ell }-1$ 隐藏层，$\widehat{y}=h_{\mathrm{\ell }}$ 是学习模型对输入 $x.$ 的预测 更简洁地说，我们有

$\widehat{y}=(I+A_{\mathrm{\ell }})\mathrm{\dots }(I+A_1)x.$

很容易看出这个模型可以表达任何线性变换$R.$我们将使用$A$作为所有权重矩阵的简写，即$\mathrm{\ell }\times d\times d$ 维张量，包含 $A_1,\mathrm{\dots },A_{\mathrm{\ell }}$ 作为切片。 我们的目标函数是最大似然估计，

$f(A,(x,y))={\parallel \widehat{y}-y\parallel }^2={\parallel (I+A_{\mathrm{\ell }})\mathrm{\dots }(I+A_1)x-Rx-\xi \parallel }^2.$ (2.2)

我们将分析人口风险的情况，定义为：

$f(A):=𝔼\left[f(A,(x,y))\right].$

回想一下，$\parallel A_i\parallel$ 是 $A_i$ 的谱范数。 我们将张量 $A$ 的范数 $\left|\right||\cdot |\left|\right|$ 定义为其切片的谱范数的最大值，

$\Vert \left|A\right|\Vert :=\underset{1\le i\le \mathrm{\ell }}{\max }\parallel A_i\parallel .$

本节第一个定理指出，目标函数$f$具有较小$\left|\right||\cdot |\left|\right|$范数的最优解，其与层数成反比 $\mathrm{\ell }$。 因此，当架构很深时，我们可以寻找相当小的范数解决方案。 我们定义$\gamma :=\max \{|\log {\sigma }_{\max }(R)|,|\log {\sigma }_{\min }(R)|\}$。 这里${\sigma }_{\min }(\cdot ),{\sigma }_{\max }(\cdot )$分别表示$R$的最小和最大奇异值。

Theorem 2.1.

假设$\mathrm{\ell }\mathrm{\ge }\mathrm{3}\mathit{}\gamma$和$\det \mathrm{(}R\mathrm{)}\mathrm{>}\mathrm{0}$。 那么，存在一个具有范数的群体风险$f\mathit{}\mathrm{(}\mathrm{\cdot }\mathrm{)}$的全局最优解$A^{\mathrm{\star }}$

$$\Vert \left|A^{\star }\right|\Vert \le (4\pi +3\gamma )/\mathrm{\ell }.$$

我们首先注意到条件$det(R)>0$在以下意义上不失一般性。 给定任何具有负行列式的线性变换 $R$ ，我们可以通过使用附加维度增强数据和标签来有效地翻转行列式：让 $x^{\prime }=[x,b]$ 和 $y^{\prime }=[y,-b]$ ，其中$b$是一个独立的随机变量（例如，来自标准正态分布），并让。 然后，我们有 $y^{\prime }=R^{\prime }{x}^{\prime }+\xi$ 和 $det(R^{\prime })=-det(R)>0$。

其次，我们注意到这里 $\gamma$ 应该被认为是一个常量，因为如果 $R$ 太大（或太小），我们可以适当缩放数据，以便 ${\sigma }_{\min }(R)\le 1\le {\sigma }_{\max }(R)$. 具体来说，如果${\sigma }_{\max }(R)/{\sigma }_{\min }(R)=\kappa$，那么我们可以正确缩放输出，以便${\sigma }_{\min }(R)=1/\sqrt{\kappa }$和${\sigma }_{\max }(R)=\sqrt{\kappa }$。 在本例中，我们有 $\gamma =\log \sqrt{\kappa }$，对于相当大的条件数 $\kappa$，它将保持一个小常数。 我们还指出，我们在分析中没有尝试优化常量因素。 定理2.1的证明比较复杂，推迟到A节。

鉴于对定理 2.1 的观察，我们将注意力限制在分析 $A$ 与 $\left|\right||\cdot |\left|\right|$ 集合中的 $f(\cdot )$ 的景观 -范数小于$\tau$，

${ℬ}_{\tau }=\{A\in {ℝ}^{\mathrm{\ell }\times d\times d}:\Vert \left|A\right|\Vert \le \tau \}.$

这里使用定理2.1，半径$\tau$应该被认为是$1/\mathrm{\ell }$的量级。 我们在本节中的主要定理声称，对于任何 ，域 ${ℬ}_{\tau }$ 中不存在坏临界点。 回想一下，临界点具有消失梯度。

Theorem 2.2.

对于任何，我们有域${ℬ}_{\tau }$内目标函数$f\mathit{}\mathrm{(}\mathrm{\cdot }\mathrm{)}$的任何临界点$A$也必须是全局最小值。

定理2.2表明优化器足以收敛到总体风险的临界点，因为所有临界点也是全局最小值。

此外，除了定理2.2之外，我们还有域${ℬ}_{\tau }$内的任何$A$满足

${\parallel \nabla f(A)\parallel }_F^2\ge 4\mathrm{\ell }{(1-\tau )}^{2\mathrm{\ell }-2}{\sigma }_{\min }(\mathrm{\Sigma })(f(A)-C_{\text{opt}}).$ (2.3)

这里$C_{\text{opt}}$是$f(\cdot )$的全局最小值，${\parallel \nabla f(A)\parallel }_F$表示欧氏范数 $\mathrm{\ell }\times d\times d$维张量$\nabla f(A)$的。 注意，${\sigma }_{\min }(\mathrm{\Sigma })$表示$\mathrm{\Sigma }$的最小奇异值。

方程 (2.3) 表示，与误差相比，梯度具有相当大的范数，这保证了迭代时梯度下降收敛到全局最小值 ([11])留在域${ℬ}_{\tau },$内，这不能由定理2.2本身保证。

为了证明定理2.2，我们从一个简化群体风险的简单主张开始。 我们用${\parallel \cdot \parallel }_F$表示矩阵的Frobenius范数，$⟨A,B⟩$表示标准基中$A$和$B$的内积（即 $⟨A,B⟩=\text{tr}(A^{\top }B)$，其中 $\text{tr}(\cdot )$ 表示矩阵的迹。）

断言 2.3。

在本节的设置中，我们有，

$f(A)={\parallel ((I+A_{\mathrm{\ell }})\mathrm{\dots }(I+A_1)-R){\mathrm{\Sigma }}^{1/2}\parallel }_F^2+C.$ (2.4)

这里$C$是一个不依赖于$A$的常数，${\mathrm{\Sigma }}^{\mathrm{1}\mathrm{/}\mathrm{2}}$表示$\mathrm{\Sigma }$的平方根，即满足$B^{\mathrm{2}}\mathrm{=}\mathrm{\Sigma }$的唯一对称矩阵$B$。

断言 2.3 的证明。

设$\text{tr}(A)$表示矩阵$A$的迹。 让$E=(I+A_{\mathrm{\ell }})\mathrm{\dots }(I+A_1)-R$。 回顾 $f(A)$ 的定义并使用方程 (2.2)，我们有

$f(A)$ $=𝔼\left[{\parallel Ex-\xi \parallel }^2\right]$ (by equation (2.2) )

$=𝔼\left[{\parallel Ex\parallel }^2+{\parallel \xi \parallel }^2-2⟨Ex,\xi ⟩\right]$

$=𝔼\left[\text{tr}(Ex{x}^{\top }{E}^{\top })\right]+𝔼\left[{\parallel \xi \parallel }^2\right]$ (since $𝔼\left[⟨Ex,\xi ⟩\right]=𝔼\left[⟨Ex,𝔼\left[\xi |x\right]⟩\right]=0$)

$=\text{tr}\left(E𝔼\left[x{x}^{\top }\right]E^{\top }\right)+C$ (where $C=𝔼[{\xi }^2]$)

$=\text{tr}(E\mathrm{\Sigma }{E}^{\top })+C={\parallel E{\mathrm{\Sigma }}^{1/2}\parallel }_F^2+C.$ (since $𝔼\left[x{x}^{\top }\right]=\mathrm{\Sigma }$)

∎

接下来，我们通过简单的矩阵演算计算目标函数 $f(\cdot )$ 的梯度。 我们将完整的证明推迟到 A 部分。

Lemma 2.4.

$f\mathit{}\mathrm{(}\mathrm{\cdot }\mathrm{)}$ 的梯度可以写为，

${\displaystyle \frac{\partial f}{\partial A_i}}=2(I+A_{i+1}^{\top })\mathrm{\dots }(I+A_{\mathrm{\ell }}^{\top })E\mathrm{\Sigma }(I+A_1^{\top })\mathrm{\dots }(I+A_{i-1}^{\top }),$ (2.5)

其中 $E\mathrm{=}\mathrm{(}I\mathrm{+}{A}_{\mathrm{\ell }}\mathrm{)}\mathit{}\mathrm{\dots }\mathit{}\mathrm{(}I\mathrm{+}{A}_{\mathrm{1}}\mathrm{)}\mathrm{-}R$ 。

现在我们准备证明定理2.2。 关键的观察是每个矩阵 $A_j$ 具有较小的范数并且不能取消单位矩阵。 因此，方程(2.5)中的梯度是除误差矩阵$E$之外的非零矩阵的乘积。因此，如果梯度消失，那么唯一的可能是矩阵$E$消失，这又意味着$A$是最优解。

定理证明2.2。

使用引理 2.4，我们有，

${\parallel {\displaystyle \frac{\partial f}{\partial A_i}}\parallel }_F$ $=2{\parallel (I+A_{i+1}^{\top })\mathrm{\dots }(I+A_{\mathrm{\ell }}^{\top })E\mathrm{\Sigma }(I+A_1^{\top })\mathrm{\dots }(I+A_{i-1}^{\top })\parallel }_F$ (by Lemma 2.4)

$\ge 2{\displaystyle \prod _{j\ne i}}{\sigma }_{\min }(I+A_i^{\top })\cdot {\sigma }_{\min }(\mathrm{\Sigma }){\parallel E\parallel }_F$ (by Claim C.2)

$\ge 2{(1-\tau )}^{\mathrm{\ell }-1}{\sigma }_{\min }({\mathrm{\Sigma }}^{1/2}){\parallel E{\mathrm{\Sigma }}^{1/2}\parallel }_F.$ (since ${\sigma }_{\min }(I+A)\ge 1-\parallel A\parallel$)

它遵循

${\parallel \nabla f(A)\parallel }_F^2$ $={\displaystyle \sum _{i=1}^{\mathrm{\ell }}}{\parallel {\displaystyle \frac{\partial f}{\partial A_i}}\parallel }_F^2\ge 4\mathrm{\ell }{(1-\tau )}^{2(\mathrm{\ell }-1)}{\sigma }_{\min }(\mathrm{\Sigma }){\parallel E{\mathrm{\Sigma }}^{1/2}\parallel }_F^2$

$=4\mathrm{\ell }{(1-\tau )}^{2(\mathrm{\ell }-1)}{\sigma }_{\min }(\mathrm{\Sigma })(f(A)-C)$ (by the definition of $E$ and Claim 2.3)

$\ge 4\mathrm{\ell }{(1-\tau )}^{2(\mathrm{\ell }-1)}{\sigma }_{\min }(\mathrm{\Sigma })(f(A)-C_{\text{opt}}).$

因此我们完成了方程的证明(2.3)。 最后，如果$A$是一个临界点，即$\nabla f(A)=0$，那么通过方程(2.3)我们可以得到$f(A)=C_{\text{opt}}$。 也就是说，$A$是全局最小值。 ∎

3 残差网络的表征能力

在本节中，我们描述残差网络的有限样本表达能力。 我们考虑具有单个 ReLU 激活且没有批量归一化的残差层。 基本残差构建块是一个函数 ${𝒯}_{U,V,s}(\cdot ):{ℝ}^k\to {ℝ}^k$，它由两个权重矩阵 $U\in {ℝ}^{k\times k},V\in {ℝ}^{k\times k}$ 和一个偏差向量 $s\in {ℝ}^k$ 参数化，

${𝒯}_{U,V,s}(h)=V\text{ReLu}(Uh+s).$ (3.1)

残差网络由一系列此类残差块组成。 与[7]中的完整预激活架构相比，我们在每个构建块中删除了两个批量归一化层和一个ReLU层。

我们假设数据具有 $r$ 标签，编码为 ${ℝ}^r$ 中的 $r$ 标准基向量，用 $e_1,\mathrm{\dots },e_r$ 表示。 我们有 $n$ 训练示例 $(x^{(1)},y^{(1)}),\mathrm{\dots },(x^{(n)},y^{(n)})$，其中 $x^{(i)}\in {ℝ}^d$ 表示第 $i$ 数据，$y^{(i)}\in \{e_1,\mathrm{\dots },e_r\}$ 表示 $i$-第一个标签。 不失一般性，我们假设数据已标准化，因此 $x^{(i)}=1.$ 我们还做出温和的假设，即没有两个数据点彼此非常接近。

Assumption 3.1.

我们假设对于每个 ，我们都有 ${\mathrm{\parallel }{x}^{\mathrm{(}i\mathrm{)}}\mathrm{-}{x}^{\mathrm{(}j\mathrm{)}}\mathrm{\parallel }}^{\mathrm{2}}\mathrm{\ge }\rho$ 对于某个绝对常数 $\rho \mathrm{>}\mathrm{0}\mathrm{.}$

例如，图像总是可以在像素空间中受到难以察觉的扰动，从而满足小但恒定的 $\rho .$ 的假设

在这个温和的假设下，我们证明只要参数数量是大于 $n$ 的对数因子，残差网络就有能力表达数据的任何可能的标签。

Theorem 3.2.

假设训练示例满足假设3.1。 然后，存在一个残差网络$N$（如下指定），其参数$O\mathit{}\mathrm{(}n\mathit{}\log \mathit{}n\mathrm{+}{r}^{\mathrm{2}}\mathrm{)}$完美地表达了训练数据，即对于所有$i\mathrm{\in }\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{\dots }\mathrm{,}n\mathrm{\}}\mathrm{,}$网络$N$ 将 $x^{\mathrm{(}i\mathrm{)}}$ 映射到 $y^{\mathrm{(}i\mathrm{)}}\mathrm{.}$

在实践中，$n>r^2,$ 很常见，例如 Imagenet 数据集的情况，其中 $n>{10}^6$ 和 $r=1000.$

我们使用等式 (3.1) 中定义的 ${𝒯}_{U,V,s}$ 形式的构建块构建以下残差网络。 该网络由$\mathrm{\ell }+1$隐藏层$h_0,\mathrm{\dots },h_{\mathrm{\ell }}$组成，输出由$\widehat{y}\in {ℝ}^r$表示。 第一层权重矩阵$A_0$将$d$维输入映射到$k$维隐藏变量$h_0$。 然后我们应用带有权重矩阵$A_j,B_j\in {ℝ}^{k\times k}$的构建块$𝒯$的$\mathrm{\ell }$层。 最后，我们应用另一个层将隐藏变量 $h_{\mathrm{\ell }}$ 映射到 ${ℝ}^k$ 中的标签 $\widehat{y}$。 从数学上来说，我们有

$h_0$ $=A_{0}x,$

$h_j$ $=h_{j-1}+{𝒯}_{A_j,B_j,b_j}(h_{j-1}),\forall j\in \{1,\mathrm{\dots },\mathrm{\ell }\}$

$\widehat{y}$ $={𝒯}_{A_{\mathrm{\ell }+1},B_{\mathrm{\ell }+1},s_{\mathrm{\ell }+1}}(h_{\mathrm{\ell }}).$

我们注意这里的$A_{\mathrm{\ell }+1}\in {ℝ}^{k\times r}$和$B_{\mathrm{\ell }+1}\in {ℝ}^{r\times r}$以便维度兼容。 我们假设标签数 $r$ 和输入维度 $d$ 都小于 $n$，这在实际应用中是安全的。 超参数 $k$ 将选择为 $O(\log n)$，层数选择为 $\mathrm{\ell }=\lceil n/k\rceil$。 因此，第一层具有 $dk$ 参数，中间的每个 $\mathrm{\ell }$ 构建块包含 $2k^2$ 参数，最终构建块具有 $kr+r^2$ 参数。 因此，参数总数为$O(kd+\mathrm{\ell }{k}^2+rk+r^2)=O(n\log n+r^2)$。

为了构建适合数据的上述形式的网络 $N$，我们首先采用一个随机矩阵 $A_0\in {ℝ}^{k\times d}$ 将所有数据点 $x^{(i)}$ 映射到向量 $h_0^{(i)}:=A_0{x}^{(i)}$。 这里我们将使用 $h_j^{(i)}$ 来表示第 $i$ 示例的第 $j$ 层隐藏变量。 根据 Johnson-Lindenstrauss 定理([10]，或参见 [17])，很有可能，结果向量 $h_0^{(i)}$ 仍然满足假设3.1（缩放比例略有不同，常数$\rho$较大），即任意两个向量$h_0^{(i)}$和$h_0^{(j)}$不是很相关的。

然后我们构造 $\mathrm{\ell }$ 中间层，将每个 $i\in \{1,\mathrm{\dots },n\}$ 的 $h_0^{(i)}$ 映射到 $h_{\mathrm{\ell }}^{(i)}$。 这些向量 $h_{\mathrm{\ell }}^{(i)}$ 将根据标签聚集到 $r$ 组中，尽管它们位于 ${ℝ}^k$ 中，而不是所需的 ${ℝ}^r$ 中。 具体来说，我们通过在${ℝ}^k$中挑选$r$随机单位向量$q_1,\mathrm{\dots },q_r$来设计这个聚类中心。 我们将它们视为维度 $k$ 中的代理标签向量（请注意，$k$ 可能比 $r$ 小得多）。 在高维度（技术上，如果$k>4\log r$)随机单位向量$q_1,\mathrm{\dots },q_r$与小于的内积成对不相关。 我们将第 $i$ 个示例与定义如下的目标代理标签向量 $v^{(i)}$ 相关联，

$\text{if}{y}^{(i)}=e_j,\text{then}{v}^{(i)}=q_j.$ (3.2)

然后，我们将构造矩阵 $(A_1,B_1),\mathrm{\dots },(A_{\mathrm{\ell }},B_{\mathrm{\ell }})$，以便网络的前 $\mathrm{\ell }$ 层将向量 $h_0^{(i)}$ 映射到代理标签向量 $v^{(i)}$。 从数学上讲，我们将构造 $(A_1,B_1),\mathrm{\dots },(A_{\mathrm{\ell }},B_{\mathrm{\ell }})$ 使得

$\forall i\in \{1,\mathrm{\dots },n\},h_{\mathrm{\ell }}^{(i)}=v^{(i)}.$ (3.3)

最后，我们将构造最后一层 ${𝒯}_{A_{\mathrm{\ell }+1},B_{\mathrm{\ell }+1},b_{\mathrm{\ell }+1}}$，以便它将向量 $q_1,\mathrm{\dots },q_r\in {ℝ}^k$ 映射到 $e_1,\mathrm{\dots },e_r\in {ℝ}^r$，

$\forall j\in \{1,\mathrm{\dots },r\},{𝒯}_{A_{\mathrm{\ell }+1},B_{\mathrm{\ell }+1},b_{\mathrm{\ell }+1}}(q_j)=e_j.$ (3.4)

将它们放在一起，通过定义 (3.2) 和方程 (3.3)，对于每个 $i$，如果标签为 $y^{(i)}$ 是 $e_j$，那么 $h_{\mathrm{\ell }}^{(i)}$ 将是 $q_j$。 然后通过方程(3.4)，我们得到${\widehat{y}}^{(i)}={𝒯}_{A_{\mathrm{\ell }+1},B_{\mathrm{\ell }+1},b_{\mathrm{\ell }+1}}(q_j)=e_j$。 因此我们得到${\widehat{y}}^{(i)}=y^{(i)}$。 该计划的关键部分是构建中间$\mathrm{\ell }$层权重矩阵，以便$h_{\mathrm{\ell }}^{(i)}=v^{(i)}$。 我们将其封装到以下非正式引理中。 正式声明和完整证明推迟到B节。

Lemma 3.3 （引理B.2的非正式版本）。

在上面的设置中，对于（几乎）任意向量 $h_{\mathrm{0}}^{\mathrm{(}\mathrm{1}\mathrm{)}}\mathrm{,}\mathrm{\dots }\mathrm{,}{h}_{\mathrm{0}}^{\mathrm{(}n\mathrm{)}}$ 和 $v^{\mathrm{(}\mathrm{1}\mathrm{)}}\mathrm{,}\mathrm{\dots }\mathrm{,}{v}^{\mathrm{(}n\mathrm{)}}\mathrm{\in }\mathrm{\{}{q}_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{q}_r\mathrm{\}}$，存在权重矩阵 $\mathrm{(}{A}_{\mathrm{1}}\mathrm{,}{B}_{\mathrm{1}}\mathrm{)}\mathrm{,}\mathrm{\dots }\mathrm{,}\mathrm{(}{A}_{\mathrm{\ell }}\mathrm{,}{B}_{\mathrm{\ell }}\mathrm{)}$，这样，

$\forall i\in \{1,\mathrm{\dots },n\},h_{\mathrm{\ell }}^{(i)}=v^{(i)}.$

我们简要地概述引理的证明以提供直觉，并将完整的证明推迟到 B 节。 每个残差块应用于隐藏变量的操作可以抽象地写为：

$\widehat{h}\to h+{𝒯}_{U,V,s}(h).$ (3.5)

其中 $h$ 对应于块之前的隐藏变量，$\widehat{h}$ 对应于块之后的隐藏变量。 我们声称，对于（几乎）任意的向量序列$h^{(1)},\mathrm{\dots },h^{(n)}$，存在${𝒯}_{U,V,s}(\cdot )$，使得操作(3.5)变换$k$ $h^{(i)}$ 的向量到我们可以自由选择的任意一组其他 $k$ 向量，并保持其余 $n-k$ 向量的值。 具体来说，对于任何大小为 $k$ 的子集 $S$ 和任何所需的向量 $v^{(i)}(i\in S)$，都存在 $U,V,s$ 使得

$v^{(i)}$ $=h^{(i)}+{𝒯}_{U,V,s}(h^{(i)})\forall i\in S$

$h^{(i)}$ $=h^{(i)}+{𝒯}_{U,V,s}(h^{(i)})\forall i\notin S$ (3.6)

该主张在引理 B.1 中得到了形式化。 我们可以重复使用它来构建 $\mathrm{\ell }$ 层构建块，每个构建块将 $\{h_0^{(1)},\mathrm{\dots },h_0^{(n)}\}$ 中的 $k$ 向量子集转换为 $\{v^{(1)},\mathrm{\dots },v^{(n)}\}$，并维护他人的价值观。 回想一下，我们有 $\mathrm{\ell }=\lceil n/k\rceil$ 层，因此在 $\mathrm{\ell }$ 层之后，所有向量 $h_0^{(i)}$ 都会转换为 $v^{(i)}$ 的，这完成校样草图。 ∎

4 全卷积残差网络的功效

受我们理论的启发，我们在标准图像分类基准上尝试了全卷积残差网络。

4.1 CIFAR10 和 CIFAR100

我们的 CIFAR10 和 CIFAR100 架构是相同的，除了最终维度分别对应于类 $10$ 和 $100$ 的数量。 在表 1 中，我们概述了我们的架构。 每个残差块的形式为$x+C_2(\mathrm{ReLU}(C_{1}x)),$，其中$C_1,C_2$是指定维度的卷积（内核宽度、内核高度、输入通道数、输出通道数） ）。 每个块中的第二个卷积始终具有步幅 $1$，而第一个卷积可能具有指定的步幅 $2$。 在变换不保持维度的情况下，原始输入 $x$ 使用平均池化和填充进行调整，这是残差层中的标准。

我们使用 Tensorflow 框架训练模型，使用动量优化器，动量为 $0.9,$，批量大小为 $128$。 所有卷积权重均通过权重衰减$0.0001.$进行训练 初始学习率为 $0.05,$，下降了 $10$、$30000$ 和 $50000$ 步长。 该模型在大约 $50k$ 步时达到峰值性能，在单个 NVIDIA Tesla K40 GPU 上大约需要 $24h$ 步。 我们的代码可以轻松地从开源实现 通过删除批量归一化，调整剩余组件和模型架构。 与代码的一个重要区别是，我们使用标准差 $\sigma =1/k^{2}c,$ 的随机正态初始化器来初始化内核大小 $k\times k$ 和 $c$ 输出通道的残差卷积层，而不是比用于标准卷积层的 $1/k\sqrt{c}$ 更好。 这种小得多的权重初始化有助于训练，同时不影响表示。

与标准模型的一个显着区别是最后一层没有经过训练，而只是一个固定的随机投影。 一方面，这稍微改善了测试误差（可能是由于正则化效应）。 另一方面，这意味着我们模型中唯一可训练的权重是卷积的权重，使我们的架构成为“全卷积”。

表格1： CIFAR10/100 的架构($55$ 卷积，$13.5$M 个参数）

variable dimensions	initial stride	description
$3\times 3\times 3\times 16$	$1$	1 standard conv
$3\times 3\times 16\times 64$	$1$	9 residual blocks
$3\times 3\times 64\times 128$	$2$	9 residual blocks
$3\times 3\times 128\times 256$	$2$	9 residual blocks
–	–	$8\times 8$ global average pool
$256\times \mathrm{𝚗𝚞𝚖}\mathrm{\_}\mathrm{𝚌𝚕𝚊𝚜𝚜𝚎𝚜}$	–	random projection (not trained)

我们模型的一个有趣的方面是，尽管其大小为 $13.59$ 万个可训练参数，但即使数据集大小为 $50000.$，模型似乎也不会过快过拟合。 相比之下，我们发现很难在 CIFAR10 上训练具有这种大小的批量归一化的模型而不会出现明显的过度拟合。

图1： CIFAR10（左）和 CIFAR (100)（右）最佳模型的收敛图。 第一步是批量大小 $128$ 的梯度更新。

表 2 总结了我们的模型与之前工作的非详尽列表相比的 top-$1$ 分类误差，仅限于 之前的最佳全卷积结果[ 15]，第一个残差结果[6]，以及[8]在CIFAR上的最新结果。 所有结果均采用标准数据增强。

表2： 不同基准上top-$1$分类误差的比较

Method	CIFAR10	CIFAR100	ImageNet	remarks
All-CNN	$7.25$	$32.39$	$41.2$	all-convolutional, dropout extra data processing
Ours	$6.38$	$24.64$	$35.29$	all-convolutional
ResNet	$6.43$	$25.16$	$19.38$
DenseNet	$3.74$	$19.25$	N/A

4.2ImageNet

ImageNet ILSVRC 2012 数据集具有 $1,281,167$ 个数据点和 $1000$ 类。 每个图像的大小都调整为具有 $3$ 通道的 $224\times 224$ 像素。 我们在 [6] 中尝试了 $34$ 层网络的全卷积变体。 原始模型实现了$25.03\%$分类错误。 我们的派生模型具有 $35.7M$ 可训练参数。 我们使用动量优化器（动量为 $0.9$）和学习率时间表对模型进行训练，学习率时间表从初始学习率 $0.1.$ 开始，每两个历时衰减 $0.94$ 倍。 训练分布在 $6$ 机器上，异步更新。 每台机器都配备了 $8$ GPU (NVIDIA Tesla K40)，并使用批量大小 $256$ 分割在 $8$ GPU 上，以便每个 GPU 更新的批量大小 $32.$

与 CIFAR10 和 CIFAR100 的情况相比，在 ImageNet 上，我们的全卷积模型的表现明显比其原始模型差。 具体来说，我们经历了大量的欠拟合，这表明较大的模型可能会表现更好。

尽管存在这个问题，我们的模型在测试集($50000$ 数据点）上仍然达到了 $35.29\%$ top-$1$ 分类错误，并且 $14.17\%$ top-$5$ 在 $700,000$ 步骤后测试训练错误（大约一周）。 虽然不再是最先进的，但这种性能明显优于 [13] 报告的 $40.7\%$ 以及 [15]。 我们相信，我们模型的更好的学习率计划和超参数设置很可能可以大大提高此处报告的初步性能。

5结论

我们的理论强调了训练深度人工神经网络时身份参数化的重要性。 一个突出的开放问题是将我们的优化结果扩展到非线性情况，其中每个残差都有一个 ReLU 激活，就像我们的表达结果一样。 我们推测类似于定理2.2的结果对于一般非线性情况是正确的。 与标准参数化不同，我们认为获得这样的结果没有根本障碍。

我们希望我们的理论和实验共同帮助简化深度学习的状态，旨在用一些基本原理来解释深度学习的成功，而不是需要巧妙组合的大量技巧。 我们相信，图像识别方面的大部分进步可以仅通过残差卷积层和 ReLU 激活来实现。 这可能会导致极其简单（尽管很深）的架构，与所有图像分类基准的最新技术相匹配。

致谢：我们感谢 Jason D. Lee、Qixing Huang 和 Jonathan Shewchuk 进行了有益的讨论，并善意地指出了本文早期版本中的错误。 我们还感谢 Jonathan Shewchuk 建议改进方程 (2.3)，并将其纳入当前版本。 马腾宇感谢Dodds Fellowship和Siebel奖学金的支持。

附录 A 第 2 部分缺少证明

在本节中，我们给出了定理2.1和引理2.4的完整证明，在2节中省略了它们。

A.1 定理证明2.1

事实证明，如果假设$R$是一个对称正半定（PSD）矩阵，或者如果我们允许变量是复矩阵，那么证明会容易得多。 这里我们首先给出第一个特殊情况的证明草图。 读者可以跳过它并跳转到下面的完整证明。 对于特殊情况，我们还将证明更强的结果，即 $\Vert \left|A^{\star }\right|\Vert \le 3\gamma /\mathrm{\ell }$。

当$R$是PSD时，它可以通过正交矩阵$U$进行对角化，在$R=UZ{U}^{\top }$的意义上，其中$Z=\mathrm{diag}(z_1,\mathrm{\dots },z_d)$是对角矩阵非负对角线条目$z_1,\mathrm{\dots },z_d$。 让$A_1^{\star }=\mathrm{\cdots }=A_{\mathrm{\ell }}^{\star }=U\mathrm{diag}(z_i^{1/\mathrm{\ell }})U^{\top }-I$，然后我们有

$(I+A_{\mathrm{\ell }}^{\star })\mathrm{\cdots }(I+A_1^{\star })$ $={(U\mathrm{diag}(z_i^{1/\mathrm{\ell }})U^{\top })}^{\mathrm{\ell }}=U\mathrm{diag}{(z_i^{1/\mathrm{\ell }})}^{\mathrm{\ell }}U$ (since $U^{\top }U=I$)

$=UZ{U}^{\top }=R.$

我们看到由 $A^{\star }$ 定义的网络重建了变换 $R$，因此它是总体风险的全局最小值（正式参见下面的声明 2.3)。 接下来，我们验证每个 $A_j^{\star }$ 具有较小的谱范数：

$\parallel A_j^{\star }\parallel$ $=\parallel I-U\mathrm{diag}(z_i^{1/\mathrm{\ell }})U^{\top })\parallel =\parallel U(I-\mathrm{diag}{(z_i)}^{1/\mathrm{\ell }})U^{\top }\parallel =\parallel I-\mathrm{diag}{(z_i)}^{1/\mathrm{\ell }}\parallel$ (since $U$ is orthonormal)

$=\underset{i}{\max }|z_i^{1/\mathrm{\ell }}-1|.$ (A.1)

从${\sigma }_{\min }(R)\le z_i\le {\sigma }_{\max }(R)$开始，我们有$\mathrm{\ell }\ge 3\gamma \ge |\log z_i|$。 它遵循

$|z_i^{1/\mathrm{\ell }}-1|=|e^{(\log z_i)/\mathrm{\ell }}-1|\le 3|(\log z_i)/\mathrm{\ell }|\le 3\gamma /\mathrm{\ell }.$ (since $|e^x-1|\le 3|x|$ for all $|x|\le 1$)

然后使用方程 (A.1) 和上面的方程，我们得到 $\Vert \left|A\right|\Vert \le {\max }_j\parallel A_j^{\star }\parallel \le 3\gamma /\mathrm{\ell }$，它完成了特殊情况的证明。

为了充分证明定理2.1，我们从以下声明开始：

Claim A.1.

假设 $Q\mathrm{\in }{ℝ}^{\mathrm{2}\mathrm{\times }\mathrm{2}}$ 是正交矩阵。 那么对于任意整数$q$，存在矩阵$W_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{W}_q\mathrm{\in }{ℝ}^{\mathrm{2}\mathrm{\times }\mathrm{2}}$和对角矩阵$\mathrm{\Lambda }$满足(a)$Q\mathrm{=}{W}_{\mathrm{1}}\mathit{}\mathrm{\dots }\mathit{}{W}_q\mathit{}\mathrm{\Lambda }$和$\mathrm{\parallel }{W}_j\mathrm{-}I\mathrm{\parallel }\mathrm{\le }\pi \mathrm{/}q$，(b) $\mathrm{\Lambda }$ 是一个对角矩阵，对角线上有 $\mathrm{\pm }\mathrm{1}$，并且 (c) 如果 $Q$ 是旋转，则 $\mathrm{\Lambda }\mathrm{=}I$.

证明。

我们首先考虑$Q$是旋转的情况。 每个旋转矩阵可以写为。 假设$Q=T(\theta )$。 然后我们可以取$W_1=\mathrm{\cdots }=W_q=T(\theta /q)$和$\mathrm{\Lambda }=I$。 我们可以验证

$\parallel W_j-I\parallel \le \theta /q.$

接下来，我们考虑 $Q$ 是反射的情况。 那么我们可以将 $Q$ 写为 $Q=T(\theta )\cdot \mathrm{diag}(-1,1)$，其中 $\mathrm{diag}(-1,1)$ 是相对于 $y$ 轴的反射。 然后我们就可以取$W_1=\mathrm{\cdots }=W_q=T(\theta /q)$和$\mathrm{\Lambda }=\mathrm{diag}(-1,1)$来完成证明。 ∎

接下来给出定理2.1的正式完整证明。 主要思想是减少块对角线情况并应用上述权利要求。

定理证明2.1。

令 $R=UK{V}^{\top }$ 为 $R$ 的奇异值分解，其中 $U$、$V$ 为两个正交矩阵，$K$是对角线上具有非负项的对角矩阵。 由于$det(R)=det(U)det(K)det(V)>0$和$det(K)>0$，我们可以适当翻转$U,V$，以便$det(U)=det(V)=1$。 由于 $U$ 是一个正矩阵（即 $U$ 满足 $U{U}^{\top }=U^{\top }U$），根据权利要求 C.1，我们可以将 $U$ 通过正交矩阵 $S$ 分块对角化为 $U=SD{S}^{-1}$，其中 $D=\mathrm{diag}(D_1,\mathrm{\dots },D_m)$ 是一个实数分块对角矩阵，每个分块 $D_i$ 的大小最多为 $2\times 2$。 使用声明A.1，我们可以得出对于任何$D_i$，都存在$W_{i,1},\mathrm{\dots },W_{i,q},{\mathrm{\Lambda }}_i$，使得

$D_i=W_{i,1}\mathrm{\dots }{W}_{i,q}{\mathrm{\Lambda }}_i$ (A.2)

和$\parallel W_{i,j}-I\parallel \le \pi /q$。 让 $\mathrm{\Lambda }=\mathrm{diag}({\mathrm{\Lambda }}_1,\mathrm{\dots },{\mathrm{\Lambda }}_m)$ 和 $W_j=\mathrm{diag}(W_{1,j},\mathrm{\dots }{W}_{m,j})$。 我们可以将方程 (A.2) 重写为

$D=W_1\mathrm{\dots }{W}_q\mathrm{\Lambda }.$ (A.3)

此外，我们有 $\mathrm{\Lambda }$ 是一个对角矩阵，对角线上有 $\pm 1$。 由于 $W_{i,j}$ 是行列式为 1 的正交矩阵，因此我们有 $det(\mathrm{\Lambda })=det(D)=det(U)=1$。 也就是说，$\mathrm{\Lambda }$ 在对角线上有偶数个 $-1$。 然后我们可以将 $-1$ 分组为 $2\times 2$ 块。 请注意， 是旋转矩阵$T(\pi )$。 因此，我们可以将 $\mathrm{\Lambda }$ 写为对角线上的 $+1$ 和块 $T(\pi )$ 的串联。 然后应用声明A.1（在每个块$T(\pi )$上），我们得到$W_1^{\prime },\mathrm{\dots },W_q^{\prime }$使得

$\mathrm{\Lambda }=W_1^{\prime }\mathrm{\dots }{W}_q^{\prime }$ (A.4)

其中$\parallel W_j^{\prime }-I\parallel \le \pi /q$。 因此，使用方程 (A.3) 和 (2.3)，我们得到

$U=SD{S}^{-1}=S{W}_1{S}^{-1}\mathrm{\cdots }S{W}_q{S}^{-1}\cdot S{W}_1^{\prime }{S}^{-1}\mathrm{\cdots }S{W}_q^{\prime }{S}^{-1}.$

此外，对于每个 $j$、$\parallel S{W}_j{S}^{-1}-I\parallel =\parallel S(W_j-I)S^{-1}\parallel =\parallel W_j-I\parallel \le \pi /q$，我们都有它，因为 $S$ 是正交矩阵。 对于$W_j^{\prime }$也可以证明同样的道理。 因此让 $B_j=S{W}_j{S}^{-1}-I$ 代表 $j\le q$ 和 $B_{j+q}=S{W}_j^{\prime }{S}^{-1}-I$，我们可以重写，

$U=(I+B_1)\mathrm{\dots }(I+B_q).$

我们可以通过将 $V$ 分解为 $2q$ 矩阵（与单位矩阵 $\pi /q$ 接近）来类似地处理 $V$，

$V^{\top }=(I+B_1^{\prime })\mathrm{\dots }(I+B_{2q}^{\prime }).$

最后，我们处理对角矩阵$K$。让$K=\mathrm{diag}(k_i)$。 我们有$\min k_i={\sigma }_{\min }(R),\max k_i={\sigma }_{\max }(R)$。 然后，我们可以写$K={(K^{\prime })}^p$，其中$K^{\prime }=\mathrm{diag}(k_i^{1/p})$和$p$是稍后选择的整数。 我们有 $\parallel K^{\prime }-I\parallel \le \max |k_i^{1/p}-1|\le \max |e^{\log k_i\cdot 1/p}-1|$。 当 $p\ge \gamma =\max \{\log \max k_i,-\log \min k_i\}=\max \{\log {\sigma }_{\max }(R),-\log {\sigma }_{\min }(R)\}$ 时，我们有

$\parallel K^{\prime }-I\parallel \le \max |e^{\log k_i\cdot 1/p}-1|\le 3\max |\log k_i\cdot 1/p|=3\gamma /p.$ (since $|e^x-1|\le 3|x|$ for $|x|\le 1$)

让$B_1^{\prime \prime }=\mathrm{\cdots }=B_p^{\prime \prime }=K^{\prime }-I$，然后我们有$K=(I+B_p^{\prime \prime })\mathrm{\cdots }(I+B_1^{\prime \prime })$。 最后，我们选择$p=\frac{3\gamma \mathrm{\ell }}{4\pi +3\gamma }$和$q=\frac{\pi \mathrm{\ell }}{4\pi +3\gamma }$， 并让$A_{p+4q}=B_{2q},\mathrm{\cdots }=A_{p+2q+1}=B_1,A_{p+2q}=B_p^{\prime \prime },\mathrm{\dots },A_{2q+1}=B_1^{\prime \prime },A_{2q}=B_{2q}^{\prime },\mathrm{\dots },A_1=B_1^{\prime }$。 我们有 $4q+p=\mathrm{\ell }$ 和

$R=UK{V}^{\top }=(I+A_{\mathrm{\ell }})\mathrm{\dots }(I+A_1).$

此外，根据需要，我们还有 $\left|\right|\left|A\right|\left|\right|\le \max \{\parallel B_j\parallel ,\parallel B_j^{\prime }\parallel .\parallel B_j^{\prime \prime }\parallel \}\le \max \{\pi /q,3\gamma /p\}\le \frac{4\pi +3\gamma }{\mathrm{\ell }}$。 ∎

A.2 引理证明2.4

我们根据定义计算部分梯度。 令 ${\mathrm{\Delta }}_j\in {ℝ}^{d\times d}$ 为 $A_j$ 的无穷小变化。 使用声明 2.3，考虑 $f(A_1,\mathrm{\dots },A_{\mathrm{\ell }}+{\mathrm{\Delta }}_j,\mathrm{\dots },A_{\mathrm{\ell }})$ 的泰勒展开式

$f(A_1,\mathrm{\dots },A_{\mathrm{\ell }}+{\mathrm{\Delta }}_j,\mathrm{\dots },A_{\mathrm{\ell }})$

$={\parallel ((I+A_{\mathrm{\ell }})\mathrm{\cdots }(I+A_j+{\mathrm{\Delta }}_j)\mathrm{\dots }(I+A_1)-R){\mathrm{\Sigma }}^{1/2}\parallel }_F^2$

$={\parallel ((I+A_{\mathrm{\ell }})\mathrm{\cdots }(I+A_1)-R){\mathrm{\Sigma }}^{1/2}+(I+A_{\mathrm{\ell }})\mathrm{\cdots }{\mathrm{\Delta }}_j\mathrm{\dots }(I+A_1){\mathrm{\Sigma }}^{1/2}\parallel }_F^2$

$={\parallel ((I+A_{\mathrm{\ell }})\mathrm{\cdots }(I+A_1)-R){\mathrm{\Sigma }}^{1/2}\parallel }_F^2+$

$2⟨((I+A_{\mathrm{\ell }})\mathrm{\cdots }(I+A_1)-R){\mathrm{\Sigma }}^{1/2},(I+A_{\mathrm{\ell }})\mathrm{\cdots }{\mathrm{\Delta }}_j\mathrm{\dots }(I+A_1){\mathrm{\Sigma }}^{1/2}⟩+O({\parallel {\mathrm{\Delta }}_j\parallel }_F^2)$

$=f(A)+2⟨(I+A_{j+1}^{\top })\mathrm{\dots }(I+A_{\mathrm{\ell }}^{\top })E\mathrm{\Sigma }(I+A_1^{\top })\mathrm{\dots }(I+A_{j-1}^{\top }),{\mathrm{\Delta }}_j⟩+O({\parallel {\mathrm{\Delta }}_j\parallel }_F^2).$

根据定义，这意味着 $\frac{\partial f}{\partial A_j}=2(I+A_{\mathrm{\ell }}^{\top })\mathrm{\dots }(I+A_{j+1}^{\top })E\mathrm{\Sigma }(I+A_{j-1}^{\top })\mathrm{\dots }(I+A_1^{\top })$。 ∎

附录B第3部分缺少证明

在本节中，我们提供定理3.2的完整证明。 我们从以下引理开始，构建一个构建块 $𝒯$，将任意 $n$ 向量序列的 $k$ 向量转换为任意向量集，并且 main他人的价值。 为了更好的抽象，我们使用 ${\alpha }^{(i)}$,${\beta }^{(i)}$ 来表示向量序列。

Lemma B.1.

令 $S\mathrm{\subset }\mathrm{[}n\mathrm{]}$ 的大小为 $k$。假设 ${\alpha }^{\mathrm{(}\mathrm{1}\mathrm{)}}\mathrm{,}\mathrm{\dots }\mathrm{,}{\alpha }^{\mathrm{(}n\mathrm{)}}$ 是 $n$ 向量的序列，对于每个 $\mathrm{1}\mathrm{\le }i\mathrm{\le }n$ 满足 a)，我们有 $\mathrm{1}\mathrm{-}{\rho }^{\mathrm{\prime }}\mathrm{\le }{\mathrm{\parallel }{\alpha }_i\mathrm{\parallel }}^{\mathrm{2}}\mathrm{\le }\mathrm{1}\mathrm{+}{\rho }^{\mathrm{\prime }}$，并且 b) 如果 $i\mathrm{\ne }j$ 和 $S$ 至少包含 $i\mathrm{,}j$ 之一，然后是 $\mathrm{\parallel }{\alpha }^{\mathrm{(}i\mathrm{)}}\mathrm{-}{\alpha }^{\mathrm{(}j\mathrm{)}}\mathrm{\parallel }\mathrm{\ge }\mathrm{3}\mathit{}{\rho }^{\mathrm{\prime }}$。 令 ${\beta }^{\mathrm{(}\mathrm{1}\mathrm{)}}\mathrm{,}\mathrm{\dots }\mathrm{,}{\beta }^{\mathrm{(}n\mathrm{)}}$ 为任意向量序列。 那么，存在$U\mathrm{,}V\mathrm{\in }{ℝ}^{k\mathrm{\times }k}\mathrm{,}s$，这样对于每个$i\mathrm{\in }S$，我们有${𝒯}_{U\mathrm{,}V\mathrm{,}s}\mathit{}\mathrm{(}{\alpha }^{\mathrm{(}i\mathrm{)}}\mathrm{)}\mathrm{=}{\beta }^{\mathrm{(}i\mathrm{)}}\mathrm{-}{\alpha }^{\mathrm{(}i\mathrm{)}}$，此外，对于每个$i\mathrm{\in }\mathrm{[}n\mathrm{]}\mathrm{\backslash }S$，我们有${𝒯}_{U\mathrm{,}V\mathrm{,}s}\mathit{}\mathrm{(}{\alpha }^{\mathrm{(}i\mathrm{)}}\mathrm{)}\mathrm{=}\mathrm{0}$。

我们可以看出结论意味着

${\beta }^{(i)}$ $={\alpha }^{(i)}+{𝒯}_{U,V,s}({\alpha }^{(i)})\forall i\in S$

${\alpha }^{(i)}$ $={\alpha }^{(i)}+{𝒯}_{U,V,s}({\alpha }^{(i)})\forall i\notin S$

这是方程 (3.6) 的另一种写法。

引理B.1的证明。

不失一般性，假设$S=\{1,\mathrm{\dots },k\}$。 我们构造 $U,V,s$ 如下。 令 $U$ 的第 $i$ 行为 $i\in [k]$ 的 ${\alpha }^{(i)}$，并令 $s=-(1-2{\rho }^{\prime })\cdot \mathrm{𝟏}$ 其中 $\mathrm{𝟏}$表示全1的向量。 令 $V$ 的 $i$ 列为 $i\in [k]$ 的 $\frac{1}{{\parallel {\alpha }^{(i)}\parallel }^2-(1-2{\rho }^{\prime })}({\beta }^{(i)}-{\alpha }^{(i)})$。 接下来我们验证一下构造的正确性。 我们首先考虑$1\le i\le k$。 我们知道 $U{\alpha }^{(i)}$ 是一个向量，其 $i$ 坐标等于 ${\parallel {\alpha }^{(i)}\parallel }^2\ge 1-{\rho }^{\prime }$。 $U{\alpha }^{(i)}$ 的第 $j$ 坐标等于 $⟨{\alpha }^{(j)},{\alpha }^{(i)}⟩$，可以使用引理假设将其上限设置为

$⟨{\alpha }^{(j)},{\alpha }^{(i)}⟩={\displaystyle \frac{1}{2}}\left({\parallel {\alpha }^{(i)}\parallel }^2+{\parallel {\alpha }^{(j)}\parallel }^2\right)-{\parallel {\alpha }^{(i)}-{\alpha }^{(j)}\parallel }^2\le 1+{\rho }^{\prime }-3{\rho }^{\prime }\le 1-2{\rho }^{\prime }.$ (B.1)

因此，这意味着 $U{\alpha }^{(i)}-(1-2{\rho }^{\prime })\cdot \mathrm{𝟏}$ 包含单个正条目（其值至少为 ${\parallel {\alpha }^{(i)}\parallel }^2-(1-2{\rho }^{\prime })\ge {\rho }^{\prime }$)，而所有其他条目均为非正条目。 这意味着 $\text{ReLu}(U{\alpha }^{(i)}+b)=\left({\parallel {\alpha }^{(i)}\parallel }^2-(1-2{\rho }^{\prime })\right)e_i$ 其中 $e_i$ 是第 $i$ 个自然基向量。 由此可见$V\text{ReLu}(U{\alpha }^{(i)}+b)=({\parallel {\alpha }^{(i)}\parallel }^2-(1-2{\rho }^{\prime }))V{e}_i={\beta }^{(i)}-{\alpha }^{(i)}$。 最后，考虑$n\ge i>k$。那么与式(B.1)中的计算类似，$U{\alpha }^{(i)}$是所有坐标都小于$1-2{\rho }^{\prime }$的向量。 因此 $U{\alpha }^{(i)}+b$ 是一个具有负项的向量。 因此我们有 $\text{ReLu}(U{\alpha }^{(i)}+b)=0$，这意味着 $V\text{ReLu}(U{\alpha }^{(i)}+b)=0$。 ∎

现在我们准备好声明引理 3.3 的正式版本。

Lemma B.2.

假设 $n$ 向量 $z^{\mathrm{(}\mathrm{1}\mathrm{)}}\mathrm{,}\mathrm{\dots }\mathrm{,}{z}^{\mathrm{(}n\mathrm{)}}$ 的序列满足假设 3.1 的宽松版本：a) 对于每个 $i$,$\mathrm{1}\mathrm{-}{\rho }^{\mathrm{\prime }}\mathrm{\le }{\mathrm{\parallel }{z}^{\mathrm{(}i\mathrm{)}}\mathrm{\parallel }}^{\mathrm{2}}\mathrm{\le }\mathrm{1}\mathrm{+}{\rho }^{\mathrm{\prime }}$ b) 对于每个 $i\mathrm{\ne }j$，我​​们有 ${\mathrm{\parallel }{z}^{\mathrm{(}i\mathrm{)}}\mathrm{-}{z}^{\mathrm{(}j\mathrm{)}}\mathrm{\parallel }}^{\mathrm{2}}\mathrm{\ge }{\rho }^{\mathrm{\prime }}\mathrm{;}$。 让 $v^{\mathrm{(}\mathrm{1}\mathrm{)}}\mathrm{,}\mathrm{\dots }\mathrm{,}{v}^{\mathrm{(}n\mathrm{)}}$ 被定义在上面。 然后存在权重矩阵$\mathrm{(}{A}_{\mathrm{1}}\mathrm{,}{B}_{\mathrm{1}}\mathrm{)}\mathrm{,}\mathrm{\dots }\mathrm{,}\mathrm{(}{A}_{\mathrm{\ell }}\mathrm{,}{B}_{\mathrm{\ell }}\mathrm{)}$，这样给定$\mathrm{\forall }i\mathrm{,}{h}_{\mathrm{0}}^{\mathrm{(}i\mathrm{)}}\mathrm{=}{z}^{\mathrm{(}i\mathrm{)}}$，我们有，

$\forall i\in \{1,\mathrm{\dots },n\},h_{\mathrm{\ell }}^{(i)}=v^{(i)}.$

我们将重复使用引理B.1来构造积木${𝒯}_{A_j,B_k,s_j}(\cdot )$，从而证明引理B.2。 每个构建块 ${𝒯}_{A_j,B_k,s_j}(\cdot )$ 获取 $\{z^{(1)},\mathrm{\dots },z^{(n)}\}$ 中 $k$ 向量的子集，并将它们转换为 $v^{(i)}$ 的，同时将所有其他向量保持为固定的。 由于它们完全是 $n/k$ 层，因此我们最终将所有 $z^{(i)}$ 映射到目标向量 $v^{(i)}$。

引理B.2的证明。

我们重复使用引理B.1。 让$S_1=[1,\mathrm{\dots },k]$。 然后使用引理B.1与${\alpha }^{(i)}=z^{(i)}$和${\beta }^{(i)}=v^{(i)}$对于$i\in [n]$，我们得到存在$A_1,B_1,b_1$这样对于$i\le k$，它保持$h_1^{(i)}=z^{(i)}+{𝒯}_{A_1,B_1,b_1}(z^{(i)})=v^{(i)}$，对于$i\ge k$，它保持$h_1^{(i)}=z^{(i)}+{𝒯}_{A_1,B_1,b_1}(z^{(i)})=z^{(i)}$。 现在我们归纳构建其他层。 我们将构建这样的图层：图层 $j$ 的隐藏变量满足 $h_j^{(i)}=v^{(i)}$ 中的每一个 $1\le i\le jk$，以及 $h_j^{(i)}=z^{(i)}$ 中的每一个 $n\ge i>jk$。 假设我们已经构造了第一个 $j$ 层，接下来我们使用引理 B.1 构造 $j+1$ 层。 然后我们认为${\alpha }^{(1)}=v^{(1)},\mathrm{\dots },{\alpha }^{(jk)}=v^{(jk)}$、${\alpha }^{(jk+1)}=z^{(jk+1)},\mathrm{\dots },{\alpha }^{(n)}=z^{(n)}$和$S=\{jk+1,\mathrm{\dots },(j+1)k\}$的选择满足引理B.1的假设。 事实上，因为 $q_i$ 是均匀随机选择的，所以我们对每个 $s$ 和 $i$、$⟨q_s,z^{(i)}⟩\le 1-{\rho }^{\prime }$ 都有 w.h.p。 因此，从 $v^{(i)}\in \{q_1,\mathrm{\dots },q_r\}$ 开始，我们就知道 $v^{(i)}$ 也与任何 $z^{(i)}$ 都不相关。 然后我们应用引理B.1并得出结论，存在$A_{j+1}=U,B_{j+1}=V,b_{j+1}=s$使得${𝒯}_{A_{j+1},b_{j+1},b_{j+1}}(v^{(i)})=0$对于$i\le jk$,${𝒯}_{A_{j+1},b_{j+1},b_{j+1}}(z^{(i)})=v^{(i)}-z^{(i)}$ 代表 ,${𝒯}_{A_{j+1},b_{j+1},b_{j+1}}(z^{(i)})=0$ 代表 $n\ge i>(j+1)k$。这些意味着

$h_{j+1}^{{}^{(i)}}$ $=h_j^{(i)}+{𝒯}_{A_{j+1},b_{j+1},b_{j+1}}(v^{(i)})=v^{(i)}\forall 1\le i\le jk$

$h_{j+1}^{{}^{(i)}}$ $=h_j^{(i)}+{𝒯}_{A_{j+1},b_{j+1},b_{j+1}}(z^{(i)})=v^{(i)}\forall jk+1\le i\le (j+1)k$

$h_{j+1}^{{}^{(i)}}$

因此，我们构建了满足层 $j+1$ 归纳假设的 $j+1$ 层。 因此，通过归纳我们得到了所有层，最后一层对于每个示例$i$都满足$h_{\mathrm{\ell }}^{(i)}=v^{(i)}$。 ∎

现在我们准备按照3节中概述的总体计划证明定理3.2。

定理证明3.2。

我们使用形式化下面讨论的直觉定理3.2。 First, take $k=c(\log n)/{\rho }^2$ for sufficiently large absolute constant $c$ (for example, $c=10$ works), by Johnson-Lindenstrauss Theorem ([10], or see [17]) we have that when $A_0$ is a random matrix with standard normal entires, with high probability, all the pairwise distance between the the set of vectors $\{0,x^{(1)},\mathrm{\dots },x^{(n)}\}$ are preserved up to $1\pm \rho /3$ factor. 也就是说，我们对每个 $i$、$1-\rho /3\le \parallel A_0{x}^{(i)}\parallel \le 1+\rho /3$ 和每个 $i\ne j$、$\parallel A_0{x}^{(i)}-A_0{x}^{(j)}\parallel \ge \rho (1-\rho /3)\ge 2\rho /3$ 都有它。 让 $z^{(i)}=A_0{x}^{(i)}$ 和 ${\rho }^{\prime }=\rho /3$。 那么我们就有 $z^{(i)}$ 满足 Lemam B.2 的条件。 我们在${ℝ}^k$中选择$r$个随机向量$q_1,\mathrm{\dots },q_r$。 让$v^{(1)},\mathrm{\dots },v^{(n)}$定义为等式(3.2)。 然后通过引理 B.2，我们可以构造矩阵 $(A_1,B_1),\mathrm{\dots },(A_{\mathrm{\ell }},B_{\mathrm{\ell }})$ 使得

$h_{\mathrm{\ell }}^{(i)}=v^{(i)}.$ (B.2)

请注意，$v^{(i)}\in \{q_1,\mathrm{\dots },q_r\}$ 和 $q_i$ 是随机单位向量。 因此，选择${\alpha }^{(1)}=q_1,\mathrm{\dots },{\alpha }^{(r)}=q_r$、${\beta }^{(1)}=e_1,\mathrm{\dots },{\beta }^{(r)}=e_r$，并且满足引理B.1的条件，并使用引理B.1 我们得出结论，存在 $A_{\mathrm{\ell }+1},B_{\mathrm{\ell }+1},s_{\mathrm{\ell }+1}$ 使得

$e_j={𝒯}_{A_{\mathrm{\ell }+1},B_{\mathrm{\ell }+1},b_{\mathrm{\ell }+1}}(v_j),\text{for every}j\in \{1,\mathrm{\dots },r\}..$ (B.3)

根据方程(3.2)和方程(B.2)中$v^{(i)}$的定义，我们得出${\widehat{y}}^{(i)}=h_{\mathrm{\ell }}^{(i)}+{𝒯}_{A_{\mathrm{\ell }+1},B_{\mathrm{\ell }+1},b_{\mathrm{\ell }+1}}(h_{\mathrm{\ell }}^{(i)})=y^{(i)}.$，其中完成证明。 ∎

附录C工具箱

在本节中，我们将陈述两个民间传说的线性代数陈述。 下面的声明应该是已知的，但我们在文献中找不到它。 为了完整性，我们在这里提供证明。

Claim C.1。

令$U\mathrm{\in }{ℝ}^{d\mathrm{\times }d}$为实数正规矩阵（即满足$U\mathit{}{U}^{\mathrm{\top }}\mathrm{=}{U}^{\mathrm{\top }}\mathit{}U$)。 那么，存在一个正交矩阵 $S\mathrm{\in }{ℝ}^{d\mathrm{\times }d}$ 使得

$U=SD{S}^{\top },$

其中$D$是一个真正的块对角矩阵，由大小最多为$\mathrm{2}\mathrm{\times }\mathrm{2}$的块组成。

证明。

由于 $U$ 是正规矩阵，因此它可酉对角化（有关背景，请参阅 [16])。 因此，${ℂ}^{d\times d}$中存在酉矩阵$V$,${ℂ}^{d\times d}$中存在对角矩阵，使得$U$具有特征分解$U=V\mathrm{\Lambda }{V}^{*}$。 由于 $U$ 本身是一个实数矩阵，因此特征值($\mathrm{\Lambda }$ 的对角线条目）以共轭对的形式出现，特征向量($V$)。 也就是说，我们可以将$V$的列分组为$(v_1,{\overline{v}}_1),\mathrm{\dots },(v_s,\overline{v_s}),v_{s+1},\mathrm{\dots },v_t$对，并令相应的特征值为${\lambda }_1,{\overline{\lambda }}_1,\mathrm{\dots },{\lambda }_{{\lambda }_s},{\overline{\lambda }}_s,{\lambda }_{s+1},\mathrm{\dots },{\lambda }_t$。 这里${\lambda }_{s+1},\mathrm{\dots },{\lambda }_t\in ℝ$。 然后我们就得到了$U={\sum }_{i=1}^{s}2\mathrm{\Re }(v_i{\lambda }_i{v}_i^{*})+{\sum }_{i=s+1}^t{v}_i{\lambda }_i{v}_i^{\top }$。 令$Q_i=\mathrm{\Re }(v_i{\lambda }_i{v}_i^{*})$，则我们有$Q_i$是一个2阶实数矩阵。 令 $S_i\in {ℝ}^{d\times 2}$ 为 $Q_i$ 列跨度的正交基，然后我们可以将 $Q_i$ 写为 $Q_i=S_i{D}_i{S}_i^{\top }$，其中 $D_i$ 是一个 $2\times 2$ 矩阵。 最后让$S=[S_1,\mathrm{\dots },S_s,v_{s+1},\mathrm{\dots },v_t]$和$D=\mathrm{diag}(D_1,\mathrm{\dots },D_s,{\lambda }_{s+1},\mathrm{\dots },{\lambda }_t)$我们完成证明。 ∎

下面的权利要求用于证明定理2.2。 我们在这里提供完整性证明。

Claim C.2 （民间传说）。

对于任意两个矩阵 $A\mathrm{,}B\mathrm{\in }{ℝ}^{d\mathrm{\times }d}$，我们有

${\parallel AB\parallel }_F\ge {\sigma }_{\min }(A){\parallel B\parallel }_F.$

证明。

由于 ${\sigma }_{\min }{(A)}^2$ 是 $A^{\top }A$ 的最小特征值，因此我们有

$B^{\top }{A}^{\top }AB⪰B^{\top }\cdot {\sigma }_{\min }{(A)}^{2}I\cdot B.$

因此，可以得出

${\parallel AB\parallel }_F^2$ $=\text{tr}(B^{\top }{A}^{\top }AB)\ge \text{tr}(B^{\top }\cdot {\sigma }_{\min }{(A)}^{2}I\cdot B)$

$={\sigma }_{\min }{(A)}^2\text{tr}(B^{\top }B)={\sigma }_{\min }{(A)}^2{\parallel B\parallel }_F^2.$

两边取平方根完成证明。 ∎