论文阅读：Sharp Representation Theorems for ReLU Networkswith Precise Dependence on Depth

原文链接：https://arxiv.org/pdf/2006.04048.pdf

摘要

对于本文定义的一类函数G_D，我们证明了具有D ReLU层的神经网络在平方损耗下的清晰无维表示结果。这些结果在以下意义上准确地反映了深度的好处：

这构成了对任意深度D和神经元数量N的前馈网络的表示能力的细粒度表征，而现有的表示结果要么要求D随N快速增长，要么假设所表示的函数非常平滑。在后一种情况下，可以用单个非线性层获得相似的速率。我们的结果证实了普遍的假设，深层网络更好地表示不太平滑的函数，实际上，主要的技术创新是充分利用了深层网络可以产生具有少量激活函数的高度振荡函数这一事实。

1 Introduction

深度神经网络是现代机器学习的主力。一个重要的原因是深层网络的普遍近似性质，它允许它们以任意精度表示任何连续实值函数。各种表示定理，建立了神经网络的普遍逼近性质[2,3,4,5,6]。在函数的正则性条件下，一条长工作线给出了神经元数量的近似率[7,8,9,10,11,12,13,14,15,16]。到目前为止，单个非线性层的情况已经很好地理解了，而相应的理论深度网络是缺乏的。

经验表明，深层网络的表现明显优于浅层网络，大量理论论文旨在理解这一点。例如，[17]表明，让深度随着样本数量的增加而增加，对于非参数回归任务来说，会给出最大最小的最优错误率。[18]考虑了深度网络中的分层学习，其中SGD训练产生的层依次构建更复杂的特征来表示功能。虽然理解基于数据训练的神经网络的泛化性能是一个难题，基于网络的表达能力决定了任意优化程序下的基本障碍的逻辑，在这篇论文中，我们关注更基本的表示问题。

一组关于深度分离的研究试图通过构造函数来深入了解深度的好处，这些函数可以被一定深度的网络有效地表示，但不能被较浅的网络表示，除非它们的宽度非常大 [19, 20, 12, 21, 22, 23, 24, 25]。例如，[23]表明径向函数的存在，它可以很容易地用两个非线性层逼近，但不能用一个非线性层逼近，[24]表明了振荡函数的存在性，它可以很容易地用具有D³非线性层的网络逼近，但不能用由D非线性层组成的2^D宽度网络来近似。[26, 27]利用动力系统的思想扩展这些结果，并获得深度宽度的权衡。在用和积网络表示概率分布的不同设置中，[28]显示了较强的D与D+1分离结果。所有这些结果都表明存在一个需要一定深度的函数，但并没有试图刻画由给定深度的网络逼近的一类函数。

对于单层具有N个非线性单元的神经网络，通过大数型参数定律得到的经典结果产生了1/N的平方损耗衰减率[7,8]。几篇论文提出了增加深度的好处[9,10,12,13]，通过实现泰勒级数近似来表明深度ReLU或RePU神经网络可以实现比1/N更快的速率,当所表示的函数非常平滑且允许深度随着损失趋于0而增长时。然而，最近在[16]中显示，当这种额外的平滑是假设的，一个单一的非线性层足以达到相似的误差衰减率。因此，这些结果并没有体现出深度的好处。

与我们最相关的工作是[14]，它考虑在sup范数下给定连续模的函数表示。当深度D与激活函数总数N成线性关系时，误差衰减率严格优于D不变时的误差衰减率。这表明深度在网络表达能力中是有利的，但是，速率是量纲相关的，因此，结果远不能清晰地描述深度的确切好处，这一点将变得很清楚。

在本文中，我们对深度在ReLU网络表示能力中的作用进行了细粒度表征。给定一个具有D个ReLU层和输入维数d的网络，我们定义了一类以其傅里叶变换衰减为特征的实值函数G_D,类似于经典作品中所考虑的类，如[7]。随着D的增加，傅里叶变换的尾部被允许变得更宽，从而捕获更广泛的函数类.请注意，众所周知，函数的傅里叶变换的衰减与它的光滑性有关(c.f.，[29])。我们在第4节中所述的结果表明，在D层中具有N个ReLU单元的网络可以实现G_D类函数的N阶速率，而具有D^’<D个ReLU层的网络必须具有较慢的N^-D’/D阶速率。所有这些速率在常数因素下都是最优的。如第3节所述，我们通过利用深层网络的组成结构系统地产生浅层网络难以产生的高振荡函数来证明这些结果。

组织。本文组织如下。在第2节中，我们介绍了符号并定义了问题。在第3节中，我们概述了结论背后的主要思想，然后在第4节中正式陈述。第5、6和7节证明了这些结果。

2 Notation, Problem Setup, and Fourier Norms

2符号、问题设置和傅里叶范数
D:ReLU层的数量
d:输入维数,d₁=d,d₁=n_i-1(i $\ge$ 2)
e_j:标准基向量

我们想知道在深度为D的神经网络中，有多少个ReLU单元是必要的和充分的，使其输出f的平方损耗为:


定义域R^d通常是隐式的，但为了清晰起见，我们偶尔也写GK(R^d)或GK( R)。由于傅里叶变换的衰减与函数的光滑性有关，函数空间序列(G_K)随着K的增加而增加光滑性较差的函数。很难准确地描述这类函数，但我们注意到，对于Bd?之外的所有K足够大(通过与合适的凹凸函数相乘)，当修改到衰变为0时，GK中包含了各种函数类。这些包括多项式、三角多项式(对于所有K $\ge$ 1)和任意深度的任何ReLU网络(当K $\ge$ 2时)。

3 Using Depth to Improve Representation

在下一节中陈述我们的表示定理之前，我们现在简要地解释核心思想：

1. 在[7]之后，我们使用傅里叶反变换将f(x)表示为某个随机变量ξ的Acos(<ξ,x>+ θ(ξ))的期望，然后使用ReLU单元实现cos(<ξ,x>+ θ(ξ))。
2. 我们使用一个类似于[24]中的想法来实现一个具有2k峰值的三角形波形T_k，使用~k^1/D个 ReLU单元在深度D的网络中排列。
3. 利用低频余弦与三角波形的组合，通过ReLU单元有效逼近cos(<ξ,x>+ θ(ξ))形式的高频余弦。

假设我们想要使用带有单个隐藏层的ReLU网络近似区间[-1,1]内t的函数f(t) = cos(ωt)。因为区间[-1,1]包含函数的Ω(ω)个周期，有效地跟踪它需要Ω(ω)个 ReLU单元。事实证明，如果我们允许两个非线性层，这种依赖性可以得到显著改善。The first layer is used

4 Main Results

接下来，我们在定理2中给出了一个匹配下界，它也表明了对于任意D，深度D和D + 1网络之间的深度分离。

5 Technical Results

在深入研究定理1和定理2的证明之前，我们需要一些技术性引理。

6 Proof of Theorem 1

7 Proof of Theorem 2

A Supplementary Material

A.1 Frequency Multipliers - Proofs
我们跳过引理1的证明，因为它是初等的。我们给出引理2的证明如下。


A.2 ReLU Representation for Sinusoids - Proofs