Error bounds for approximations with deep ReLU networks

doi:10.1016/j.neunet.2017.07.002

Neural Networks 神经网络

Volume 94, October 2017, Pages 103-114
第 94 卷，2017 年 10 月，第 103-114 页

https://doi.org/10.1016/j.neunet.2017.07.002 Get rights and content 获取权利和内容

Abstract 摘要

We study expressive power of shallow and deep neural networks with piece-wise linear activation functions. We establish new rigorous upper and lower bounds for the network complexity in the setting of approximations in Sobolev spaces. In particular, we prove that deep ReLU networks more efficiently approximate smooth functions than shallow networks. In the case of approximations of 1D Lipschitz functions we describe adaptive depth-6 network architectures more efficient than the standard shallow architecture.
我们研究了具有片断线性激活函数的浅层和深层神经网络的表达能力。我们在 Sobolev 空间近似的背景下，为网络复杂性建立了新的严格上下限。特别是，我们证明了深度 ReLU 网络比浅层网络更有效地逼近平滑函数。在近似一维 Lipschitz 函数的情况下，我们描述了比标准浅层架构更高效的自适应深度-6 网络架构。

Keywords 关键词

Deep ReLU networks

Approximation complexity

深度 ReLU 网络近似复杂度

1. Introduction 1.导言

Recently, multiple successful applications of deep neural networks to pattern recognition problems LeCun et al. (2015), Schmidhuber (2015) have revived active interest in theoretical properties of such networks, in particular their expressive power. It has been argued that deep networks may be more expressive than shallow ones of comparable size (see, e.g., Bianchini and Scarselli (2014), Delalleau and Bengio (2011), Montufar et al. (2014), Raghu et al. (2016), Telgarsky (2015)). In contrast to a shallow network, a deep one can be viewed as a long sequence of non-commutative transformations, which is a natural setting for high expressiveness (cf. the well-known Solovay–Kitaev theorem on fast approximation of arbitrary quantum operations by sequences of non-commutative gates, see Dawson and Nielsen (2006), Kitaev et al. (2002)).
最近，深度神经网络在模式识别问题上的多次成功应用LeCun等人（2015）、Schmidhuber（2015）重新激发了人们对此类网络理论特性的兴趣，尤其是它们的表现力。有人认为，深度网络可能比同等规模的浅层网络更具表现力（参见 Bianchini 和 Scarselli (2014)、Delalleau 和 Bengio (2011)、Montufar 等人 (2014)、Raghu 等人 (2016)、Telgarsky (2015)）。与浅层网络相比，深层网络可被视为非交换变换的长序列，这是高表达能力的天然环境（参见著名的索洛维-基塔耶夫定理：通过非交换门序列快速逼近任意量子运算，见 Dawson 和 Nielsen (2006)、Kitaev 等人 (2002)）。

There are various ways to characterize expressive power of networks. Delalleau and Bengio (2011) consider sum–product networks and prove for certain classes of polynomials that they are much more easily represented by deep networks than by shallow networks. Montufar et al. (2014) estimate the number of linear regions in the network’s landscape. Bianchini and Scarselli (2014) give bounds for Betti numbers characterizing topological properties of functions represented by networks. Telgarsky (2015), Telgarsky (2016) provides specific examples of classification problems where deep networks are provably more efficient than shallow ones.
表征网络表达能力的方法多种多样。Delalleau 和 Bengio（2011 年）考虑了和积网络，并证明对于某些多项式类别，深度网络比浅层网络更容易表现它们。Montufar 等人（2014 年）估算了网络景观中线性区域的数量。Bianchini 和 Scarselli（2014）给出了贝蒂数的边界，表征了网络所代表函数的拓扑特性。Telgarsky (2015)、Telgarsky (2016) 提供了分类问题的具体例子，证明深度网络比浅层网络更有效。

In the context of classification problems, a general and standard approach to characterizing expressiveness is based on the notion of the Vapnik–Chervonenkis dimension (Vapnik & Chervonenkis, 2015). There exist several bounds for VC-dimension of deep networks with piece-wise polynomial activation functions that go back to geometric techniques of Goldberg and Jerrum (1995) and earlier results of Warren (1968); see Bartlett et al. (1998), Sakurai (1999) and the book (Anthony & Bartlett, 2009). There is a related concept, the fat-shattering dimension, for real-valued approximation problems Anthony and Bartlett (2009), Kearns and Schapire (1990).
在分类问题中，表征表现力的一般标准方法是基于 Vapnik-Chervonenkis 维度的概念（Vapnik & Chervonenkis, 2015）。对于具有片断多项式激活函数的深度网络的 VC 维度，存在几种边界，这些边界可追溯到 Goldberg 和 Jerrum（1995 年）的几何技术以及 Warren（1968 年）的早期结果；参见 Bartlett 等人（1998 年）、Sakurai（1999 年）和本书（Anthony & Bartlett, 2009 年）。对于实值近似问题，Anthony 和 Bartlett (2009)、Kearns 和 Schapire (1990)有一个相关的概念，即 "碎脂维度"。

A very general approach to expressiveness in the context of approximation is the method of nonlinear widths by DeVore, Howard, and Micchelli (1989) that concerns approximation of a family of functions under assumption of a continuous dependence of the model on the approximated function.
DeVore 、Howard 和 Micchelli（1989 年）提出的非线性宽度法是近似计算中一种非常通用的表达方法，它涉及在模型对近似函数具有连续依赖性的假设条件下对函数族的近似。

In this paper we examine the problem of shallow-vs-deep expressiveness from the perspective of approximation theory and general spaces of functions having derivatives up to certain order (Sobolev-type spaces). In this framework, the problem of expressiveness is very well studied in the case of shallow networks with a single hidden layer, where it is known, in particular, that to approximate a $C^{n}$ -function on a $d$ -dimensional set with infinitesimal error $ϵ$ one needs a network of size about $ϵ^{- d ∕ n}$ , assuming a smooth activation function (see, e.g., Mhaskar (1996), Pinkus (1999) for a number of related rigorous upper and lower bounds and further qualifications of this result). Much less seems to be known about deep networks in this setting, though Mhaskar, Liao, and Poggio (2016), Mhaskar and Poggio (2016) have recently introduced functional spaces constructed using deep dependency graphs and obtained expressiveness bounds for related deep networks.
在本文中，我们从近似理论和具有一定阶导数的函数的一般空间（Sobolev 型空间）的角度来研究浅层与深层的表现力问题。在这一框架下，人们对单隐层浅层网络的表现力问题研究得非常透彻，尤其是已知要在 $d$ 维集合上以无穷小误差 $ϵ$ 近似一个 $C^{n}$ 函数，需要一个大小约为 $ϵ^{- d ∕ n}$ 的网络，同时假设激活函数是平滑的（参见 Mhaskar (1996)、Pinkus (1999)，以了解大量相关的严格上下限和对这一结果的进一步限定）。虽然 Mhaskar、Liao 和 Poggio（2016 年）、Mhaskar 和 Poggio（2016 年）最近引入了使用深度依赖图构建的函数空间，并获得了相关深度网络的表现力边界，但人们对这种情况下的深度网络的了解似乎要少得多。

We will focus our attention on networks with the ReLU activation function $σ (x) = max (0, x)$ , which, despite its utter simplicity, seems to be the most popular choice in practical applications (LeCun et al., 2015). We will consider $L^{\infty}$ -error of approximation of functions belonging to the Sobolev spaces $W^{n, \infty} ({[0, 1]}^{d})$ (without any assumptions of hierarchical structure). We will often consider families of approximations, as the approximated function runs over the unit ball $F_{d, n}$ in $W^{n, \infty} ({[0, 1]}^{d})$ . In such cases we will distinguish scenarios of fixed and adaptive network architectures. Our goal is to obtain lower and upper bounds on the expressiveness of deep and shallow networks in different scenarios. We measure complexity of networks in a conventional way, by counting the number of their weights and computation units (cf. Anthony and Bartlett (2009)).
我们将重点关注具有 ReLU 激活函数 $σ (x) = max (0, x)$ 的网络，尽管它非常简单，但似乎是实际应用中最受欢迎的选择（LeCun 等人，2015 年）。我们将考虑 $L^{\infty}$ -属于 Sobolev 空间 $W^{n, \infty} ({[0, 1]}^{d})$ 的函数的近似误差（没有任何层次结构假设）。在这种情况下，我们将区分固定网络架构和自适应网络架构。我们的目标是获得深层和浅层网络在不同场景下的表现力下限和上限。我们用传统方法测量网络的复杂性，即计算其权重和计算单元的数量（参见 Anthony 和 Bartlett (2009)）。

The main body of the paper consists of Sections 2 The ReLU network model, 3 Upper bounds, 4 Lower bounds.
本文主体包括第 2 节 ReLU 网络模型、第 3 节上界、第 4 节下界。

In Section 2 we describe our ReLU network model and show that the ReLU function is replaceable by any other continuous piece-wise linear activation function, up to constant factors in complexity asymptotics (Proposition 1).
在第 2 节中，我们描述了 ReLU 网络模型，并证明 ReLU 函数可由任何其他连续的片断线性激活函数替代，在复杂性渐近论中可达到常数因子（命题 1）。

In Section 3 we establish several upper bounds on the complexity of approximating by ReLU networks, in particular showing that deep networks are quite efficient for approximating smooth functions. Specifically:
在第 3 节中，我们确定了 ReLU 网络近似复杂度的几个上限，特别是表明深度网络在近似平滑函数时相当高效。具体来说

$•$
In Section 3.1 we show that the function $f (x) = x^{2}$ can be $ϵ$ -approximated by a network of depth and complexity $O (ln (1 ∕ ϵ))$ (Proposition 2). This also leads to similar upper bounds on the depth and complexity that are sufficient to implement an approximate multiplication in a ReLU network (Proposition 3).
在第 3.1 节中，我们证明了函数 $f (x) = x^{2}$ 可以通过深度和复杂度均为 $O (ln (1 ∕ ϵ))$ 的网络进行 $ϵ$ 近似运算（命题 2）。这也引出了在 ReLU 网络中实现近似乘法所需的深度和复杂度的类似上限（命题 3）。
$•$
In Section 3.2 we describe a ReLU network architecture of depth $O (ln (1 ∕ ϵ))$ and complexity $O (ϵ^{- d ∕ n} ln (1 ∕ ϵ))$ that is capable of approximating with error $ϵ$ any function from $F_{d, n}$ (Theorem 1).
在第 3.2 节中，我们描述了一个深度为 $O (ln (1 ∕ ϵ))$ 、复杂度为 $O (ϵ^{- d ∕ n} ln (1 ∕ ϵ))$ 的 ReLU 网络结构，它能够以误差 $ϵ$ 近似 $F_{d, n}$ 中的任何函数（定理 1）。
$•$
In Section 3.3 we show that, even with fixed-depth networks, one can further decrease the approximation complexity if the network architecture is allowed to depend on the approximated function. Specifically, we prove that one can $ϵ$ -approximate a given Lipschitz function on the segment $[0, 1]$ by a depth-6 ReLU network with $O (\frac{1}{ϵ ln (1 ∕ ϵ)})$ connections and activation units (Theorem 2). This upper bound is of interest since it lies below the lower bound provided by the method of nonlinear widths under assumption of continuous model selection (see Section 4.1).
在第 3.3 节中，我们将证明，即使是固定深度的网络，如果允许网络结构依赖于近似函数，也可以进一步降低近似复杂度。具体地说，我们证明了一个具有 $O (\frac{1}{ϵ ln (1 ∕ ϵ)})$ 连接和激活单元的深度为 6 的 ReLU 网络可以 $ϵ$ 近似 $[0, 1]$ 段上的给定 Lipschitz 函数（定理 2）。这个上界低于连续模型选择假设下的非线性宽度方法所提供的下界（见第 4.1 节），因此很有意义。

In Section 4 we obtain several lower bounds on the complexity of approximation by deep and shallow ReLU networks, using different approaches and assumptions.
在第 4 节中，我们利用不同的方法和假设，得出了深层和浅层 ReLU 网络近似复杂度的几个下限。

$•$
In Section 4.1 we recall the general lower bound provided by the method of continuous nonlinear widths. This method assumes that parameters of the approximation continuously depend on the approximated function, but does not assume anything about how the approximation depends on its parameters. In this setup, at least $\sim ϵ^{- d ∕ n}$ connections and weights are required for an $ϵ$ -approximation on $F_{d, n}$ (Theorem 3). As already mentioned, for $d = n = 1$ this lower bound is above the upper bound provided by Theorem 2.
在第 4.1 节中，我们回顾了连续非线性宽度法提供的一般下限。这种方法假定近似的参数连续地依赖于近似函数，但不假定近似如何依赖于其参数。在这种情况下，对 $F_{d, n}$ 的 $ϵ$ 近似至少需要 $\sim ϵ^{- d ∕ n}$ 的连接和权重（定理 3）。如前所述，对 $d = n = 1$ 而言，这一下限高于定理 2 所提供的上限。
$•$
In Section 4.2 we consider the setup where the same network architecture is used to approximate all functions in $F_{d, n}$ , but the weights are not assumed to continuously depend on the function. In this case, application of existing results on VC-dimension of deep piece-wise polynomial networks yields a $\sim ϵ^{d ∕ (2 n)}$ lower bound in general and a $\sim ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ)$ lower bound if the network depth grows as $O ({ln}^{p} (1 ∕ ϵ))$ (Theorem 4).
在第 4.2 节中，我们考虑了使用相同网络结构逼近 $F_{d, n}$ 中所有函数，但权重不连续依赖于函数的情况。在这种情况下，应用现有的关于深度片断多项式网络 VC 维度的结果，一般会得到 $\sim ϵ^{d ∕ (2 n)}$ 的下限，如果网络深度以 $O ({ln}^{p} (1 ∕ ϵ))$ 的方式增长，则会得到 $\sim ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ)$ 的下限（定理 4）。
$•$
In Section 4.3 we consider an individual approximation, without any assumptions regarding it as an element of a family as in Sections 4.1 and 4.2. We prove that for any $d, n$ there exists a function in $W^{n, \infty} ({[0, 1]}^{d})$ such that its approximation complexity is not $o (ϵ^{- d ∕ (9 n)})$ as $ϵ \to 0$ (Theorem 5).
在第 4.3 节中，我们将考虑单个近似值，而不像第 4.1 节和第 4.2 节那样假设它是一个族的元素。我们将证明，对于任何 $d, n$ 都存在一个 $W^{n, \infty} ({[0, 1]}^{d})$ 中的函数，使得它的近似复杂度不是 $o (ϵ^{- d ∕ (9 n)})$ 而是 $ϵ \to 0$ （定理 5）。
$•$
In Section 4.4 we prove that $ϵ$ -approximation of any nonlinear $C^{2}$ -function by a network of fixed depth $L$ requires at least $\sim ϵ^{- 1 ∕ (2 (L - 2))}$ computation units (Theorem 6). By comparison with Theorem 1, this shows that for sufficiently smooth functions approximation by fixed-depth ReLU networks is less efficient than by unbounded-depth networks.
在第 4.4 节中，我们证明用固定深度为 $L$ 的网络对任何非线性 $C^{2}$ 函数进行 $ϵ$ 近似至少需要 $\sim ϵ^{- 1 ∕ (2 (L - 2))}$ 计算单元（定理 6）。与定理 1 相比，这表明对于足够光滑的函数，用固定深度 ReLU 网络逼近的效率比用无界深度网络逼近的效率要低。

In Section 5 we discuss the obtained bounds and summarize their implications, in particular comparing deep vs. shallow networks and fixed vs. adaptive architectures.
在第 5 节中，我们将讨论所获得的边界并总结其影响，特别是比较深层网络与浅层网络以及固定架构与自适应架构。

The arXiv preprint of the first version of the present work appeared almost simultaneously with the work of Liang and Srikant (2016) containing results partly overlapping with our results in Sections 3.1 Fast deep approximation of squaring and multiplication, 3.2 Fast deep approximation of general smooth functions, 4.4 Slow approximation of smooth functions by shallow networks. Liang and Srikant consider networks equipped with both ReLU and threshold activation functions. They prove a logarithmic upper bound for the complexity of approximating the function $f (x) = x^{2}$ , which is analogous to our Proposition 2. Then, they extend this upper bound to polynomials and smooth functions. In contrast to our treatment of generic smooth functions based on standard Sobolev spaces, they impose more complex assumptions on the function (including, in particular, how many derivatives it has) that depend on the required approximation accuracy $ϵ$ . As a consequence, they obtain strong $O ({ln}^{c} (1 ∕ ϵ))$ complexity bounds rather different from our bound in Theorem 1 (in fact, our lower bound proved in Theorem 5 rules out, in general, such strong upper bounds for functions having only finitely many derivatives). Also, Liang and Srikant prove a lower bound for the complexity of approximating convex functions by shallow networks. Our version of this result, given in Section 4.4, is different in that we assume smoothness and nonlinearity instead of global convexity.
本工作第一版的 arXiv 预印本几乎与 Liang 和 Srikant（2016 年）的工作同时出现，其中的结果与我们在第 3.1 节 "平方和乘法的快速深度逼近"、第 3.2 节 "一般平滑函数的快速深度逼近"、第 4.4 节 "浅层网络对平滑函数的慢速逼近 "中的结果部分重叠。Liang 和 Srikant 考虑了同时配备 ReLU 和阈值激活函数的网络。他们证明了函数 $f (x) = x^{2}$ 近似复杂度的对数上限，这与我们的命题 2 类似。然后，他们将这一上限扩展到多项式和平滑函数。与我们基于标准索波列夫空间对一般平稳函数的处理不同，他们对函数（尤其包括函数有多少导数）施加了更复杂的假设，而这些假设取决于所需的逼近精度 $ϵ$ 。因此，他们得到的强 $O ({ln}^{c} (1 ∕ ϵ))$ 复杂性边界与我们在定理 1 中的边界截然不同（事实上，我们在定理 5 中证明的下界一般排除了对只有有限多个导数的函数的强上界）。此外，Liang 和 Srikant 还证明了用浅层网络逼近凸函数的复杂度下限。我们在第 4.4 节中给出的这一结果与之不同，我们假设的是平滑性和非线性，而不是全局凸性。

2. The ReLU network model
2.ReLU 网络模型

Throughout the paper, we consider feedforward neural networks with the ReLU (Rectified Linear Unit) activation function $σ (x) = max (0, x) .$ The network consists of several input units, one output unit, and a number of “hidden” computation units. Each hidden unit performs an operation of the form (1) $y = σ (\sum_{k = 1}^{N} w_{k} x_{k} + b)$ with some weights (adjustable parameters) ${(w_{k})}_{k = 1}^{N}$ and $b$ depending on the unit. The output unit is also a computation unit, but without the nonlinearity, i.e., it computes $y = \sum_{k = 1}^{N} w_{k} x_{k} + b$ . The units are grouped in layers, and the inputs ${(x_{k})}_{k = 1}^{N}$ of a computation unit in a certain layer are outputs of some units belonging to any of the preceding layers (see Fig. 1). Note that we allow connections between units in non-neighboring layers. Occasionally, when this cannot cause confusion, we may denote the network and the function it implements by the same symbol.
在本文中，我们考虑的是具有 ReLU（整流线性单元）激活函数 $σ (x) = max (0, x) .$ 的前馈神经网络。该网络由多个输入单元、一个输出单元和若干 "隐藏 "计算单元组成。每个 "隐藏 "单元执行的运算形式为 (1) $y = σ (\sum_{k = 1}^{N} w_{k} x_{k} + b)$ ，并根据单元的不同设置一些权重（可调参数） ${(w_{k})}_{k = 1}^{N}$ 和 $b$ 。输出单元也是一个计算单元，但没有非线性，即计算 $y = \sum_{k = 1}^{N} w_{k} x_{k} + b$ 。单元按层分组，某层计算单元的输入 ${(x_{k})}_{k = 1}^{N}$ 是属于前几层的某些单元的输出（见图 1）。请注意，我们允许非相邻层的单元之间存在连接。有时，在不会引起混淆的情况下，我们可以用相同的符号表示网络及其实现的功能。

The depth of the network, the number of units and the total number of weights are standard measures of network complexity (Anthony & Bartlett, 2009). We will use these measures throughout the paper. The number of weights is, clearly, the sum of the total number of connections and the number of computation units. We identify the depth with the number of layers (in particular, the most common type of neural networks – shallow networks having a single hidden layer – are depth-3 networks according to this convention).
网络深度、单元数和权重总数是衡量网络复杂性的标准指标（Anthony & Bartlett，2009 年）。本文将通篇使用这些指标。权重数显然是连接总数和计算单元数的总和。我们用层数来确定深度（尤其是最常见的神经网络类型--具有单个隐藏层的浅层网络--根据这一惯例属于深度-3 网络）。

We finish this subsection with a proposition showing that, given our complexity measures, using the ReLU activation function is not much different from using any other piece-wise linear activation function with finitely many breakpoints: one can replace one network by an equivalent one but having another activation function while only increasing the number of units and weights by constant factors. This justifies our restricted attention to the ReLU networks (which could otherwise have been perceived as an excessively particular example of networks).
在本小节的最后，我们将提出一个命题，说明根据我们的复杂度度量，使用 ReLU 激活函数与使用任何其他具有有限多个断点的片断线性激活函数并无太大区别：我们可以用一个等效的网络取代一个网络，但使用另一个激活函数，而只需增加单位数和权重的常数。这就证明了我们只关注 ReLU 网络是有道理的（否则它可能会被视为一个过于特殊的网络实例）。

Proposition 1 命题 1

Let $ρ : R \to R$ be any continuous piece-wise linear function with $M$ breakpoints, where $1 \leq M < \infty$
让 $ρ : R \to R$ 是任意连续的片断线性函数，其断点为 $M$ ，其中 $1 \leq M < \infty$ .

(a)
Let $ξ$ be a network with the activation function $ρ$ , having depth $L$ , $W$ weights and $U$ computation units. Then there exists a ReLU network $η$ that has depth $L$ , not more than ${(M + 1)}^{2} W$ weights and not more than $(M + 1) U$ units, and that computes the same function as $ξ$
假设 $ξ$ 是一个具有激活函数 $ρ$ 的网络，其深度为 $L$ $W$ 权重和 $U$ 计算单元。那么存在一个深度为 $L$ 、权重不超过 ${(M + 1)}^{2} W$ 、计算单元不超过 $(M + 1) U$ 的 ReLU 网络 $η$ ，它计算的函数与 $ξ$ 相同。.
(b)
Conversely, let $η$ be a ReLU network of depth $L$ with $W$ weights and $U$ computation units. Let $D$ be a bounded subset of $R^{n}$ , where $n$ is the input dimension of $η$ . Then there exists a network with the activation function $ρ$ that has depth $L$ , $4 W$ weights and $2 U$ units, and that computes the same function as $η$ on the set $D$
反过来，假设 $η$ 是一个深度为 $L$ 的 ReLU 网络，权重为 $W$ ，计算单元为 $U$ 。让 $D$ 是 $R^{n}$ 的有界子集，其中 $n$ 是 $η$ 的输入维度。那么就存在一个具有激活函数 $ρ$ 的网络，它的深度为 $L$ $4 W$ 权重和 $2 U$ 单元，在集合 $D$ 上计算与 $η$ 相同的函数。.

Proof 证明

(a) Let $a_{1} < \dots < a_{M}$ be the breakpoints of $ρ$ , i.e., the points where its derivative is discontinuous: $ρ^{'} (a_{k} +) \neq ρ^{'} (a_{k} -)$ . We can then express $ρ$ via the ReLU function $σ$ , as a linear combination $ρ (x) = c_{0} σ (a_{1} - x) + \sum_{m = 1}^{M} c_{m} σ (x - a_{m}) + h$ with appropriately chosen coefficients ${(c_{m})}_{m = 0}^{M}$ and $h$ . It follows that computation performed by a single $ρ$ -unit, $x_{1}, \dots, x_{N} \mapsto ρ (\sum_{k = 1}^{N} w_{k} x_{k} + b),$ can be equivalently represented by a linear combination of a constant function and computations of $M + 1$ $σ$ -units, $x_{1}, \dots, x_{N} \mapsto \{\begin{matrix} σ (\sum_{k = 1}^{N} w_{k} x_{k} + b - a_{m}), & m = 1, \dots, M, \\ σ (a_{1} - b - \sum_{k = 1}^{N} w_{k} x_{k}), & m = 0 \end{matrix}$ (here $m$ is the index of a $ρ$ -unit). We can then replace one-by-one all the $ρ$ -units in the network $ξ$ by $σ$ -units, without changing the output of the network. Obviously, these replacements do not change the network depth. Since each hidden unit gets replaced by $M + 1$ new units, the number of units in the new network is not greater than $M + 1$ times their number in the original network. Note also that the number of connections in the network is multiplied, at most, by ${(M + 1)}^{2}$ . Indeed, each unit replacement entails replacing each of the incoming and outgoing connections of this unit by $M + 1$ new connections, and each connection is replaced twice: as an incoming and as an outgoing one. These considerations imply the claimed complexity bounds for the resulting $σ$ -network $η$ .
(a) 设 $a_{1} < \dots < a_{M}$ 为 $ρ$ 的断点，即其导数不连续的点： $ρ^{'} (a_{k} +) \neq ρ^{'} (a_{k} -)$ .然后，我们可以通过 ReLU 函数 $σ$ 将 $ρ$ 表示为一个线性组合 $ρ (x) = c_{0} σ (a_{1} - x) + \sum_{m = 1}^{M} c_{m} σ (x - a_{m}) + h$ ，并适当选择系数 ${(c_{m})}_{m = 0}^{M}$ 和 $h$ 。由此可见，单个 $ρ$ 单位 $x_{1}, \dots, x_{N} \mapsto ρ (\sum_{k = 1}^{N} w_{k} x_{k} + b),$ 的计算可以等价地表示为一个常数函数和 $M + 1$ $σ$ 单位 $x_{1}, \dots, x_{N} \mapsto \{\begin{matrix} σ (\sum_{k = 1}^{N} w_{k} x_{k} + b - a_{m}), & m = 1, \dots, M, \\ σ (a_{1} - b - \sum_{k = 1}^{N} w_{k} x_{k}), & m = 0 \end{matrix}$ 的计算的线性组合（这里 $m$ 是 $ρ$ 单位的索引）。然后，我们可以在不改变网络输出的情况下，用 $σ$ 单位逐一替换 $ξ$ 网络中的所有 $ρ$ 单位。显然，这些替换不会改变网络深度。由于每个隐藏单元都会被 $M + 1$ 个新单元替换，因此新网络中单元的数量不会超过原始网络中单元数量的 $M + 1$ 倍。还需要注意的是，网络中的连接数最多乘以 ${(M + 1)}^{2}$ 。事实上，每个单元的替换都需要用 $M + 1$ 个新连接替换该单元的每个输入和输出连接，每个连接都会被替换两次：输入连接和输出连接。这些考虑意味着所得到的 $σ$ - 网络 $η$ 的复杂度边界。

(b) Let $a$ be any breakpoint of $ρ$ , so that $ρ^{'} (a +) \neq ρ^{'} (a -)$ . Let $r_{0}$ be the distance separating $a$ from the nearest other breakpoint, so that $ρ$ is linear on $[a, a + r_{0}]$ and on $[a - r_{0}, a]$ (if $ρ$ has only one node, any $r_{0} > 0$ will do). Then, for any $r > 0$ , we can express the ReLU function $σ$ via $ρ$ in the $r$ -neighborhood of 0: $σ (x) = \frac{ρ (a + \frac{r_{0}}{2 r} x) - ρ (a - \frac{r_{0}}{2} + \frac{r_{0}}{2 r} x) - ρ (a) + ρ (a - \frac{r_{0}}{2})}{(ρ^{'} (a +) - ρ^{'} (a -)) \frac{r_{0}}{2 r}}, x \in [- r, r] .$ It follows that a computation performed by a single $σ$ -unit, $x_{1}, \dots, x_{N} \mapsto σ (\sum_{k = 1}^{N} w_{k} x_{k} + b),$ can be equivalently represented by a linear combination of a constant function and two $ρ$ -units, $x_{1}, \dots, x_{N} \mapsto \{\begin{matrix} ρ (a + \frac{r_{0}}{2 r} b + \frac{r_{0}}{2 r} \sum_{k = 1}^{N} w_{k} x_{k}), \\ ρ (a - \frac{r_{0}}{2} + \frac{r_{0}}{2 r} b + \frac{r_{0}}{2 r} \sum_{k = 1}^{N} w_{k} x_{k}), \end{matrix}$ provided the condition (2) $\sum_{k = 1}^{N} w_{k} x_{k} + b \in [- r, r]$ holds. Since $D$ is a bounded set, we can choose $r$ at each unit of the initial network $η$ sufficiently large so as to satisfy condition (2) for all network inputs from $D$ . Then, like in (a), we replace each $σ$ -unit with two $ρ$ -units, which produces the desired $ρ$ -network. □
(b) 让 $a$ 成为 $ρ$ 的任意一个断点，从而 $ρ^{'} (a +) \neq ρ^{'} (a -)$ 。让 $r_{0}$ 是 $a$ 与最近的其他断点之间的距离，这样 $ρ$ 在 $[a, a + r_{0}]$ 和 $[a - r_{0}, a]$ 上是线性的（如果 $ρ$ 只有一个节点，那么任何 $r_{0} > 0$ 都可以）。那么，对于任意 $r > 0$ ，我们可以通过 $ρ$ 在 0 的 $r$ 邻域表达 ReLU 函数 $σ$ ： $σ (x) = \frac{ρ (a + \frac{r_{0}}{2 r} x) - ρ (a - \frac{r_{0}}{2} + \frac{r_{0}}{2 r} x) - ρ (a) + ρ (a - \frac{r_{0}}{2})}{(ρ^{'} (a +) - ρ^{'} (a -)) \frac{r_{0}}{2 r}}, x \in [- r, r] .$ 由此可见，只要条件 (2) $\sum_{k = 1}^{N} w_{k} x_{k} + b \in [- r, r]$ 成立，由单个 $σ$ 单位 $x_{1}, \dots, x_{N} \mapsto σ (\sum_{k = 1}^{N} w_{k} x_{k} + b),$ 执行的计算可以等价地用一个常数函数和两个 $ρ$ 单位 $x_{1}, \dots, x_{N} \mapsto \{\begin{matrix} ρ (a + \frac{r_{0}}{2 r} b + \frac{r_{0}}{2 r} \sum_{k = 1}^{N} w_{k} x_{k}), \\ ρ (a - \frac{r_{0}}{2} + \frac{r_{0}}{2 r} b + \frac{r_{0}}{2 r} \sum_{k = 1}^{N} w_{k} x_{k}), \end{matrix}$ 的线性组合来表示。由于 $D$ 是一个有界集，我们可以在初始网络的每个单元 $η$ 中选择足够大的 $r$ ，从而使来自 $D$ 的所有网络输入都满足条件 (2)。然后，与（a）中一样，我们用两个 $ρ$ 单位替换每个 $σ$ 单位，这样就得到了所需的 $ρ$ 网络。□

3. Upper bounds 3.上限

Throughout the paper, we will be interested in approximating functions $f : {[0, 1]}^{d} \to R$ by ReLU networks. Given a function $f : {[0, 1]}^{d} \to R$ and its approximation $\tilde{f}$ , by the approximation error we will always mean the uniform maximum error $‖ f - \tilde{f} ‖_{\infty} = max_{x \in {[0, 1]}^{d}} | f (x) - \tilde{f} (x) | .$
在本文中，我们将始终关注通过 ReLU 网络逼近函数 $f : {[0, 1]}^{d} \to R$ 的问题。给定函数 $f : {[0, 1]}^{d} \to R$ 及其近似值 $\tilde{f}$ ，近似误差总是指均匀最大误差 $‖ f - \tilde{f} ‖_{\infty} = max_{x \in {[0, 1]}^{d}} | f (x) - \tilde{f} (x) | .$

3.1. Fast deep approximation of squaring and multiplication
3.1.平方和乘法的快速深度逼近

Our first key result shows that ReLU networks with unconstrained depth can very efficiently approximate the function $f (x) = x^{2}$ (more efficiently than any fixed-depth network, as we will see in Section 4.4). Our construction uses the “sawtooth” function that has previously appeared in the paper by Telgarsky (2015).
我们的第一个关键结果表明，无深度限制的 ReLU 网络可以非常高效地逼近函数 $f (x) = x^{2}$ （比任何固定深度的网络都更高效，我们将在第 4.4 节中看到这一点）。我们的构造使用了之前出现在 Telgarsky（2015）论文中的 "锯齿 "函数。

Proposition 2 命题 2

The function $f (x) = x^{2}$ on the segment $[0, 1]$ can be approximated with any error $ϵ > 0$ by a ReLU network having the depth and the number of weights and computation units $O (ln (1 ∕ ϵ))$
可以用一个深度、权重和计算单元数为 $O (ln (1 ∕ ϵ))$ 的 ReLU 网络来逼近线段 $[0, 1]$ 上的函数 $f (x) = x^{2}$ ，误差为 $ϵ > 0$ 。.

Proof 证明

Consider the “tooth” (or “mirror”) function $g : [0, 1] \to [0, 1],$ $g (x) = \{\begin{matrix} 2 x, & x < \frac{1}{2}, \\ 2 (1 - x), & x \geq \frac{1}{2}, \end{matrix}$ and the iterated functions $g_{s} (x) = \underset{s}{\underset{︸}{g \circ g \circ \dots \circ g}} (x) .$ Telgarsky has shown (see Lemma 2.4 in Telgarsky (2015)) that $g_{s}$ is a “sawtooth” function with $2^{s - 1}$ uniformly distributed “teeth” (each application of $g$ doubles the number of teeth): $g_{s} (x) = \{\begin{matrix} 2^{s} (x - \frac{2 k}{2^{s}}), & x \in [\frac{2 k}{2^{s}}, \frac{2 k + 1}{2^{s}}], k = 0, 1, \dots, 2^{s - 1} - 1 \\ 2^{s} (\frac{2 k}{2^{s}} - x), & x \in [\frac{2 k - 1}{2^{s}}, \frac{2 k}{2^{s}}], k = 1, 2, \dots, 2^{s - 1}, \end{matrix}$ (see Fig. 2, Fig. 2(a)). Our key observation now is that the function $f (x) = x^{2}$ can be approximated by linear combinations of the functions $g_{s}$ . Namely, let $f_{m}$ be the piece-wise linear interpolation of $f$ with $2^{m} + 1$ uniformly distributed breakpoints $\frac{k}{2^{m}}, k = 0, \dots, 2^{m}$ : $f_{m} (\frac{k}{2^{m}}) = {(\frac{k}{2^{m}})}^{2}, k = 0, \dots, 2^{m}$ (see Fig. 2(b)). The function $f_{m}$ approximates $f$ with the error $ϵ_{m} = 2^{- 2 m - 2}$ . Now note that refining the interpolation from $f_{m - 1}$ to $f_{m}$ amounts to adjusting it by a function proportional to a sawtooth function: $f_{m - 1} (x) - f_{m} (x) = \frac{g_{m} (x)}{2^{2 m}} .$ Hence $f_{m} (x) = x - \sum_{s = 1}^{m} \frac{g_{s} (x)}{2^{2 s}} .$ Since $g$ can be implemented by a finite ReLU network (as $g (x) = 2 σ (x) - 4 σ (x - \frac{1}{2}) + 2 σ (x - 1)$ ) and since construction of $f_{m}$ only involves $O (m)$ linear operations and compositions of $g$ , we can implement $f_{m}$ by a ReLU network having depth and the number of weights and computation units all being $O (m)$ (see Fig. 2(c)). This implies the claim of the proposition. □
考虑 "齿"（或 "镜"）函数 $g : [0, 1] \to [0, 1],$ $g (x) = \{\begin{matrix} 2 x, & x < \frac{1}{2}, \\ 2 (1 - x), & x \geq \frac{1}{2}, \end{matrix}$ 和迭代函数 $g_{s} (x) = \underset{s}{\underset{︸}{g \circ g \circ \dots \circ g}} (x) .$ Telgarsky 已经证明（见 Telgarsky (2015)中的 Lemma 2.4）， $g_{s}$ 是一个具有 $2^{s - 1}$ 均匀分布的 "齿 "的 "锯齿 "函数（每次应用 $g$ 都会使齿的数量加倍）：6#（见图 2，图 2(a)）。我们现在要观察的关键是，函数 $f (x) = x^{2}$ 可以用函数 $g_{s}$ 的线性组合来近似。也就是说，让 $f_{m}$ 成为 $f$ 与 $2^{m} + 1$ 均匀分布的断点 $\frac{k}{2^{m}}, k = 0, \dots, 2^{m}$ ： $f_{m} (\frac{k}{2^{m}}) = {(\frac{k}{2^{m}})}^{2}, k = 0, \dots, 2^{m}$ （见图 2(b)）。函数 $f_{m}$ 近似 $f$ ，误差为 $ϵ_{m} = 2^{- 2 m - 2}$ 。现在请注意，从 $f_{m - 1}$ 到 $f_{m}$ 的细化插值相当于用一个与锯齿形函数成比例的函数进行调整： $f_{m - 1} (x) - f_{m} (x) = \frac{g_{m} (x)}{2^{2 m}} .$ 因此 $f_{m} (x) = x - \sum_{s = 1}^{m} \frac{g_{s} (x)}{2^{2 s}} .$ 由于 $g$ 可以用有限 ReLU 网络来实现（如 $g (x) = 2 σ (x) - 4 σ (x - \frac{1}{2}) + 2 σ (x - 1)$ ），并且由于 $f_{m}$ 的构造只涉及 $O (m)$ 的线性运算和 $g$ 的合成，我们可以用一个深度、权重和计算单元数都为 $O (m)$ 的 ReLU 网络来实现 $f_{m}$ （见图 2(c)）。这意味着命题的主张。□

Since (3) $x y = \frac{1}{2} ({(x + y)}^{2} - x^{2} - y^{2}),$ we can use Proposition 2 to efficiently implement accurate multiplication in a ReLU network. The implementation will depend on the required accuracy and the magnitude of the multiplied quantities.
由于 (3) $x y = \frac{1}{2} ({(x + y)}^{2} - x^{2} - y^{2}),$ ，我们可以利用命题 2 在 ReLU 网络中有效地实现精确乘法。实现方式取决于所需的精度和被乘量的大小。

Proposition 3 命题 3

Given $M > 0$ and $ϵ \in (0, 1)$ , there is a ReLU network $η$ with two input units that implements a function $\tilde{\times} : R^{2} \to R$ so that
给定 $M > 0$ 和 $ϵ \in (0, 1)$ ，有一个带有两个输入单元的 ReLU 网络 $η$ ，它实现了一个函数 $\tilde{\times} : R^{2} \to R$ ，因此

(a)
for any inputs $x, y$ , if $| x | \leq M$ and $| y | \leq M$ , then $| \tilde{\times} (x, y) - x y | \leq ϵ$ ;
对于任何输入 $x, y$ ，如果 $| x | \leq M$ 和 $| y | \leq M$ ，那么 $| \tilde{\times} (x, y) - x y | \leq ϵ$ ；
(b)
if $x = 0$ or $y = 0$ , then $\tilde{\times} (x, y) = 0$ ;
如果 $x = 0$ 或 $y = 0$ ，则 $\tilde{\times} (x, y) = 0$ ；
(c)
the depth and the number of weights and computation units in $η$ are not greater than $c_{1} ln (1 ∕ ϵ) + c_{2}$ with an absolute constant $c_{1}$ and a constant $c_{2} = c_{2} (M)$
0#中的深度、权重数和计算单元数不大于 $c_{1} ln (1 ∕ ϵ) + c_{2}$ ，绝对常数为 $c_{1}$ ，常数为 $c_{2} = c_{2} (M)$ 。.

Proof 证明

Let ${\tilde{f}}_{sq, δ}$ be the approximate squaring function from Proposition 2 such that ${\tilde{f}}_{sq, δ} (0) = 0$ and $| {\tilde{f}}_{sq, δ} (x) - x^{2} | < δ$ for $x \in [0, 1]$ . Assume without loss of generality that $M \geq 1$ and set (4) $\tilde{\times} (x, y) = \frac{M^{2}}{8} ({\tilde{f}}_{sq, δ} (\frac{| x + y |}{2 M}) - {\tilde{f}}_{sq, δ} (\frac{| x |}{2 M}) - {\tilde{f}}_{sq, δ} (\frac{| y |}{2 M})),$ where $δ = \frac{8 ϵ}{3 M^{2}}$ . Then property (b) is immediate and (a) follows easily using expansion (3). To conclude (c), observe that computation (4) consists of three instances of ${\tilde{f}}_{sq, δ}$ and finitely many linear and ReLU operations, so, using Proposition 2, we can implement $\tilde{\times}$ by a ReLU network such that its depth and the number of computation units and weights are $O (ln (1 ∕ δ))$ , i.e. are $O (ln (1 ∕ ϵ) + ln M)$ . □
让 ${\tilde{f}}_{sq, δ}$ 是命题 2 中的近似平方函数，这样 ${\tilde{f}}_{sq, δ} (0) = 0$ 和 $| {\tilde{f}}_{sq, δ} (x) - x^{2} | < δ$ 对于 $x \in [0, 1]$ .在不失一般性的前提下，假设 $M \geq 1$ 并设 (4) $\tilde{\times} (x, y) = \frac{M^{2}}{8} ({\tilde{f}}_{sq, δ} (\frac{| x + y |}{2 M}) - {\tilde{f}}_{sq, δ} (\frac{| x |}{2 M}) - {\tilde{f}}_{sq, δ} (\frac{| y |}{2 M})),$ 为 $δ = \frac{8 ϵ}{3 M^{2}}$ 。那么性质 (b) 是直接的，而 (a) 很容易通过展开式 (3) 得出。为了得出(c)，请观察计算(4)由 ${\tilde{f}}_{sq, δ}$ 的三个实例以及有限多的线性和 ReLU 运算组成，因此，利用命题 2，我们可以用一个 ReLU 网络来实现 $\tilde{\times}$ ，使得它的深度和计算单元与权重的数量都是 $O (ln (1 ∕ δ))$ ，即都是 $O (ln (1 ∕ ϵ) + ln M)$ 。□

3.2. Fast deep approximation of general smooth functions
3.2.一般光滑函数的快速深度逼近

In order to formulate our general result, Theorem 1, we consider the Sobolev spaces $W^{n, \infty} ({[0, 1]}^{d})$ with $n = 1, 2, \dots$ . Recall that $W^{n, \infty} ({[0, 1]}^{d})$ is defined as the space of functions on ${[0, 1]}^{d}$ lying in $L^{\infty}$ along with their weak derivatives up to order $n$ . The norm in $W^{n, \infty} ({[0, 1]}^{d})$ can be defined by $‖ f ‖_{W^{n, \infty} ({[0, 1]}^{d})} = max_{n : | n | \leq n} \underset{x \in {[0, 1]}^{d}}{ess sup} | D^{n} f (x) |,$ where $n = (n_{1}, \dots, n_{d}) \in {0, 1, \dots}^{d}$ , $| n | = n_{1} + \dots + n_{d}$ , and $D^{n} f$ is the respective weak derivative. Here and in the sequel we denote vectors by boldface characters. The space $W^{n, \infty} ({[0, 1]}^{d})$ can be equivalently described as consisting of the functions from $C^{n - 1} ({[0, 1]}^{d})$ such that all their derivatives of order $n - 1$ are Lipschitz continuous.
为了提出我们的一般结果，即定理 1，我们考虑了 $W^{n, \infty} ({[0, 1]}^{d})$ 与 $n = 1, 2, \dots$ 的索波列夫空间。回想一下， $W^{n, \infty} ({[0, 1]}^{d})$ 被定义为 ${[0, 1]}^{d}$ 上位于 $L^{\infty}$ 的函数空间及其直到 $n$ 阶的弱导数。 $W^{n, \infty} ({[0, 1]}^{d})$ 中的规范可以用 $‖ f ‖_{W^{n, \infty} ({[0, 1]}^{d})} = max_{n : | n | \leq n} \underset{x \in {[0, 1]}^{d}}{ess sup} | D^{n} f (x) |,$ 来定义，其中 $n = (n_{1}, \dots, n_{d}) \in {0, 1, \dots}^{d}$ , $| n | = n_{1} + \dots + n_{d}$ 和 $D^{n} f$ 是各自的弱导数。在这里和后续章节中，我们用黑体字表示向量。空间 $W^{n, \infty} ({[0, 1]}^{d})$ 可以等价地描述为由来自 $C^{n - 1} ({[0, 1]}^{d})$ 的函数组成，这些函数的所有阶导数 $n - 1$ 都是 Lipschitz 连续的。

Throughout the paper, we denote by $F_{n, d}$ the unit ball in $W^{n, \infty} ({[0, 1]}^{d})$ : $F_{n, d} = {f \in W^{n, \infty} ({[0, 1]}^{d}) : ‖ f ‖_{W^{n, \infty} ({[0, 1]}^{d})} \leq 1} .$
在本文中，我们用 $F_{n, d}$ 表示 $W^{n, \infty} ({[0, 1]}^{d})$ 中的单位球： $F_{n, d} = {f \in W^{n, \infty} ({[0, 1]}^{d}) : ‖ f ‖_{W^{n, \infty} ({[0, 1]}^{d})} \leq 1} .$

Also, it will now be convenient to make a distinction between networks and network architectures : we define the latter as the former with unspecified weights. We say that a network architecture is capable of expressing any function from $F_{d, n}$ with error $ϵ$ meaning that this can be achieved by some weight assignment.
此外，我们现在可以方便地对网络和网络架构进行区分：我们将后者定义为前者，但不指定权重。我们说，网络结构能够表达来自 $F_{d, n}$ 的任何函数，且误差为 $ϵ$ ，这意味着可以通过某种权重分配来实现。

Theorem 1 定理 1

For any $d, n$ and $ϵ \in (0, 1)$ , there is a ReLU network architecture that
对于任意的 $d, n$ 和 $ϵ \in (0, 1)$ ，都有一个 ReLU 网络结构，即

1.
is capable of expressing any function from $F_{d, n}$ with error $ϵ$ ;
能够表达来自 $F_{d, n}$ 的任何函数，且误差为 $ϵ$ ；
2.
has the depth at most $c (ln (1 ∕ ϵ) + 1)$ and at most $c ϵ^{- d ∕ n} (ln (1 ∕ ϵ) + 1)$ weights and computation units, with some constant $c = c (d, n)$
深度最多为 $c (ln (1 ∕ ϵ) + 1)$ ，权重和计算单元最多为 $c ϵ^{- d ∕ n} (ln (1 ∕ ϵ) + 1)$ ，常数为 $c = c (d, n)$ .

Proof 证明

The proof will consist of two steps. We start with approximating $f$ by a sum–product combination $f_{1}$ of local Taylor polynomials and one-dimensional piecewise-linear functions. After that, we will use results of the previous section to approximate $f_{1}$ by a neural network.
证明分为两个步骤。首先，我们用局部泰勒多项式和一维片断线性函数的和积组合 $f_{1}$ 近似 $f$ 。之后，我们将利用上一节的结果，用神经网络来逼近 $f_{1}$ 。

Let $N$ be a positive integer. Consider a partition of unity formed by a grid of ${(N + 1)}^{d}$ functions $ϕ_{m}$ on the domain ${[0, 1]}^{d}$ : $\sum_{m} ϕ_{m} (x) \equiv 1, x \in {[0, 1]}^{d} .$ Here $m = (m_{1}, \dots, m_{d}) \in {0, 1, \dots, N}^{d}$ , and the function $ϕ_{m}$ is defined as the product (5) $ϕ_{m} (x) = \prod_{k = 1}^{d} ψ (3 N (x_{k} - \frac{m_{k}}{N})),$ where $ψ (x) = \{\begin{matrix} 1, & | x | < 1, \\ 0, & 2 < | x |, \\ 2 - | x |, & 1 \leq | x | \leq 2 \end{matrix}$ (see Fig. 3). Note that (6) $‖ ψ ‖_{\infty} = 1 and ‖ ϕ_{m} ‖_{\infty} = 1 \forall m$ and (7) $supp ϕ_{m} \subset {x : | x_{k} - \frac{m_{k}}{N} | < \frac{1}{N} \forall k} .$
设 $N$ 为正整数。考虑由域 ${[0, 1]}^{d}$ 上的 ${(N + 1)}^{d}$ 函数 $ϕ_{m}$ 的网格构成的 unity 的分割： $\sum_{m} ϕ_{m} (x) \equiv 1, x \in {[0, 1]}^{d} .$ 这里是 $m = (m_{1}, \dots, m_{d}) \in {0, 1, \dots, N}^{d}$ ，函数 $ϕ_{m}$ 定义为 (5) $ϕ_{m} (x) = \prod_{k = 1}^{d} ψ (3 N (x_{k} - \frac{m_{k}}{N})),$ 其中 $ψ (x) = \{\begin{matrix} 1, & | x | < 1, \\ 0, & 2 < | x |, \\ 2 - | x |, & 1 \leq | x | \leq 2 \end{matrix}$ 的乘积（见图 3）。注意 (6) $‖ ψ ‖_{\infty} = 1 and ‖ ϕ_{m} ‖_{\infty} = 1 \forall m$ 和 (7) $supp ϕ_{m} \subset {x : | x_{k} - \frac{m_{k}}{N} | < \frac{1}{N} \forall k} .$

For any $m \in {0, \dots, N}^{d}$ , consider the degree- $(n - 1)$ Taylor polynomial for the function $f$ at $x = \frac{m}{N}$ : (8) $P_{m} (x) = \sum_{n : | n | < n} \frac{D^{n} f}{n!} |_{x = \frac{m}{N}} {(x - \frac{m}{N})}^{n},$ with the usual conventions $n! = \prod_{k = 1}^{d} n_{k}!$ and ${(x - \frac{m}{N})}^{n} = \prod_{k = 1}^{d} {(x_{k} - \frac{m_{k}}{N})}^{n_{k}}$ . Now define an approximation to $f$ by (9) $f_{1} = \sum_{m \in {0, \dots, N}^{d}} ϕ_{m} P_{m} .$ We bound the approximation error using the Taylor expansion of $f$ : $| f (x) - f_{1} (x) | = | \sum_{m} ϕ_{m} (x) (f (x) - P_{m} (x)) | \leq \sum_{m : | x_{k} - \frac{m_{k}}{N} | < \frac{1}{N} \forall k} | f (x) - P_{m} (x) | \leq 2^{d} max_{m : | x_{k} - \frac{m_{k}}{N} | < \frac{1}{N} \forall k} | f (x) - P_{m} (x) | \leq \frac{2^{d} d^{n}}{n!} {(\frac{1}{N})}^{n} max_{n : | n | = n} \underset{x \in {[0, 1]}^{d}}{ess sup} | D^{n} f (x) | \leq \frac{2^{d} d^{n}}{n!} {(\frac{1}{N})}^{n} .$ Here in the second step we used the support property (7) and the bound (6), in the third the observation that any $x \in {[0, 1]}^{d}$ belongs to the support of at most $2^{d}$ functions $ϕ_{m}$ , in the fourth a standard bound for the Taylor remainder, and in the fifth the property $‖ f ‖_{W^{n, \infty} ({[0, 1]}^{d})} \leq 1 .$
对于任意 $m \in {0, \dots, N}^{d}$ , 考虑函数 $f$ 在 $x = \frac{m}{N}$ ： (8) $P_{m} (x) = \sum_{n : | n | < n} \frac{D^{n} f}{n!} |_{x = \frac{m}{N}} {(x - \frac{m}{N})}^{n},$ 与通常的约定 $n! = \prod_{k = 1}^{d} n_{k}!$ 和 ${(x - \frac{m}{N})}^{n} = \prod_{k = 1}^{d} {(x_{k} - \frac{m_{k}}{N})}^{n_{k}}$ 。现在用 (9) $f_{1} = \sum_{m \in {0, \dots, N}^{d}} ϕ_{m} P_{m} .$ 来定义 $f$ 的近似值，我们用 $f$ 的泰勒展开来约束近似误差：在第二步中，我们使用了支持性质 (7) 和约束 (6)；在第三步中，我们观察到任何 $x \in {[0, 1]}^{d}$ 都属于最多 $2^{d}$ 个函数 $ϕ_{m}$ 的支持；在第四步中，我们使用了泰勒余数的标准约束；在第五步中，我们使用了性质 $‖ f ‖_{W^{n, \infty} ({[0, 1]}^{d})} \leq 1 .$ 。

It follows that if we choose (10) $N = ⌈ {(\frac{n!}{2^{d} d^{n}} \frac{ϵ}{2})}^{- 1 ∕ n} ⌉$ (where $⌈ \cdot ⌉$ is the ceiling function), then (11) $‖ f - f_{1} ‖_{\infty} \leq \frac{ϵ}{2} .$ Note that, by (8) the coefficients of the polynomials $P_{m}$ are uniformly bounded for all $f \in F_{d, n}$ : (12) $P_{m} (x) = \sum_{n : | n | < n} a_{m, n} {(x - \frac{m}{N})}^{n}, | a_{m, n} | \leq 1 .$
由此可见，如果我们选择 (10) $N = ⌈ {(\frac{n!}{2^{d} d^{n}} \frac{ϵ}{2})}^{- 1 ∕ n} ⌉$ （其中 $⌈ \cdot ⌉$ 是上限函数），那么 (11) $‖ f - f_{1} ‖_{\infty} \leq \frac{ϵ}{2} .$ 注意，根据 (8)，多项式 $P_{m}$ 的系数对所有 $f \in F_{d, n}$ ： (12) $P_{m} (x) = \sum_{n : | n | < n} a_{m, n} {(x - \frac{m}{N})}^{n}, | a_{m, n} | \leq 1 .$

We have therefore reduced our task to the following: construct a network architecture capable of approximating with uniform error $\frac{ϵ}{2}$ any function of the form (9), assuming that $N$ is given by (10) and the polynomials $P_{m}$ are of the form (12).
因此，我们将任务简化为：假设 $N$ 由 (10) 给出，多项式 $P_{m}$ 的形式为 (12)，构建一个能够以均匀误差 $\frac{ϵ}{2}$ 近似 (9) 形式的任何函数的网络架构。

Expand $f_{1}$ as (13) $f_{1} (x) = \sum_{m \in {0, \dots, N}^{d}} \sum_{n : | n | < n} a_{m, n} ϕ_{m} (x) {(x - \frac{m}{N})}^{n} .$ The expansion is a linear combination of not more than $d^{n} {(N + 1)}^{d}$ terms $ϕ_{m} (x) {(x - \frac{m}{N})}^{n}$ . Each of these terms is a product of at most $d + n - 1$ piece-wise linear univariate factors: $d$ functions $ψ (3 N x_{k} - 3 m_{k})$ (see (5)) and at most $n - 1$ linear expressions $x_{k} - \frac{m_{k}}{N}$ . We can implement an approximation of this product by a neural network with the help of Proposition 3. Specifically, let $\tilde{\times}$ be the approximate multiplication from Proposition 3 for $M = d + n$ and some accuracy $δ$ to be chosen later, and consider the approximation of the product $ϕ_{m} (x) {(x - \frac{m}{N})}^{n}$ obtained by the chained application of $\tilde{\times}$ : (14) ${\tilde{f}}_{m, n} (x) = \tilde{\times} (ψ (3 N x_{1} - 3 m_{1}), \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \dots, \tilde{\times} (x_{k} - \frac{m_{k}}{N}, \dots) \dots)) .$ Using statement (c) of Proposition 3, we see that ${\tilde{f}}_{m, n}$ can be implemented by a ReLU network with the depth and the number of weights and computation units not larger than $(d + n) c_{1} ln (1 ∕ δ)$ , for some constant $c_{1} = c_{1} (d, n)$ .
将 $f_{1}$ 展开为 (13) $f_{1} (x) = \sum_{m \in {0, \dots, N}^{d}} \sum_{n : | n | < n} a_{m, n} ϕ_{m} (x) {(x - \frac{m}{N})}^{n} .$ 展开是不超过 $d^{n} {(N + 1)}^{d}$ 项 $ϕ_{m} (x) {(x - \frac{m}{N})}^{n}$ 的线性组合。每个项都是最多 $d + n - 1$ 个片断线性单变量因子的乘积： $d$ 函数 $ψ (3 N x_{k} - 3 m_{k})$ （见 (5)）和最多 $n - 1$ 线性表达式 $x_{k} - \frac{m_{k}}{N}$ 的乘积。在命题 3 的帮助下，我们可以用神经网络实现对这个乘积的逼近。具体来说，假设 $\tilde{\times}$ 是命题 3 中 $M = d + n$ 的近似乘法和稍后选择的某个精度 $δ$ ，并考虑由 $\tilde{\times}$ 的链式应用得到的乘积 $ϕ_{m} (x) {(x - \frac{m}{N})}^{n}$ 的近似值： (14) ${\tilde{f}}_{m, n} (x) = \tilde{\times} (ψ (3 N x_{1} - 3 m_{1}), \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \dots, \tilde{\times} (x_{k} - \frac{m_{k}}{N}, \dots) \dots)) .$ 利用命题 3 的陈述（c），我们可以看到 ${\tilde{f}}_{m, n}$ 可以由一个 ReLU 网络来实现，其深度和权值以及计算单元的数量不大于 $(d + n) c_{1} ln (1 ∕ δ)$ ，对于某个常数 $c_{1} = c_{1} (d, n)$ 。

Now we estimate the error of this approximation. Note that we have $| ψ (3 N x_{k} - 3 m_{k}) | \leq 1$ and $| x_{k} - \frac{m_{k}}{N} | \leq 1$ for all $k$ and all $x \in {[0, 1]}^{d}$ . By statement (a) of Proposition 3, if $| a | \leq 1$ and $| b | \leq M$ , then $| \tilde{\times} (a, b) | \leq | b | + δ$ . Repeatedly applying this observation to all approximate multiplications in (14) while assuming $δ < 1$ , we see that the arguments of all these multiplications are bounded by our $M$ (equal to $d + n$ ) and the statement (a) of Proposition 3 holds for each of them. We then have (15) $| {\tilde{f}}_{m, n} (x) - ϕ_{m} (x) {(x - \frac{m}{N})}^{n} | = | \tilde{\times} (ψ (3 N x_{1} - 3 m_{1}), \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots))) - ψ (3 N x_{1} - 3 m_{1}) ψ (3 N x_{2} - 3 m_{2}) ψ (3 N x_{3} - 3 m_{3}) \dots | \leq | \tilde{\times} (ψ (3 N x_{1} - 3 m_{1}), \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots))) - ψ (3 N x_{1} - 3 m_{1}) \cdot \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots)) | + | ψ (3 N x_{1} - 3 m_{1}) | \cdot | \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots)) - ψ (3 N x_{2} - 3 m_{2}) \cdot \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots) | + \dots \leq (d + n) δ .$ Moreover, by statement (b) of Proposition 3, (16) ${\tilde{f}}_{m, n} (x) = ϕ_{m} (x) {(x - \frac{m}{N})}^{n}, x ⁄ \in supp ϕ_{m} .$ Now we define the full approximation by (17) $\tilde{f} = \sum_{m \in {0, \dots, N}^{d}} \sum_{n : | n | < n} a_{m, n} {\tilde{f}}_{m, n} .$ We estimate the approximation error of $\tilde{f}$ : $| \tilde{f} (x) - f_{1} (x) | = | \sum_{m \in {0, \dots, N}^{d}} \sum_{n : | n | < n} a_{m, n} ({\tilde{f}}_{m, n} (x) - ϕ_{m} (x) {(x - \frac{m}{N})}^{n}) | = | \sum_{m : x \in supp ϕ_{m}} \sum_{n : | n | < n} a_{m, n} ({\tilde{f}}_{m, n} (x) - ϕ_{m} (x) {(x - \frac{m}{N})}^{n}) | \leq 2^{d} max_{m : x \in supp ϕ_{m}} \sum_{n : | n | < n} | {\tilde{f}}_{m, n} (x) - ϕ_{m} (x) {(x - \frac{m}{N})}^{n} | \leq 2^{d} d^{n} (d + n) δ,$ where in the first step we use expansion (13), in the second the identity (16), in the third the bound $| a_{m, n} | \leq 1$ and the fact that $x \in supp ϕ_{m}$ for at most $2^{d}$ functions $ϕ_{m}$ , and in the fourth the bound (15). It follows that if we choose (18) $δ = \frac{ϵ}{2^{d + 1} d^{n} (d + n)},$ then $‖ \tilde{f} - f_{1} ‖_{\infty} \leq \frac{ϵ}{2}$ and hence, by (11), $‖ \tilde{f} - f ‖_{\infty} \leq ‖ \tilde{f} - f_{1} ‖_{\infty} + ‖ f_{1} - f ‖_{\infty} \leq \frac{ϵ}{2} + \frac{ϵ}{2} \leq ϵ .$
现在我们来估算这个近似值的误差。请注意，对于所有 $k$ 和所有 $x \in {[0, 1]}^{d}$ ，我们都有 $| ψ (3 N x_{k} - 3 m_{k}) | \leq 1$ 和 $| x_{k} - \frac{m_{k}}{N} | \leq 1$ 。根据命题 3 的陈述 (a)，如果 $| a | \leq 1$ 和 $| b | \leq M$ ，那么 $| \tilde{\times} (a, b) | \leq | b | + δ$ 。在假设 $δ < 1$ 的情况下，将这一观察结果重复应用于 (14) 中的所有近似乘法，我们会发现所有这些乘法的参数都以我们的 $M$ 为界（等于 $d + n$ ），并且命题 3 的陈述 (a) 对它们中的每一个都成立。因此，我们有 (15) $| {\tilde{f}}_{m, n} (x) - ϕ_{m} (x) {(x - \frac{m}{N})}^{n} | = | \tilde{\times} (ψ (3 N x_{1} - 3 m_{1}), \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots))) - ψ (3 N x_{1} - 3 m_{1}) ψ (3 N x_{2} - 3 m_{2}) ψ (3 N x_{3} - 3 m_{3}) \dots | \leq | \tilde{\times} (ψ (3 N x_{1} - 3 m_{1}), \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots))) - ψ (3 N x_{1} - 3 m_{1}) \cdot \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots)) | + | ψ (3 N x_{1} - 3 m_{1}) | \cdot | \tilde{\times} (ψ (3 N x_{2} - 3 m_{2}), \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots)) - ψ (3 N x_{2} - 3 m_{2}) \cdot \tilde{\times} (ψ (3 N x_{3} - 3 m_{3}), \dots) | + \dots \leq (d + n) δ .$ 而且，根据命题 3 的陈述 (b)， (16) ${\tilde{f}}_{m, n} (x) = ϕ_{m} (x) {(x - \frac{m}{N})}^{n}, x ⁄ \in supp ϕ_{m} .$ 现在我们用 (17) $\tilde{f} = \sum_{m \in {0, \dots, N}^{d}} \sum_{n : | n | < n} a_{m, n} {\tilde{f}}_{m, n} .$ 来定义完全近似，我们估计 $\tilde{f}$ 的近似误差： $| \tilde{f} (x) - f_{1} (x) | = | \sum_{m \in {0, \dots, N}^{d}} \sum_{n : | n | < n} a_{m, n} ({\tilde{f}}_{m, n} (x) - ϕ_{m} (x) {(x - \frac{m}{N})}^{n}) | = | \sum_{m : x \in supp ϕ_{m}} \sum_{n : | n | < n} a_{m, n} ({\tilde{f}}_{m, n} (x) - ϕ_{m} (x) {(x - \frac{m}{N})}^{n}) | \leq 2^{d} max_{m : x \in supp ϕ_{m}} \sum_{n : | n | < n} | {\tilde{f}}_{m, n} (x) - ϕ_{m} (x) {(x - \frac{m}{N})}^{n} | \leq 2^{d} d^{n} (d + n) δ,$ 其中第一步我们使用扩展 (13)，第二步使用特性 (16)，第三步使用约束 $| a_{m, n} | \leq 1$ 和 $x \in supp ϕ_{m}$ 对于最多 $2^{d}$ 的函数 $ϕ_{m}$ 的事实，第四步使用约束 (15)。由此可见，如果我们选择 (18) $δ = \frac{ϵ}{2^{d + 1} d^{n} (d + n)},$ ，那么 $‖ \tilde{f} - f_{1} ‖_{\infty} \leq \frac{ϵ}{2}$ ，因此，根据 (11)， $‖ \tilde{f} - f ‖_{\infty} \leq ‖ \tilde{f} - f_{1} ‖_{\infty} + ‖ f_{1} - f ‖_{\infty} \leq \frac{ϵ}{2} + \frac{ϵ}{2} \leq ϵ .$

On the other hand, note that by (17), $\tilde{f}$ can be implemented by a network consisting of parallel subnetworks that compute each of ${\tilde{f}}_{m, n}$ ; the final output is obtained by weighting the outputs of the subnetworks with the weights $a_{m, n}$ . The architecture of the full network does not depend on $f$ ; only the weights $a_{m, n}$ do. As already shown, each of these subnetworks has not more than $c_{1} ln (1 ∕ δ)$ layers, weights and computation units, with some constant $c_{1} = c_{1} (d, n)$ . There are not more than $d^{n} {(N + 1)}^{d}$ such subnetworks. Therefore, the full network for $\tilde{f}$ has not more than $c_{1} ln (1 ∕ δ) + 1$ layers and $d^{n} {(N + 1)}^{d} (c_{1} ln (1 ∕ δ) + 1)$ weights and computation units. With $δ$ given by (18) and $N$ given by (10), we obtain the claimed complexity bounds. □
另一方面，请注意，根据 (17)， $\tilde{f}$ 可以通过一个由并行子网络组成的网络来实现，子网络计算 ${\tilde{f}}_{m, n}$ 中的每一条；最终输出由子网络的输出与权重 $a_{m, n}$ 加权得到。整个网络的结构与 $f$ 无关，只与权重 $a_{m, n}$ 有关。如前所述，每个子网络的层数、权重和计算单元都不超过 $c_{1} ln (1 ∕ δ)$ ，且有一定的常数 $c_{1} = c_{1} (d, n)$ 。这样的子网络不会超过 $d^{n} {(N + 1)}^{d}$ 。因此， $\tilde{f}$ 的完整网络的层数不超过 $c_{1} ln (1 ∕ δ) + 1$ ，权重和计算单元不超过 $d^{n} {(N + 1)}^{d} (c_{1} ln (1 ∕ δ) + 1)$ 。根据 (18) 所给出的 $δ$ 和 (10) 所给出的 $N$ ，我们得到了所宣称的复杂度边界。□

We remark that an analog of Theorem 1 for so-called $k$ ’th order activation functions with $k \geq 2$ can be found in Mhaskar (1993).
我们要指出的是，定理 1 与所谓的 $k$ 'th 阶激活函数 $k \geq 2$ 的类似，可以在 Mhaskar (1993) 中找到。

3.3. Faster approximations using adaptive network architectures
3.3.利用自适应网络架构实现更快近似

Theorem 1 provides an upper bound for the approximation complexity in the case when the same network architecture is used to approximate all functions in $F_{d, n}$ . We can consider an alternative, “adaptive architecture” scenario where not only the weights, but also the architecture is adjusted to the approximated function. We expect, of course, that this would decrease the complexity of the resulting architectures, in general (at the price of needing to find the appropriate architecture). In this section we show that we can indeed obtain better upper bounds in this scenario.
定理 1 提供了使用相同网络架构逼近 $F_{d, n}$ 中所有函数时的逼近复杂度上限。我们可以考虑另一种 "自适应架构 "方案，即根据近似函数调整权重和架构。当然，我们预计这将在总体上降低由此产生的架构的复杂性（代价是需要找到合适的架构）。在本节中，我们将展示在这种情况下我们确实可以获得更好的上限。

For simplicity, we will only consider the case $d = n = 1$ . Then, $W^{n, \infty} ({[0, 1]}^{d})$ is the space of Lipschitz functions on the segment $[0, 1]$ . The set $F_{1, 1}$ consists of functions $f$ having both $‖ f ‖_{\infty}$ and the Lipschitz constant bounded by 1. Theorem 1 provides an upper bound $O (\frac{ln (1 ∕ ϵ)}{ϵ})$ for the number of weights and computation units, but in this special case there is in fact a better bound $O (\frac{1}{ϵ})$ obtained simply by piece-wise interpolation.
为简单起见，我们只考虑 $d = n = 1$ 的情况。然后， $W^{n, \infty} ({[0, 1]}^{d})$ 是线段 $[0, 1]$ 上的 Lipschitz 函数空间。定理 1 为权重和计算单元的数量提供了一个上限 $O (\frac{ln (1 ∕ ϵ)}{ϵ})$ ，但在这种特殊情况下，实际上有一个更好的上限 $O (\frac{1}{ϵ})$ ，只需通过分段插值即可获得。

Namely, given $f \in F_{1, 1}$ and $ϵ > 0$ , set $T = ⌈ \frac{1}{ϵ} ⌉$ and let $\tilde{f}$ be the piece-wise interpolation of $f$ with $T + 1$ uniformly spaced breakpoints ${(\frac{t}{T})}_{t = 0}^{T}$ (i.e., $\tilde{f} (\frac{t}{T}) = f (\frac{t}{T}), t = 0, \dots, T$ ). The function $\tilde{f}$ is also Lipschitz with constant 1 and hence $‖ f - \tilde{f} ‖_{\infty} \leq \frac{1}{T} \leq ϵ$ (since for any $x \in [0, 1]$ we can find $t$ such that $| x - \frac{t}{T} | \leq \frac{1}{2 T}$ and then $| f (x) - \tilde{f} (x) | \leq | f (x) - f (\frac{t}{T}) | + | \tilde{f} (\frac{t}{T}) - \tilde{f} (x) | \leq 2 \cdot \frac{1}{2 T} = \frac{1}{T}$ ). At the same time, the function $\tilde{f}$ can be expressed in terms of the ReLU function $σ$ by $\tilde{f} (x) = b + \sum_{t = 0}^{T - 1} w_{t} σ (x - \frac{t}{T})$ with some coefficients $b$ and ${(w_{t})}_{t = 0}^{T - 1}$ . This expression can be viewed as a special case of the depth-3 ReLU network with $O (\frac{1}{ϵ})$ weights and computation units.
即，给定 $f \in F_{1, 1}$ 和 $ϵ > 0$ ，设 $T = ⌈ \frac{1}{ϵ} ⌉$ ，让 $\tilde{f}$ 是 $f$ 与 $T + 1$ 均匀间隔的断点 ${(\frac{t}{T})}_{t = 0}^{T}$ 的片断插值（即 $\tilde{f} (\frac{t}{T}) = f (\frac{t}{T}), t = 0, \dots, T$ ）。函数 $\tilde{f}$ 也是常数为 1 的 Lipschitz 函数，因此 $‖ f - \tilde{f} ‖_{\infty} \leq \frac{1}{T} \leq ϵ$ 也是 Lipschitz 函数（因为对于任意 $x \in [0, 1]$ ，我们都可以找到 $t$ ，这样 $| x - \frac{t}{T} | \leq \frac{1}{2 T}$ 和 $| f (x) - \tilde{f} (x) | \leq | f (x) - f (\frac{t}{T}) | + | \tilde{f} (\frac{t}{T}) - \tilde{f} (x) | \leq 2 \cdot \frac{1}{2 T} = \frac{1}{T}$ 都是 Lipschitz 函数）。同时，函数 $\tilde{f}$ 可以用 ReLU 函数 $σ$ 表示，即 $\tilde{f} (x) = b + \sum_{t = 0}^{T - 1} w_{t} σ (x - \frac{t}{T})$ 加上一些系数 $b$ 和 ${(w_{t})}_{t = 0}^{T - 1}$ 。这个表达式可以看作是具有 $O (\frac{1}{ϵ})$ 权重和计算单元的深度-3 ReLU 网络的特例。

We show now how the bound $O (\frac{1}{ϵ})$ can be improved by using adaptive architectures.
现在，我们将展示如何通过使用自适应架构来改进 $O (\frac{1}{ϵ})$ 约束。

Theorem 2 定理 2

For any $f \in F_{1, 1}$ and $ϵ \in (0, \frac{1}{2})$ , there exists a depth- 6 ReLU network $η$ (with architecture depending on $f$ ) that provides an $ϵ$ -approximation of $f$ while having not more than $\frac{c}{ϵ ln (1 ∕ ϵ)}$ weights, connections and computation units. Here $c$ is an absolute constant.
对于任意的 $f \in F_{1, 1}$ 和 $ϵ \in (0, \frac{1}{2})$ ，存在一个深度为 6 的 ReLU 网络 $η$ （其结构取决于 $f$ ），它提供了 $ϵ$ - $f$ 的近似值，同时权重、连接和计算单元不超过 $\frac{c}{ϵ ln (1 ∕ ϵ)}$ 。这里的 $c$ 是一个绝对常数。

Proof 证明

We first explain the idea of the proof. We start with interpolating $f$ by a piece-wise linear function, but not on the length scale $ϵ$ —instead, we do it on a coarser length scale $m ϵ$ , with some $m = m (ϵ) > 1$ . We then create a “cache” of auxiliary subnetworks that we use to fill in the details and go down to the scale $ϵ$ , in each of the $m ϵ$ -subintervals. This allows us to reduce the amount of computations for small $ϵ$ because the complexity of the cache only depends on $m$ . The assignment of cached subnetworks to the subintervals is encoded in the network architecture and depends on the function $f$ . We optimize $m$ by balancing the complexity of the cache with that of the initial coarse approximation. This leads to $m \sim ln (1 ∕ ϵ)$ and hence to the reduction of the total complexity of the network by a factor $\sim ln (1 ∕ ϵ)$ compared to the simple piece-wise linear approximation on the scale $ϵ$ . This construction is inspired by a similar argument used to prove the $O (2^{n} ∕ n)$ upper bound for the complexity of Boolean circuits implementing $n$ -ary functions (Shannon, 1949).
我们首先解释一下证明的思路。我们先用一个片断线性函数对 $f$ 进行插值，但不是在长度尺度 $ϵ$ 上进行，而是在更粗的长度尺度 $m ϵ$ 上进行，其中包含一些 $m = m (ϵ) > 1$ 。然后，我们会创建一个辅助子网的 "缓存"，用来填补细节，并在每个 $m ϵ$ - 子区间内细化到 $ϵ$ 的尺度。这使我们能够减少小 $ϵ$ 的计算量，因为缓存的复杂度只取决于 $m$ 。缓存子网络到子区间的分配在网络结构中编码，并取决于函数 $f$ 。我们通过平衡缓存的复杂度和初始粗略近似的复杂度来优化 $m$ 。这导致了 $m \sim ln (1 ∕ ϵ)$ ，因此，与规模为 $ϵ$ 的简单片断线性近似相比，网络的总复杂度降低了 $\sim ln (1 ∕ ϵ)$ 。这种构造的灵感来源于证明实现 $n$ -ary 函数的布尔电路复杂度上限 $O (2^{n} ∕ n)$ 的类似论证（香农，1949 年）。

The proof becomes simpler if, in addition to the ReLU function $σ$ , we are allowed to use the activation function (19) $ρ (x) = \{\begin{matrix} x, & x \in [0, 1), \\ 0, & x ⁄ \in [0, 1) \end{matrix}$ in our neural network. Since $ρ$ is discontinuous, we cannot just use Proposition 1 to replace $ρ$ -units by $σ$ -units. We will first prove the analog of the claimed result for the model including $ρ$ -units, and then we will show how to construct a purely ReLU network.
如果除了 ReLU 函数 $σ$ 之外，我们还可以在神经网络中使用激活函数 (19) $ρ (x) = \{\begin{matrix} x, & x \in [0, 1), \\ 0, & x ⁄ \in [0, 1) \end{matrix}$ ，那么证明就变得更简单了。由于 $ρ$ 是不连续的，我们不能直接用命题 1 将 $ρ$ 单位替换为 $σ$ 单位。我们将首先证明包含 $ρ$ 单位的模型的类似结果，然后再展示如何构建一个纯 ReLU 网络。

Lemma 1 例题 1

For any $f \in F_{1, 1}$ and $ϵ \in (0, \frac{1}{2})$ , there exists a depth-5 network including $σ$ -units and $ρ$ -units, that provides an $ϵ$ -approximation of $f$ while having not more than $\frac{c}{ϵ ln (1 ∕ ϵ)}$ weights, where $c$ is an absolute constant.
对于任意的 $f \in F_{1, 1}$ 和 $ϵ \in (0, \frac{1}{2})$ ，存在一个深度为 5 的网络，其中包括 $σ$ - 单元和 $ρ$ - 单元，它提供了 $ϵ$ - $f$ 的近似值，同时权重不超过 $\frac{c}{ϵ ln (1 ∕ ϵ)}$ ，其中 $c$ 是一个绝对常量。

Proof 证明

Given $f \in F_{1, 1}$ , we will construct an approximation $\tilde{f}$ to $f$ in the form $\tilde{f} = {\tilde{f}}_{1} + {\tilde{f}}_{2} .$ Here, ${\tilde{f}}_{1}$ is the piece-wise linear interpolation of $f$ with the breakpoints ${\frac{t}{T}}_{t = 0}^{T}$ , for some positive integer $T$ to be chosen later. Since $f$ is Lipschitz with constant 1, ${\tilde{f}}_{1}$ is also Lipschitz with constant 1. We will denote by $I_{t}$ the intervals between the breakpoints: $I_{t} = [\frac{t}{T}, \frac{t + 1}{T}), t = 0, \dots, T - 1 .$ We will now construct ${\tilde{f}}_{2}$ as an approximation to the difference (20) $f_{2} = f - {\tilde{f}}_{1} .$ Note that $f_{2}$ vanishes at the endpoints of the intervals $I_{t}$ : (21) $f_{2} (\frac{t}{T}) = 0, t = 0, \dots, T,$ and $f_{2}$ is Lipschitz with constant 2: (22) $| f_{2} (x_{1}) - f_{2} (x_{2}) | \leq 2 | x_{1} - x_{2} |,$ since $f$ and ${\tilde{f}}_{1}$ are Lipschitz with constant 1.
给定 $f \in F_{1, 1}$ ，我们将以 $\tilde{f} = {\tilde{f}}_{1} + {\tilde{f}}_{2} .$ 的形式构建 $\tilde{f}$ 与 $f$ 的近似值 ${\tilde{f}}_{1}$ 是 $f$ 与断点 ${\frac{t}{T}}_{t = 0}^{T}$ 的片断线性插值，对于某个正整数 $T$ 待定。由于 $f$ 是常数为 1 的 Lipschitz，所以 ${\tilde{f}}_{1}$ 也是常数为 1 的 Lipschitz。我们用 $I_{t}$ 表示断点之间的间隔： $I_{t} = [\frac{t}{T}, \frac{t + 1}{T}), t = 0, \dots, T - 1 .$ 现在我们将构建 ${\tilde{f}}_{2}$ 作为差值 (20) $f_{2} = f - {\tilde{f}}_{1} .$ 的近似值，注意 $f_{2}$ 在区间 $I_{t}$ ： (21) $f_{2} (\frac{t}{T}) = 0, t = 0, \dots, T,$ 和 $f_{2}$ 是常数为 2 的 Lipschitz： (22) $| f_{2} (x_{1}) - f_{2} (x_{2}) | \leq 2 | x_{1} - x_{2} |,$ 因为 $f$ 和 ${\tilde{f}}_{1}$ 是常数为 1 的 Lipschitz。

To define ${\tilde{f}}_{2}$ , we first construct a set $Γ$ of cached functions. Let $m$ be a positive integer to be chosen later. Let $Γ$ be the set of piecewise linear functions $γ : [0, 1] \to R$ with the breakpoints ${\frac{r}{m}}_{r = 0}^{m}$ and the properties $γ (0) = γ (1) = 0$ and $γ (\frac{r}{m}) - γ (\frac{r - 1}{m}) \in {- \frac{2}{m}, 0, \frac{2}{m}}, r = 1, \dots, m .$ Note that the size $| Γ |$ of $Γ$ is not larger than $3^{m}$ .
要定义 ${\tilde{f}}_{2}$ ，我们首先要构建一个缓存函数集 $Γ$ 。让 $m$ 为稍后选择的正整数。让 $Γ$ 成为具有断点 ${\frac{r}{m}}_{r = 0}^{m}$ 和属性 $γ (0) = γ (1) = 0$ 及 $γ (\frac{r}{m}) - γ (\frac{r - 1}{m}) \in {- \frac{2}{m}, 0, \frac{2}{m}}, r = 1, \dots, m .$ 的片断线性函数集合 $γ : [0, 1] \to R$ 注意 $Γ$ 的大小 $| Γ |$ 不大于 $3^{m}$ 。

If $g : [0, 1] \to R$ is any Lipschitz function with constant 2 and $g (0) = g (1) = 0$ , then $g$ can be approximated by some $γ \in Γ$ with error not larger than $\frac{2}{m}$ : namely, take $γ (\frac{r}{m}) = \frac{2}{m} ⌊ g (\frac{r}{m}) ∕ \frac{2}{m} ⌋$ .
如果 $g : [0, 1] \to R$ 是常数为 2 的任意 Lipschitz 函数，且 $g (0) = g (1) = 0$ ，那么 $g$ 可以用误差不大于 $\frac{2}{m}$ 的某个 $γ \in Γ$ 近似：即取 $γ (\frac{r}{m}) = \frac{2}{m} ⌊ g (\frac{r}{m}) ∕ \frac{2}{m} ⌋$ 。

Moreover, if $f_{2}$ is defined by (20), then, using (21), (22), on each interval $I_{t}$ the function $f_{2}$ can be approximated with error not larger than $\frac{2}{T m}$ by a properly rescaled function $γ \in Γ$ . Namely, for each $t = 0, \dots, T - 1$ we can define the function $g$ by $g (y) = T f_{2} (\frac{t + y}{T})$ . Then it is Lipschitz with constant 2 and $g (0) = g (1) = 0$ , so we can find $γ_{t} \in Γ$ such that $sup_{y \in [0, 1)} | T f_{2} (\frac{t + y}{T}) - γ_{t} (y) | \leq \frac{2}{m} .$ This can be equivalently written as $sup_{x \in I_{t}} | f_{2} (x) - \frac{1}{T} γ_{t} (T x - t) | \leq \frac{2}{T m} .$ Note that the obtained assignment $t \mapsto γ_{t}$ is not injective, in general ( $T$ will be larger than $| Γ |$ ).
此外，如果 $f_{2}$ 由 (20) 定义，那么，利用 (21)、(22)，在每个区间 $I_{t}$ 上，函数 $f_{2}$ 可以用一个适当重标的函数 $γ \in Γ$ 近似，误差不大于 $\frac{2}{T m}$ 。也就是说，对于每个 $t = 0, \dots, T - 1$ ，我们可以用 $g (y) = T f_{2} (\frac{t + y}{T})$ 来定义函数 $g$ 。那么它是常数为 2 的 Lipschitz 函数和 $g (0) = g (1) = 0$ ，所以我们可以找到 $γ_{t} \in Γ$ 使得 $sup_{y \in [0, 1)} | T f_{2} (\frac{t + y}{T}) - γ_{t} (y) | \leq \frac{2}{m} .$ 可以等价地写成 $sup_{x \in I_{t}} | f_{2} (x) - \frac{1}{T} γ_{t} (T x - t) | \leq \frac{2}{T m} .$ 注意得到的赋值 $t \mapsto γ_{t}$ 一般来说不是注入式的（ $T$ 将大于 $| Γ |$ ）。

We can then define ${\tilde{f}}_{2}$ on the whole $[0, 1)$ by (23) ${\tilde{f}}_{2} (x) = \frac{1}{T} γ_{t} (T x - t), x \in I_{t}, t = 0, \dots, T - 1 .$ This ${\tilde{f}}_{2}$ approximates $f_{2}$ with error $\frac{2}{T m}$ on $[0, 1)$ : (24) $sup_{x \in [0, 1)} | f_{2} (x) - {\tilde{f}}_{2} (x) | \leq \frac{2}{T m},$ and hence, by (20), for the full approximation $\tilde{f} = {\tilde{f}}_{1} + {\tilde{f}}_{2}$ we will also have (25) $sup_{x \in [0, 1)} | f (x) - \tilde{f} (x) | \leq \frac{2}{T m} .$ Note that the approximation ${\tilde{f}}_{2}$ has properties analogous to (21), (22) : (26) ${\tilde{f}}_{2} (\frac{t}{T}) = 0, t = 0, \dots, T,$ (27) $| {\tilde{f}}_{2} (x_{1}) - {\tilde{f}}_{2} (x_{2}) | \leq 2 | x_{1} - x_{2} |,$ in particular, ${\tilde{f}}_{2}$ is continuous on $[0, 1)$ .
我们可以通过 (23) ${\tilde{f}}_{2} (x) = \frac{1}{T} γ_{t} (T x - t), x \in I_{t}, t = 0, \dots, T - 1 .$ 在 $[0, 1)$ 上定义 ${\tilde{f}}_{2}$ 这个 ${\tilde{f}}_{2}$ 以 $\frac{2}{T m}$ 的误差近似 $f_{2}$ 在 $[0, 1)$ ： (24) $sup_{x \in [0, 1)} | f_{2} (x) - {\tilde{f}}_{2} (x) | \leq \frac{2}{T m},$ 因此，根据 (20)，对于完整的近似值 $\tilde{f} = {\tilde{f}}_{1} + {\tilde{f}}_{2}$ 我们也将有 (25) $sup_{x \in [0, 1)} | f (x) - \tilde{f} (x) | \leq \frac{2}{T m} .$ 注意，近似值 ${\tilde{f}}_{2}$ 具有类似于 (21)、(22) 的性质： (26) ${\tilde{f}}_{2} (\frac{t}{T}) = 0, t = 0, \dots, T,$ (27) $| {\tilde{f}}_{2} (x_{1}) - {\tilde{f}}_{2} (x_{2}) | \leq 2 | x_{1} - x_{2} |,$ 特别是， ${\tilde{f}}_{2}$ 在 $[0, 1)$ 上是连续的。

We will now rewrite ${\tilde{f}}_{2}$ in a different form interpretable as a computation by a neural network. Specifically, using our additional activation function $ρ$ given by (19), we can express ${\tilde{f}}_{2}$ as (28) ${\tilde{f}}_{2} (x) = \frac{1}{T} \sum_{γ \in Γ} γ (\sum_{t : γ_{t} = γ} ρ (T x - t)) .$ Indeed, given $x \in [0, 1)$ , observe that all the terms in the inner sum vanish except for the one corresponding to the $t$ determined by the condition $x \in I_{t}$ . For this particular $t$ we have $ρ (T x - t) = T x - t$ . Since $γ (0) = 0$ , we conclude that (28) agrees with (23).
现在，我们将以另一种形式重写 ${\tilde{f}}_{2}$ ，将其解释为神经网络的计算。具体地说，利用（19）给出的附加激活函数 $ρ$ ，我们可以将 ${\tilde{f}}_{2}$ 表达为 (28) ${\tilde{f}}_{2} (x) = \frac{1}{T} \sum_{γ \in Γ} γ (\sum_{t : γ_{t} = γ} ρ (T x - t)) .$ 事实上，在给出 $x \in [0, 1)$ 的情况下，除了与条件 $x \in I_{t}$ 确定的 $t$ 相对应的项之外，观察到内和中的所有项都消失了。对于这个特殊的 $t$ ，我们有 $ρ (T x - t) = T x - t$ 。由于 $γ (0) = 0$ ，我们得出结论 (28) 与 (23) 一致。

Let us also expand $γ \in Γ$ over the basis of shifted ReLU functions: $γ (x) = \sum_{r = 0}^{m - 1} c_{γ, r} σ (x - \frac{r}{m}), x \in [0, 1] .$ Substituting this expansion in (28), we finally obtain (29) ${\tilde{f}}_{2} (x) = \frac{1}{T} \sum_{γ \in Γ} \sum_{r = 0}^{m - 1} c_{γ, r} σ (\sum_{t : γ_{t} = γ} ρ (T x - t) - \frac{r}{m}) .$
我们还可以在移位 ReLU 函数的基础上展开 $γ \in Γ$ ： $γ (x) = \sum_{r = 0}^{m - 1} c_{γ, r} σ (x - \frac{r}{m}), x \in [0, 1] .$ 将这一扩展代入 (28)，我们最终得到 (29) ${\tilde{f}}_{2} (x) = \frac{1}{T} \sum_{γ \in Γ} \sum_{r = 0}^{m - 1} c_{γ, r} σ (\sum_{t : γ_{t} = γ} ρ (T x - t) - \frac{r}{m}) .$

Now consider the implementation of $\tilde{f}$ by a neural network. The term ${\tilde{f}}_{1}$ can clearly be implemented by a depth-3 ReLU network using $O (T)$ connections and computation units. The term ${\tilde{f}}_{2}$ can be implemented by a depth-5 network with $ρ$ - and $σ$ -units as follows (we denote a computation unit by $Q$ with a superscript indexing the layer and a subscript indexing the unit within the layer).
现在考虑用神经网络来实现 $\tilde{f}$ 。项 ${\tilde{f}}_{1}$ 显然可以用深度为 3 的 ReLU 网络，使用 $O (T)$ 连接和计算单元来实现。术语 ${\tilde{f}}_{2}$ 可以通过深度-5 网络使用 $ρ$ - 和 $σ$ - 单元来实现（我们用 $Q$ 表示计算单元，上标表示层，下标表示层内单元）。

1.
The first layer contains the single input unit $Q^{(1)}$ .
第一层包含单输入单元 $Q^{(1)}$ 。
2.
The second layer contains $T$ units ${(Q_{t}^{(2)})}_{t = 1}^{T}$ computing $Q_{t}^{(2)} = ρ (T Q^{(1)} - t) .$
第二层包含 $T$ 单元 ${(Q_{t}^{(2)})}_{t = 1}^{T}$ 计算 $Q_{t}^{(2)} = ρ (T Q^{(1)} - t) .$
3.
The third layer contains $| Γ |$ units ${(Q_{γ}^{(3)})}_{γ \in Γ}$ computing $Q_{γ}^{(3)} = σ (\sum_{t : γ_{t} = γ} Q_{t}^{(2)})$ . This is equivalent to $Q_{γ}^{(3)} = \sum_{t : γ_{t} = γ} Q_{t}^{(2)}$ , because $Q_{t}^{(2)} \geq 0$ .
第三层包含 $| Γ |$ 单元 ${(Q_{γ}^{(3)})}_{γ \in Γ}$ 计算 $Q_{γ}^{(3)} = σ (\sum_{t : γ_{t} = γ} Q_{t}^{(2)})$ 。这相当于 $Q_{γ}^{(3)} = \sum_{t : γ_{t} = γ} Q_{t}^{(2)}$ ，因为 $Q_{t}^{(2)} \geq 0$ .
4.
The fourth layer contains $m | Γ |$ units ${(Q_{γ, r}^{(4)})}_{\overset{γ \in Γ}{r = 0, \dots, m - 1}}$ computing $Q_{γ, r}^{(4)} = σ (Q_{γ}^{(3)} - \frac{r}{m}) .$
第四层包含 $m | Γ |$ 单元 ${(Q_{γ, r}^{(4)})}_{\overset{γ \in Γ}{r = 0, \dots, m - 1}}$ 计算 $Q_{γ, r}^{(4)} = σ (Q_{γ}^{(3)} - \frac{r}{m}) .$
5.
The final layer consists of a single output unit $Q^{(5)} = \sum_{γ \in Γ} \sum_{r = 0}^{m - 1} \frac{c_{γ, r}}{T} Q_{γ, r}^{(4)} .$
最后一层由一个输出单元 $Q^{(5)} = \sum_{γ \in Γ} \sum_{r = 0}^{m - 1} \frac{c_{γ, r}}{T} Q_{γ, r}^{(4)} .$ 组成

Examining this network, we see that the total number of connections and units in it is $O (T + m | Γ |)$ and hence is $O (T + m 3^{m})$ . This also holds for the full network implementing $\tilde{f} = {\tilde{f}}_{1} + {\tilde{f}}_{2}$ , since the term ${\tilde{f}}_{1}$ requires even fewer layers, connections and units. The output units of the subnetworks for ${\tilde{f}}_{1}$ and ${\tilde{f}}_{2}$ can be merged into the output unit for ${\tilde{f}}_{1} + {\tilde{f}}_{2}$ , so the depth of the full network is the maximum of the depths of the networks implementing ${\tilde{f}}_{1}$ and ${\tilde{f}}_{2}$ , i.e., is 5 (see Fig. 4).
观察这个网络，我们会发现其中连接和单元的总数是 $O (T + m | Γ |)$ ，因此是 $O (T + m 3^{m})$ 。这同样适用于实现 $\tilde{f} = {\tilde{f}}_{1} + {\tilde{f}}_{2}$ 的完整网络，因为 ${\tilde{f}}_{1}$ 项所需的层数、连接数和单元数都更少。 ${\tilde{f}}_{1}$ 和 ${\tilde{f}}_{2}$ 子网络的输出单元可以合并到 ${\tilde{f}}_{1} + {\tilde{f}}_{2}$ 的输出单元中，因此整个网络的深度是实现 ${\tilde{f}}_{1}$ 和 ${\tilde{f}}_{2}$ 的网络深度的最大值，即 5（见图 4）。

Now, given $ϵ \in (0, \frac{1}{2})$ , take $m = ⌈ \frac{1}{2} {log}_{3} (1 ∕ ϵ) ⌉$ and $T = ⌈ \frac{2}{m ϵ} ⌉$ . Then, by (25), the approximation error ${max}_{x \in [0, 1]} | f (x) - \tilde{f} (x) | \leq \frac{2}{T m} \leq ϵ$ , while $T + m 3^{m} = O (\frac{1}{ϵ ln (1 ∕ ϵ)})$ , which implies the claimed complexity bound. □
现在，给定 $ϵ \in (0, \frac{1}{2})$ ，取 $m = ⌈ \frac{1}{2} {log}_{3} (1 ∕ ϵ) ⌉$ 和 $T = ⌈ \frac{2}{m ϵ} ⌉$ 。那么，根据 (25)，近似误差 ${max}_{x \in [0, 1]} | f (x) - \tilde{f} (x) | \leq \frac{2}{T m} \leq ϵ$ ，而 $T + m 3^{m} = O (\frac{1}{ϵ ln (1 ∕ ϵ)})$ ，这意味着所宣称的复杂度约束。□

We show now how to modify the constructed network so as to remove $ρ$ -units. We only need to modify the ${\tilde{f}}_{2}$ part of the network. We will show that for any $δ > 0$ we can replace ${\tilde{f}}_{2}$ with a function ${\tilde{f}}_{3, δ}$ (defined below) that
现在，我们将展示如何修改所构建的网络，以删除 $ρ$ 单位。我们只需要修改网络的 ${\tilde{f}}_{2}$ 部分。我们将证明，对于任何 $δ > 0$ ，我们都可以用函数 ${\tilde{f}}_{3, δ}$ （定义见下文）来代替 ${\tilde{f}}_{2}$ ，即

(a)
obeys the following analog of approximation bound (24) : (30) $sup_{x \in [0, 1]} | f_{2} (x) - {\tilde{f}}_{3, δ} (x) | \leq \frac{8 δ}{T} + \frac{2}{T m},$
遵从以下近似约束 (24) 的类似条件： (30) $sup_{x \in [0, 1]} | f_{2} (x) - {\tilde{f}}_{3, δ} (x) | \leq \frac{8 δ}{T} + \frac{2}{T m},$
(b)
and is implementable by a depth-6 ReLU network having complexity $c (T + m 3^{m})$ with an absolute constant $c$ independent of $δ$ .
并可由深度为 6 的 ReLU 网络实现，其复杂度为 $c (T + m 3^{m})$ ，绝对常数 $c$ 与 $δ$ 无关。

Since $δ$ can be taken arbitrarily small, the theorem then follows by arguing as in Lemma 1, only with ${\tilde{f}}_{2}$ replaced by ${\tilde{f}}_{3, δ}$ .
由于 $δ$ 可任意取小，因此，只需用 ${\tilde{f}}_{3, δ}$ 代替 ${\tilde{f}}_{2}$ 即可得出定理，其论证过程与定理 1 相同。

As a first step, we approximate $ρ$ by a continuous piece-wise linear function $ρ_{δ}$ , with a small $δ > 0$ : $ρ (y) = \{\begin{matrix} y, & y \in [0, 1 - δ), \\ \frac{1 - δ}{δ} (1 - y), & y \in [1 - δ, 1), \\ 0, & y ⁄ \in [0, 1) . \end{matrix}$ Let ${\tilde{f}}_{2, δ}$ be defined as ${\tilde{f}}_{2}$ in (29), but with $ρ$ replaced by $ρ_{δ}$ : ${\tilde{f}}_{2, δ} (x) = \frac{1}{T} \sum_{γ \in Γ} \sum_{r = 0}^{m - 1} c_{γ, r} σ (\sum_{t : γ_{t} = γ} ρ_{δ} (T x - t) - \frac{r}{m}) .$ Since $ρ_{δ}$ is a continuous piece-wise linear function with three breakpoints, we can express it via the ReLU function, and hence implement ${\tilde{f}}_{2, δ}$ by a purely ReLU network, as in Proposition 1, and the complexity of the implementation does not depend on $δ$ . However, replacing $ρ$ with $ρ_{δ}$ affects the function ${\tilde{f}}_{2}$ on the intervals $(\frac{t - δ}{T}, \frac{t}{T}], t = 1, \dots, T$ , introducing there a large error (of magnitude $O (\frac{1}{T})$ ). But recall that both $f_{2}$ and ${\tilde{f}}_{2}$ vanish at the points $\frac{t}{T}, t = 0, \dots, T$ , by (21), (26). We can then largely remove this newly introduced error by simply suppressing ${\tilde{f}}_{2, δ}$ near the points $\frac{t}{T}$ .
第一步，我们用一个连续的片断线性函数 $ρ_{δ}$ 来近似 $ρ$ ，并加上一个小的 $δ > 0$ ： $ρ (y) = \{\begin{matrix} y, & y \in [0, 1 - δ), \\ \frac{1 - δ}{δ} (1 - y), & y \in [1 - δ, 1), \\ 0, & y ⁄ \in [0, 1) . \end{matrix}$ 让 ${\tilde{f}}_{2, δ}$ 定义为 (29) 中的 ${\tilde{f}}_{2}$ ，但 $ρ$ 由 $ρ_{δ}$ 代替： ${\tilde{f}}_{2, δ} (x) = \frac{1}{T} \sum_{γ \in Γ} \sum_{r = 0}^{m - 1} c_{γ, r} σ (\sum_{t : γ_{t} = γ} ρ_{δ} (T x - t) - \frac{r}{m}) .$ 由于 $ρ_{δ}$ 是一个连续的片断线性函数，有三个断点，我们可以通过 ReLU 函数来表达它，因此可以用纯 ReLU 网络来实现 ${\tilde{f}}_{2, δ}$ ，如命题 1 所示，而且实现的复杂度与 $δ$ 无关。不过，用 $ρ_{δ}$ 代替 $ρ$ 会影响区间 $(\frac{t - δ}{T}, \frac{t}{T}], t = 1, \dots, T$ 上的函数 ${\tilde{f}}_{2}$ ，从而引入一个很大的误差（量级为 $O (\frac{1}{T})$ ）。但是，根据 (21) 和 (26)， $f_{2}$ 和 ${\tilde{f}}_{2}$ 在点 $\frac{t}{T}, t = 0, \dots, T$ 上都消失了。因此，我们只需抑制 $\frac{t}{T}$ 点附近的 ${\tilde{f}}_{2, δ}$ ，就可以大致消除这个新引入的误差。

Precisely, consider the continuous piece-wise linear function $ϕ_{δ} (y) = \{\begin{matrix} 0, & y ⁄ \in [0, 1 - δ), \\ \frac{y}{δ}, & y \in [0, δ), \\ 1, & y \in [δ, 1 - 2 δ), \\ \frac{1 - δ - y}{δ}, & y \in [1 - 2 δ, 1 - δ) \end{matrix}$ and the full comb-like filtering function $Φ_{δ} (x) = \sum_{t = 0}^{T - 1} ϕ_{δ} (T x - t) .$ Note that $Φ_{δ}$ is continuous piece-wise linear with $4 T$ breakpoints, and $0 \leq Φ_{δ} (x) \leq 1$ . We then define our final modification of ${\tilde{f}}_{2}$ as (31) ${\tilde{f}}_{3, δ} (x) = σ ({\tilde{f}}_{2, δ} (x) + 2 Φ_{δ} (x) - 1) - σ (2 Φ_{δ} (x) - 1) .$
准确地说，考虑连续的片断线性函数 $ϕ_{δ} (y) = \{\begin{matrix} 0, & y ⁄ \in [0, 1 - δ), \\ \frac{y}{δ}, & y \in [0, δ), \\ 1, & y \in [δ, 1 - 2 δ), \\ \frac{1 - δ - y}{δ}, & y \in [1 - 2 δ, 1 - δ) \end{matrix}$ 和全梳状滤波函数 $Φ_{δ} (x) = \sum_{t = 0}^{T - 1} ϕ_{δ} (T x - t) .$ 注意， $Φ_{δ}$ 是连续的片断线性函数，带有 $4 T$ 断点和 $0 \leq Φ_{δ} (x) \leq 1$ 。然后，我们将 ${\tilde{f}}_{2}$ 的最终修改定义为 (31) ${\tilde{f}}_{3, δ} (x) = σ ({\tilde{f}}_{2, δ} (x) + 2 Φ_{δ} (x) - 1) - σ (2 Φ_{δ} (x) - 1) .$

Lemma 2 推理 2

The function ${\tilde{f}}_{3, δ}$ obeys the bound (30)
函数 ${\tilde{f}}_{3, δ}$ 服从约束 (30).

Proof 证明

Given $x \in [0, 1)$ , let $t \in {0, \dots, T - 1}$ and $y \in [0, 1)$ be determined from the representation $x = \frac{t + y}{T}$ (i.e., $y$ is the relative position of $x$ in the respective interval $I_{t}$ ). Consider several possibilities for $y$ :
给定 $x \in [0, 1)$ ，让 $t \in {0, \dots, T - 1}$ 和 $y \in [0, 1)$ 根据表示 $x = \frac{t + y}{T}$ 确定（即 $y$ 是 $x$ 在相应区间 $I_{t}$ 中的相对位置）。考虑 $y$ 的几种可能性：

1.
$y \in [1 - δ, 1]$ . In this case $Φ_{δ} (x) = 0$ . Note that (32) $sup_{x \in [0, 1]} | {\tilde{f}}_{2, δ} (x) | \leq 1,$ because, by construction, ${sup}_{x \in [0, 1]} | {\tilde{f}}_{2, δ} (x) | \leq {sup}_{x \in [0, 1]} | {\tilde{f}}_{2} (x) |$ , and ${sup}_{x \in [0, 1]} | {\tilde{f}}_{2} (x) | \leq 1$ by (26), (27). It follows that both terms in (31) vanish, i.e., ${\tilde{f}}_{3, δ} (x) = 0$ . But, since $f_{2}$ is Lipschitz with constant 2 by (22) and $f_{2} (\frac{t + 1}{T}) = 0$ , we have $| f_{2} (x) | \leq | f_{2} (x) - f_{2} (\frac{t + 1}{T}) | \leq \frac{2 | y - 1 |}{T} \leq \frac{2 δ}{T}$ . This implies $| f_{2} (x) - {\tilde{f}}_{3, δ} (x) | \leq \frac{2 δ}{T}$ .
在这种情况下 $Φ_{δ} (x) = 0$ .注意，根据构造， (32) $sup_{x \in [0, 1]} | {\tilde{f}}_{2, δ} (x) | \leq 1,$ 是因为 ${sup}_{x \in [0, 1]} | {\tilde{f}}_{2, δ} (x) | \leq {sup}_{x \in [0, 1]} | {\tilde{f}}_{2} (x) |$ ，而 ${sup}_{x \in [0, 1]} | {\tilde{f}}_{2} (x) | \leq 1$ 是因为 (26), (27)。由此可见，(31) 中的两项都消失了，即 ${\tilde{f}}_{3, δ} (x) = 0$ .但是，由于由 (22) 和 $f_{2} (\frac{t + 1}{T}) = 0$ 可知 $f_{2}$ 是常数为 2 的 Lipschitz 值，所以有 $| f_{2} (x) | \leq | f_{2} (x) - f_{2} (\frac{t + 1}{T}) | \leq \frac{2 | y - 1 |}{T} \leq \frac{2 δ}{T}$ .这意味着 $| f_{2} (x) - {\tilde{f}}_{3, δ} (x) | \leq \frac{2 δ}{T}$ .
2.
$y \in [δ, 1 - 2 δ]$ . In this case $Φ_{δ} (x) = 1$ and ${\tilde{f}}_{2, δ} (x) = {\tilde{f}}_{2} (x)$ . Using (32), we find that ${\tilde{f}}_{3, δ} (x) = {\tilde{f}}_{2, δ} (x) = {\tilde{f}}_{2} (x)$ . It follows that $| f_{2} (x) - {\tilde{f}}_{3, δ} (x) | = | f_{2} (x) - {\tilde{f}}_{2} (x) | \leq \frac{2}{T m}$ .
在这种情况下， $Φ_{δ} (x) = 1$ 和 ${\tilde{f}}_{2, δ} (x) = {\tilde{f}}_{2} (x)$ .利用（32），我们发现 ${\tilde{f}}_{3, δ} (x) = {\tilde{f}}_{2, δ} (x) = {\tilde{f}}_{2} (x)$ . 由此得出 $| f_{2} (x) - {\tilde{f}}_{3, δ} (x) | = | f_{2} (x) - {\tilde{f}}_{2} (x) | \leq \frac{2}{T m}$ .
3.
$y \in [0, δ] \cup [1 - 2 δ, 1 - δ]$ . In this case ${\tilde{f}}_{2, δ} (x) = {\tilde{f}}_{2} (x)$ . Since $σ$ is Lipschitz with constant 1, $| {\tilde{f}}_{3, δ} (x) | \leq | {\tilde{f}}_{2, δ} (x) | = | {\tilde{f}}_{2} (x) |$ . Both $f_{2}$ and ${\tilde{f}}_{2}$ are Lipschitz with constant 2 (by (22), (27)) and vanish at $\frac{t}{T}$ and $\frac{t + 1}{T}$ (by (21), (26)). It follows that $| f_{2} (x) - {\tilde{f}}_{3, δ} (x) | \leq | f_{2} (x) | + | {\tilde{f}}_{2} (x) | \leq 2 \{\begin{matrix} 2 | x - \frac{t}{T} |, & y \in [0, δ] \\ 2 | x - \frac{t + 1}{T} |, & y \in [1 - 2 δ, 1 - δ] \end{matrix} \leq \frac{8 δ}{T} . □$
在这种情况下， ${\tilde{f}}_{2, δ} (x) = {\tilde{f}}_{2} (x)$ .由于 $σ$ 是常数为 1 的 Lipschitz，所以 $| {\tilde{f}}_{3, δ} (x) | \leq | {\tilde{f}}_{2, δ} (x) | = | {\tilde{f}}_{2} (x) |$ . $f_{2}$ 和 ${\tilde{f}}_{2}$ 都是常数为 2 的 Lipschitz（由 (22), (27)），并且在 $\frac{t}{T}$ 和 $\frac{t + 1}{T}$ 处消失（由 (21), (26)）。由此可见， $| f_{2} (x) - {\tilde{f}}_{3, δ} (x) | \leq | f_{2} (x) | + | {\tilde{f}}_{2} (x) | \leq 2 \{\begin{matrix} 2 | x - \frac{t}{T} |, & y \in [0, δ] \\ 2 | x - \frac{t + 1}{T} |, & y \in [1 - 2 δ, 1 - δ] \end{matrix} \leq \frac{8 δ}{T} . □$

It remains to verify the complexity property (b) of the function ${\tilde{f}}_{3, δ}$ . As already mentioned, ${\tilde{f}}_{2, δ}$ can be implemented by a depth-5 purely ReLU network with not more than $c (T + m 3^{m})$ weights, connections and computation units, where $c$ is an absolute constant independent of $δ$ . The function $Φ_{δ}$ can be implemented by a shallow, depth-3 network with $O (T)$ units and connection. Then, computation of ${\tilde{f}}_{3, δ}$ can be implemented by a network including two subnetworks for computing ${\tilde{f}}_{2, δ}$ and $Ψ_{δ}$ , and an additional layer containing two $σ$ -units as written in (31). We thus obtain 6 layers in the resulting full network and, choosing $T$ and $m$ in the same way as in Lemma 1, obtain the bound $\frac{c}{ϵ ln (1 ∕ ϵ)}$ for the number of its connections, weights, and computation units. □
我们还需要验证函数 ${\tilde{f}}_{3, δ}$ 的复杂性属性 (b)。如前所述， ${\tilde{f}}_{2, δ}$ 可以由一个深度为 5 的纯 ReLU 网络实现，其权重、连接和计算单元不超过 $c (T + m 3^{m})$ ，其中 $c$ 是一个与 $δ$ 无关的绝对常量。函数 $Φ_{δ}$ 可以通过一个深度为 3 的浅层网络来实现，该网络具有 $O (T)$ 个单元和连接。然后，对 ${\tilde{f}}_{3, δ}$ 的计算可以通过一个网络来实现，该网络包括两个用于计算 ${\tilde{f}}_{2, δ}$ 和 $Ψ_{δ}$ 的子网络，以及一个包含两个 $σ$ 单元的附加层，如 (31) 所述。因此，我们可以在得到的完整网络中得到 6 层，并以与假设 1 相同的方式选择 $T$ 和 $m$ ，从而得到其连接、权重和计算单元数量的约束 $\frac{c}{ϵ ln (1 ∕ ϵ)}$ 。□

4. Lower bounds 4.下限

4.1. Continuous nonlinear widths
4.1.连续非线性宽度

The method of continuous nonlinear widths (DeVore et al., 1989) is a very general approach to the analysis of parameterized nonlinear approximations, based on the assumption of continuous selection of their parameters. We are interested in the following lower bound for the complexity of approximations in $W^{n, \infty} ({[0, 1]}^{d}) .$
连续非线性宽度方法（DeVore 等人，1989 年）是分析参数化非线性近似的一种非常通用的方法，它基于参数连续选择的假设。我们对 $W^{n, \infty} ({[0, 1]}^{d}) .$ 中近似复杂度的下限感兴趣

Theorem 3 定理 3

DeVore et al., (1989), Theorem 4.2
DeVore 等人，（1989 年），定理 4.2

Fix $d, n$ . Let $W$ be a positive integer and $η : R^{W} \to C ({[0, 1]}^{d})$ be any mapping between the space $R^{W}$ and the space $C ({[0, 1]}^{d})$ . Suppose that there is a continuous map $M : F_{d, n} \to R^{W}$ such that $‖ f - η (M (f)) ‖_{\infty} \leq ϵ$ for all $f \in F_{d, n}$ . Then $W \geq c ϵ^{- d ∕ n}$ , with some constant $c$ depending only on $n$
固定 $d, n$ 。让 $W$ 是一个正整数， $η : R^{W} \to C ({[0, 1]}^{d})$ 是空间 $R^{W}$ 与空间 $C ({[0, 1]}^{d})$ 之间的任意映射。假设有一个连续映射 $M : F_{d, n} \to R^{W}$ ，使得 $‖ f - η (M (f)) ‖_{\infty} \leq ϵ$ 对于所有 $f \in F_{d, n}$ 。那么 $W \geq c ϵ^{- d ∕ n}$ ，与某个常数 $c$ 仅取决于 $n$ .

We apply this theorem by taking $η$ to be some ReLU network architecture, and $R^{W}$ the corresponding weight space. It follows that if a ReLU network architecture is capable of expressing any function from $F_{d, n}$ with error $ϵ$ , then, under the hypothesis of continuous weight selection, the network must have at least $c ϵ^{- d ∕ n}$ weights. The number of connections is then lower bounded by $\frac{c}{2} ϵ^{- d ∕ n}$ (since the number of weights is not larger than the sum of the number of computation units and the number of connections, and there are at least as many connections as units).
我们应用该定理时，将 $η$ 作为某个 ReLU 网络架构，而 $R^{W}$ 则是相应的权重空间。由此可知，如果一个 ReLU 网络体系结构能够表达 $F_{d, n}$ 的任何函数，且误差为 $ϵ$ ，那么在连续权值选择的假设下，该网络必须至少有 $c ϵ^{- d ∕ n}$ 个权值。连接数的下限为 $\frac{c}{2} ϵ^{- d ∕ n}$ （因为权重数不会大于计算单元数与连接数之和，而且连接数至少与计算单元数相同）。

The hypothesis of continuous weight selection is crucial in Theorem 3. By examining our proof of the counterpart upper bound $O (ϵ^{- d ∕ n} ln (1 ∕ ϵ))$ in Theorem 1, the weights are selected there in a continuous manner, so this upper bound asymptotically lies above $c ϵ^{- d ∕ n}$ in agreement with Theorem 3. We remark, however, that the optimal choice of the network weights (minimizing the error) is known to be discontinuous in general, even for shallow networks (Kainen, Kůrková, & Vogt, 1999).
连续权重选择的假设在定理 3 中至关重要。根据我们对定理 1 中对应上限 $O (ϵ^{- d ∕ n} ln (1 ∕ ϵ))$ 的证明，权重的选择是连续的，因此该上限渐近地高于 $c ϵ^{- d ∕ n}$ ，与定理 3 一致。不过我们要指出的是，网络权重的最优选择（误差最小化）在一般情况下是不连续的，即使对于浅层网络也是如此（Kainen, Kůrková, & Vogt, 1999）。

We also compare the bounds of Theorem 2, Theorem 3. In the case $d = n = 1$ , Theorem 3 provides a lower bound $\frac{c}{ϵ}$ for the number of weights and connections. On the other hand, in the adaptive architecture scenario, Theorem 2 provides the upper bound $\frac{c}{ϵ ln (1 ∕ ϵ)}$ for the number of weights, connections and computation units. The fact that this latter bound is asymptotically below the bound of Theorem 3 reflects the extra expressiveness associated with variable network architecture.
我们还可以比较定理 2 和定理 3 的边界。在 $d = n = 1$ 的情况下，定理 3 提供了权重和连接数的下限 $\frac{c}{ϵ}$ 。另一方面，在自适应架构情况下，定理 2 提供了权重、连接和计算单元数量的上限 $\frac{c}{ϵ ln (1 ∕ ϵ)}$ 。事实上，后一个界限逐渐低于定理 3 的界限，这反映了与可变网络架构相关的额外表现力。

4.2. Bounds based on VC-dimension
4.2.基于 VC 维度的界限

In this section we consider the setup where the same network architecture is used to approximate all functions $f \in F_{d, n}$ , but the dependence of the weights on $f$ is not assumed to be necessarily continuous. In this setup, some lower bounds on the network complexity can be obtained as a consequence of existing upper bounds on VC-dimension of networks with piece-wise polynomial activation functions and Boolean outputs (Anthony & Bartlett, 2009). In the next theorem, part (a) is a more general but weaker bound, while part (b) is a stronger bound assuming a constrained growth of the network depth.
在本节中，我们将考虑这样一种情况：使用相同的网络架构来逼近所有函数 $f \in F_{d, n}$ ，但权重对 $f$ 的依赖性不一定是连续的。在这种情况下，网络复杂度的一些下限可以通过现有的具有片断多项式激活函数和布尔输出的网络的 VC 维度上限得到（Anthony & Bartlett，2009 年）。在下一个定理中，(a) 部分是一个更一般但较弱的约束，而 (b) 部分是一个假设网络深度增长受限的更强约束。

Theorem 4 定理 4

Fix $d, n$ 修复 $d, n$ .

(a)
For any $ϵ \in (0, 1)$ , a ReLU network architecture capable of approximating any function $f \in F_{d, n}$ with error $ϵ$ must have at least $c ϵ^{- d ∕ (2 n)}$ weights, with some constant $c = c (d, n) > 0$
对于任意 $ϵ \in (0, 1)$ ，能够以误差 $ϵ$ 近似任意函数 $f \in F_{d, n}$ 的 ReLU 网络结构必须至少有 $c ϵ^{- d ∕ (2 n)}$ 个权值，其中包含某个常数 $c = c (d, n) > 0$ .
(b)
Let $p \geq 0, c_{1} > 0$ be some constants. For any $ϵ \in (0, \frac{1}{2})$ , if a ReLU network architecture of depth $L \leq c_{1} {ln}^{p} (1 ∕ ϵ)$ is capable of approximating any function $f \in F_{d, n}$ with error $ϵ$ , then the network must have at least $c_{2} ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ)$ weights, with some constant $c_{2} = c_{2} (d, n, p, c_{1}) > 0$ . ¹
假设 $p \geq 0, c_{1} > 0$ 是一些常数。对于任意 $ϵ \in (0, \frac{1}{2})$ ，如果深度为 $L \leq c_{1} {ln}^{p} (1 ∕ ϵ)$ 的 ReLU 网络结构能够以误差 $ϵ$ 近似任意函数 $f \in F_{d, n}$ ，那么该网络必须至少有 $c_{2} ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ)$ 个权值，且有某个常数 $c_{2} = c_{2} (d, n, p, c_{1}) > 0$ ¹

Proof 证明

Recall that given a class $H$ of Boolean functions on ${[0, 1]}^{d}$ , the VC-dimension of $H$ is defined as the size of the largest shattered subset $S \subset {[0, 1]}^{d}$ , i.e. the largest subset on which $H$ can compute any dichotomy (see, e.g., (Anthony & Bartlett, 2009), Section 3.3). We are interested in the case when $H$ is the family of functions obtained by applying thresholds $1 (x > a)$ to a ReLU network with fixed architecture but variable weights. In this case Theorem 8.7 of Anthony and Bartlett (2009) implies that (33) $VCdim (H) \leq c_{3} W^{2},$ and Theorem 8.8 implies that (34) $VCdim (H) \leq c_{3} L^{2} W ln W,$ where $W$ is the number of weights, $L$ is the network depth, and $c_{3}$ is an absolute constant.
回想一下，给定 ${[0, 1]}^{d}$ 上的一类布尔函数 $H$ ， $H$ 的 VC 维度被定义为最大破碎子集 $S \subset {[0, 1]}^{d}$ 的大小，即 $H$ 可以计算任何二分法的最大子集（参见，例如，（Anthony & Bartlett, 2009），第 3.3 节）。我们感兴趣的情况是，当 $H$ 是将阈值 $1 (x > a)$ 应用于具有固定架构但权重可变的 ReLU 网络时得到的函数族。在这种情况下，Anthony 和 Bartlett（2009 年）的定理 8.7 意味着 (33) $VCdim (H) \leq c_{3} W^{2},$ ，定理 8.8 意味着 (34) $VCdim (H) \leq c_{3} L^{2} W ln W,$ ，其中 $W$ 是权重数， $L$ 是网络深度， $c_{3}$ 是绝对常量。

Given a positive integer $N$ to be chosen later, choose $S$ as a set of $N^{d}$ points $x_{1}, \dots, x_{N^{d}}$ in the cube ${[0, 1]}^{d}$ such that the distance between any two of them is not less than $\frac{1}{N}$ . Given any assignment of values $y_{1}, \dots, y_{N^{d}} \in R$ , we can construct a smooth function $f$ satisfying $f (x_{m}) = y_{m}$ for all $m$ by setting (35) $f (x) = \sum_{m = 1}^{N^{d}} y_{m} ϕ (N (x - x_{m})),$ with some $C^{\infty}$ function $ϕ : R^{d} \to R$ such that $ϕ (0) = 1$ and $ϕ (x) = 0$ if $| x | > \frac{1}{2}$ .
给定一个稍后选择的正整数 $N$ ，选择 $S$ 作为立方体 ${[0, 1]}^{d}$ 中 $N^{d}$ 点 $x_{1}, \dots, x_{N^{d}}$ 的集合，使得任意两个点之间的距离不小于 $\frac{1}{N}$ 。给定值 $y_{1}, \dots, y_{N^{d}} \in R$ 的任意赋值，我们可以通过设置 (35) $f (x) = \sum_{m = 1}^{N^{d}} y_{m} ϕ (N (x - x_{m})),$ 与某个 $C^{\infty}$ 函数 $ϕ : R^{d} \to R$ 使 $ϕ (0) = 1$ 和 $ϕ (x) = 0$ 满足 $f (x_{m}) = y_{m}$ 的所有 $m$ 来构造一个平滑函数 $f$ 。

Let us obtain a condition ensuring that such $f \in F_{d, n}$ . For any multi-index $n$ , $max_{x} | D^{n} f (x) | = N^{| n |} max_{m} | y_{m} | max_{x} | D^{n} ϕ (x) |,$ so if (36) $max_{m} | y_{m} | \leq c_{4} N^{- n},$ with the constant $c_{4} = {({max}_{n : | n | \leq n} {max}_{x} | D^{n} ϕ (x) |)}^{- 1}$ , then $f \in F_{d, n}$ .
让我们得到一个条件，确保这样的 $f \in F_{d, n}$ .对于任意多指数 $n$ , $max_{x} | D^{n} f (x) | = N^{| n |} max_{m} | y_{m} | max_{x} | D^{n} ϕ (x) |,$ 所以如果 (36) $max_{m} | y_{m} | \leq c_{4} N^{- n},$ 加上常数 $c_{4} = {({max}_{n : | n | \leq n} {max}_{x} | D^{n} ϕ (x) |)}^{- 1}$ , 那么 $f \in F_{d, n}$ .

Now set (37) $ϵ = \frac{c_{4}}{3} N^{- n} .$ Suppose that there is a ReLU network architecture $η$ that can approximate, by adjusting its weights, any $f \in F_{d, n}$ with error less than $ϵ$ . Denote by $η (x, w)$ the output of the network for the input vector $x$ and the vector of weights $w$ .
现在设 (37) $ϵ = \frac{c_{4}}{3} N^{- n} .$ 假设有一个 ReLU 网络结构 $η$ ，它可以通过调整权重，以小于 $ϵ$ 的误差逼近任何 $f \in F_{d, n}$ 。用 $η (x, w)$ 表示输入向量 $x$ 和权重向量 $w$ 的网络输出。

Consider any assignment $z$ of Boolean values $z_{1}, \dots, z_{N^{d}} \in {0, 1}$ . Set $y_{m} = z_{m} c_{4} N^{- n}, m = 1, \dots, N^{d},$ and let $f$ be given by (35) (see Fig. 5); then (36) holds and hence $f \in F_{d, n}$ .
考虑布尔值 $z_{1}, \dots, z_{N^{d}} \in {0, 1}$ 的任意赋值 $z$ 。设 $y_{m} = z_{m} c_{4} N^{- n}, m = 1, \dots, N^{d},$ 并让 $f$ 由 (35) 给出（见图 5）；则 (36) 成立，因此 $f \in F_{d, n}$ .

By assumption, there is then a vector of weights, $w = w_{z}$ , such that for all $m$ we have $| η (x_{m}, w_{z}) - y_{m} | \leq ϵ$ , and in particular $η (x_{m}, w_{z}) \{\begin{matrix} \geq & c_{4} N^{- n} - ϵ & > c_{4} N^{- n} ∕ 2, & if z_{m} = 1, \\ \leq & ϵ & < c_{4} N^{- n} ∕ 2, & if z_{m} = 0, \end{matrix}$ so the thresholded network $η_{1} = 1 (η > c_{4} N^{- n} ∕ 2)$ has outputs $η_{1} (x_{m}, w_{z}) = z_{m}, m = 1, \dots, N^{d} .$ Since the Boolean values $z_{m}$ were arbitrary, we conclude that the subset $S$ is shattered and hence $VCdim (η_{1}) \geq N^{d} .$ Expressing $N$ through $ϵ$ with (37), we obtain (38) $VCdim (η_{1}) \geq {(\frac{3 ϵ}{c_{4}})}^{- d ∕ n} .$ To establish part (a) of the Theorem, we apply bound (33) to the network $η_{1}$ : (39) $VCdim (η_{1}) \leq c_{3} W^{2},$ where $W$ is the number of weights in $η_{1}$ , which is the same as in $η$ if we do not count the threshold parameter. Combining (38) with (39), we obtain the desired lower bound $W \geq c ϵ^{- d ∕ (2 n)}$ with $c = {(c_{4} ∕ 3)}^{d ∕ (2 n)} c_{3}^{- 1 ∕ 2}$ .
根据假设，存在一个权重向量 $w = w_{z}$ ，这样对于所有 $m$ 我们都有 $| η (x_{m}, w_{z}) - y_{m} | \leq ϵ$ ，尤其是 $η (x_{m}, w_{z}) \{\begin{matrix} \geq & c_{4} N^{- n} - ϵ & > c_{4} N^{- n} ∕ 2, & if z_{m} = 1, \\ \leq & ϵ & < c_{4} N^{- n} ∕ 2, & if z_{m} = 0, \end{matrix}$ ，因此阈值网络 $η_{1} = 1 (η > c_{4} N^{- n} ∕ 2)$ 有输出 $η_{1} (x_{m}, w_{z}) = z_{m}, m = 1, \dots, N^{d} .$ 由于布尔值 $z_{m}$ 是任意的，我们得出结论，子集 $S$ 是破碎的，因此 $VCdim (η_{1}) \geq N^{d} .$ 用 (37) 表示 $N$ 到 $ϵ$ ，我们得到 (38) $VCdim (η_{1}) \geq {(\frac{3 ϵ}{c_{4}})}^{- d ∕ n} .$ 为了建立定理 (a) 部分，我们对网络 $η_{1}$ 应用约束 (33) ： (39) $VCdim (η_{1}) \leq c_{3} W^{2},$ 其中 $W$ 是 $η_{1}$ 中的权重数，如果不计算阈值参数，则与 $η$ 中的权重数相同。结合 (38) 和 (39)，我们可以得到所需的下界 $W \geq c ϵ^{- d ∕ (2 n)}$ 和 $c = {(c_{4} ∕ 3)}^{d ∕ (2 n)} c_{3}^{- 1 ∕ 2}$ 。

To establish part (b) of the theorem,we use bound (34) and the hypothesis $L \leq c_{1} {ln}^{p} (1 ∕ ϵ)$ : (40) $VCdim (η_{1}) \leq c_{3} c_{1}^{2} {ln}^{2 p} (1 ∕ ϵ) W ln W .$ Combining (38) with (40), we obtain (41) $W ln W \geq \frac{1}{c_{3} c_{1}^{2}} {(\frac{3 ϵ}{c_{4}})}^{- d ∕ n} {ln}^{- 2 p} (1 ∕ ϵ) .$ Trying a $W$ of the form $W_{c_{2}} = c_{2} ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ)$ with a constant $c_{2}$ , we get $W_{c_{2}} ln W_{c_{2}} = c_{2} ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ) \times (\frac{d}{n} ln (1 ∕ ϵ) + ln c_{2} - (2 p + 1) ln ln (1 ∕ ϵ)) = (c_{2} \frac{d}{n} + o (1)) ϵ^{- d ∕ n} {ln}^{- 2 p} (1 ∕ ϵ) .$ Comparing this with (41), we see that if we choose $c_{2} < {(c_{4} ∕ 3)}^{d ∕ n} n ∕ (d c_{3} c_{1}^{2})$ , then for sufficiently small $ϵ$ we have $W ln W \geq W_{c_{2}} ln W_{c_{2}}$ and hence $W \geq W_{c_{2}}$ , as claimed. We can ensure that $W \geq W_{c_{2}}$ for all $ϵ \in (0, \frac{1}{2})$ by further decreasing $c_{2}$ . □
为了建立定理的（b）部分，我们使用约束（34）和假设 $L \leq c_{1} {ln}^{p} (1 ∕ ϵ)$ ： (40) $VCdim (η_{1}) \leq c_{3} c_{1}^{2} {ln}^{2 p} (1 ∕ ϵ) W ln W .$ 将（38）与（40）结合，我们得到 (41) $W ln W \geq \frac{1}{c_{3} c_{1}^{2}} {(\frac{3 ϵ}{c_{4}})}^{- d ∕ n} {ln}^{- 2 p} (1 ∕ ϵ) .$ 尝试一个形式为 $W_{c_{2}} = c_{2} ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ)$ 的 $W$ 与一个常数 $c_{2}$ ，我们得到 $W_{c_{2}} ln W_{c_{2}} = c_{2} ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ) \times (\frac{d}{n} ln (1 ∕ ϵ) + ln c_{2} - (2 p + 1) ln ln (1 ∕ ϵ)) = (c_{2} \frac{d}{n} + o (1)) ϵ^{- d ∕ n} {ln}^{- 2 p} (1 ∕ ϵ) .$ 将其与（41）比较，我们发现，如果我们选择 $c_{2} < {(c_{4} ∕ 3)}^{d ∕ n} n ∕ (d c_{3} c_{1}^{2})$ ，那么对于足够小的 $ϵ$ ，我们有 $W ln W \geq W_{c_{2}} ln W_{c_{2}}$ ，因此有 $W \geq W_{c_{2}}$ ，正如我们所声称的。我们可以通过进一步减小 $c_{2}$ 来确保 $W \geq W_{c_{2}}$ 适用于所有 $ϵ \in (0, \frac{1}{2})$ 。□

We remark that the constrained depth hypothesis of part (b) is satisfied, with $p = 1$ , by the architecture used for the upper bound in Theorem 1. The bound stated in part (b) of Theorem 4 matches the upper bound of Theorem 1 and the lower bound of Theorem 3 up to a power of $ln (1 ∕ ϵ)$ .
我们注意到，根据定理 1 中上限所使用的结构，(b) 部分的受限深度假设在 $p = 1$ 的情况下是满足的。定理 4 (b) 部分所述的界限与定理 1 的上界和定理 3 的下界相匹配，最大为 $ln (1 ∕ ϵ)$ 的幂。

4.3. Adaptive network architectures
4.3.自适应网络架构

Our goal in this section is to obtain a lower bound for the approximation complexity in the scenario where the network architecture may depend on the approximated function. This lower bound is thus a counterpart to the upper bound of Section 3.3.
本节的目标是在网络架构可能取决于近似函数的情况下，获得近似复杂度的下限。因此，这个下限与第 3.3 节中的上限相对应。

To state this result we define the complexity $N (f, ϵ)$ of approximating the function $f$ with error $ϵ$ as the minimal number of hidden computation units in a ReLU network that provides such an approximation.
为了说明这一结果，我们将误差为 $ϵ$ 的函数 $f$ 的近似复杂度 $N (f, ϵ)$ 定义为 ReLU 网络中提供这种近似的隐藏计算单元的最小数量。

Theorem 5 定理 5

For any $d, n$ , there exists $f \in W^{n, \infty} ({[0, 1]}^{d})$ such that $N (f, ϵ)$ is not $o (ϵ^{- d ∕ (9 n)})$ as $ϵ \to 0$
对于任何 $d, n$ ，都存在 $f \in W^{n, \infty} ({[0, 1]}^{d})$ ，使得 $N (f, ϵ)$ 不是 $o (ϵ^{- d ∕ (9 n)})$ 而是 $ϵ \to 0$ .

The proof relies on the following lemma.
证明依赖于下面的 Lemma。

Lemma 3 推理 3

Fix $d, n$ . For any sufficiently small $ϵ > 0$ there exists $f_{ϵ} \in F_{d, n}$ such that $N (f_{ϵ}, ϵ) \geq c_{1} ϵ^{- d ∕ (8 n)}$ , with some constant $c_{1} = c_{1} (d, n) > 0$
固定 $d, n$ 。对于任何足够小的 $ϵ > 0$ ，存在 $f_{ϵ} \in F_{d, n}$ ，使得 $N (f_{ϵ}, ϵ) \geq c_{1} ϵ^{- d ∕ (8 n)}$ ，与某个常数 $c_{1} = c_{1} (d, n) > 0$ .

Proof 证明

Observe that all the networks with not more than $m$ hidden computation units can be embedded in the single “enveloping” network that has $m$ hidden layers, each consisting of $m$ units, and that includes all the connections between units not in the same layer (see Fig. 6, Fig. 6(a)). The number of weights in this enveloping network is $O (m^{4})$ . On the other hand, Theorem 4 (a) states that at least $c ϵ^{- d ∕ (2 n)}$ weights are needed for an architecture capable of $ϵ$ -approximating any function in $F_{d, n}$ . It follows that there is a function $f_{ϵ} \in F_{d, n}$ that cannot be $ϵ$ -approximated by networks with fewer than $c_{1} ϵ^{- d ∕ (8 n)}$ computation units. □
请注意，所有隐藏计算单元不超过 $m$ 的网络都可以嵌入一个 "包络 "网络中，该网络有 $m$ 个隐藏层，每个隐藏层由 $m$ 个单元组成，并包括不在同一层的单元之间的所有连接（见图 6，图 6(a)）。这个包络网络的权重数为 $O (m^{4})$ 。另一方面，定理 4 (a) 指出，能够 $ϵ$ 近似 $F_{d, n}$ 中任何函数的架构至少需要 $c ϵ^{- d ∕ (2 n)}$ 个权重。由此可见，有一个函数 $f_{ϵ} \in F_{d, n}$ 是少于 $c_{1} ϵ^{- d ∕ (8 n)}$ 个计算单元的网络无法 $ϵ$ 近似的。□

Before proceeding to the proof of Theorem 5, note that $N (f, ϵ)$ is a monotone decreasing function of $ϵ$ with a few obvious properties: (42) $N (a f, | a | ϵ) = N (f, ϵ), for any a \in R ∖ {0}$ (follows by multiplying the weights of the output unit of the approximating network by a constant); (43) $N (f \pm g, ϵ + ‖ g ‖_{\infty}) \leq N (f, ϵ)$ (follows by approximating $f \pm g$ by an approximation of $f$ ); (44) $N (f_{1} \pm f_{2}, ϵ_{1} + ϵ_{2}) \leq N (f_{1}, ϵ_{1}) + N (f_{2}, ϵ_{2})$ (follows by combining approximating networks for $f_{1}$ and $f_{2}$ as in Fig. 6(b)).
在继续证明定理 5 之前，请注意 $N (f, ϵ)$ 是 $ϵ$ 的单调递减函数，具有几个明显的性质：2#（将近似网络输出单元的权重乘以一个常数即可得出）； (43) $N (f \pm g, ϵ + ‖ g ‖_{\infty}) \leq N (f, ϵ)$ （用 $f$ 的近似值近似 $f \pm g$ 即可得出）； (44) $N (f_{1} \pm f_{2}, ϵ_{1} + ϵ_{2}) \leq N (f_{1}, ϵ_{1}) + N (f_{2}, ϵ_{2})$ （如图 6(b)所示，将 $f_{1}$ 和 $f_{2}$ 的近似网络合并即可得出）。

Proof 证明

Proof of Theorem 5 定理 5 的证明

The claim of Theorem 5 is similar to the claim of Lemma 3, but is about a single function $f$ satisfying a slightly weaker complexity bound at multiple values of $ϵ \to 0$ . We will assume that Theorem 5 is false, i.e., (45) $N (f, ϵ) = o (ϵ^{- d ∕ (9 n)})$ for all $f \in W^{n, \infty} ({[0, 1]}^{d})$ , and we will reach contradiction by presenting $f$ violating this assumption. Specifically, we construct this $f$ as (46) $f = \sum_{k = 1}^{\infty} a_{k} f_{k},$ with some $a_{k} \in R$ , $f_{k} \in F_{d, n}$ , and we will make sure that (47) $N (f, ϵ_{k}) \geq ϵ_{k}^{- d ∕ (9 n)}$ for a sequence of $ϵ_{k} \to 0$ .
定理 5 的主张与 Lemma 3 的主张类似，但涉及的是在多个 $ϵ \to 0$ 值下满足稍弱复杂度约束的单个函数 $f$ 。我们将假设定理 5 是假的，即 (45) $N (f, ϵ) = o (ϵ^{- d ∕ (9 n)})$ 对于所有 $f \in W^{n, \infty} ({[0, 1]}^{d})$ ，我们将通过提出违反这一假设的 $f$ 来达到矛盾。具体地说，我们将 $f$ 构造为 (46) $f = \sum_{k = 1}^{\infty} a_{k} f_{k},$ 与一些 $a_{k} \in R$ , $f_{k} \in F_{d, n}$ ，我们将确保 (47) $N (f, ϵ_{k}) \geq ϵ_{k}^{- d ∕ (9 n)}$ 为 $ϵ_{k} \to 0$ 的序列。

We determine $a_{k}, f_{k}, ϵ_{k}$ sequentially. Suppose we have already found ${a_{s}, f_{s}, ϵ_{s}}_{s = 1}^{k - 1}$ ; let us describe how we define $a_{k}, f_{k}, ϵ_{k}$ .
我们依次确定 $a_{k}, f_{k}, ϵ_{k}$ 。假设我们已经找到了 ${a_{s}, f_{s}, ϵ_{s}}_{s = 1}^{k - 1}$ ；让我们描述一下如何定义 $a_{k}, f_{k}, ϵ_{k}$ 。

First, we set (48) $a_{k} = min_{s = 1, \dots, k - 1} \frac{ϵ_{s}}{2^{k - s}} .$ In particular, this ensures that $a_{k} \leq ϵ_{1} 2^{1 - k},$ so that the function $f$ defined by the series (46) will be in $W^{n, \infty} ({[0, 1]}^{d})$ , because $‖ f_{k} ‖_{W^{n, \infty} ({[0, 1]}^{d})} \leq 1$ .
首先，我们设置 (48) $a_{k} = min_{s = 1, \dots, k - 1} \frac{ϵ_{s}}{2^{k - s}} .$ 特别是，这样可以确保 $a_{k} \leq ϵ_{1} 2^{1 - k},$ 使得由数列 (46) 定义的函数 $f$ 在 $W^{n, \infty} ({[0, 1]}^{d})$ 中，因为 $‖ f_{k} ‖_{W^{n, \infty} ({[0, 1]}^{d})} \leq 1$ .

Next, using Lemma 3 and Eq. (42), observe that if $ϵ_{k}$ is sufficiently small, then we can find $f_{k} \in F_{d, n}$ such that (49) $N (a_{k} f_{k}, 3 ϵ_{k}) = N (f_{k}, \frac{3 ϵ_{k}}{a_{k}}) \geq c_{1} {(\frac{3 ϵ_{k}}{a_{k}})}^{- d ∕ (8 n)} \geq 2 ϵ_{k}^{- d ∕ (9 n)} .$ In addition, by assumption (45), if $ϵ_{k}$ is small enough then (50) $N (\sum_{s = 1}^{k - 1} a_{s} f_{s}, ϵ_{k}) \leq ϵ_{k}^{- d ∕ (9 n)} .$ Let us choose $ϵ_{k}$ and $f_{k}$ so that both (49), (50) hold. Obviously, we can also make sure that $ϵ_{k} \to 0$ as $k \to \infty$ .
接下来，利用 Lemma 3 和公式 (42)，观察到如果 $ϵ_{k}$ 足够小，那么我们可以找到 $f_{k} \in F_{d, n}$ 使 (49) $N (a_{k} f_{k}, 3 ϵ_{k}) = N (f_{k}, \frac{3 ϵ_{k}}{a_{k}}) \geq c_{1} {(\frac{3 ϵ_{k}}{a_{k}})}^{- d ∕ (8 n)} \geq 2 ϵ_{k}^{- d ∕ (9 n)} .$ 成立。此外，根据假设 (45)，如果 $ϵ_{k}$ 足够小，那么 (50) $N (\sum_{s = 1}^{k - 1} a_{s} f_{s}, ϵ_{k}) \leq ϵ_{k}^{- d ∕ (9 n)} .$ 我们选择 $ϵ_{k}$ 和 $f_{k}$ 使 (49), (50) 都成立。显然，我们还可以确保 $ϵ_{k} \to 0$ 如 $k \to \infty$ .

Let us check that the above choice of ${a_{k}, f_{k}, ϵ_{k}}_{k = 1}^{\infty}$ ensures that inequality (47) holds for all $k$ : $N (\sum_{s = 1}^{\infty} a_{s} f_{s}, ϵ_{k}) \geq N (\sum_{s = 1}^{k} a_{s} f_{s}, ϵ_{k} + ‖ \sum_{s = k + 1}^{\infty} a_{s} {f_{s} ‖}_{\infty}) \geq N (\sum_{s = 1}^{k} a_{s} f_{s}, ϵ_{k} + \sum_{s = k + 1}^{\infty} a_{s}) \geq N (\sum_{s = 1}^{k} a_{s} f_{s}, 2 ϵ_{k}) \geq N (a_{k} f_{k}, 3 ϵ_{k}) - N (\sum_{s = 1}^{k - 1} a_{s} f_{s}, ϵ_{k}) \geq ϵ^{- d ∕ (9 n)} .$ Here in the first step we use inequality (43), in the second the monotonicity of $N (f, ϵ)$ , in the third the monotonicity of $N (f, ϵ)$ and the setting (48), in the fourth the inequality (44), and in the fifth the conditions (49), (50). □
让我们检验一下，上述 ${a_{k}, f_{k}, ϵ_{k}}_{k = 1}^{\infty}$ 的选择是否能确保不等式（47）对所有 $k$ 都成立：这里，第一步我们使用不等式 (43)，第二步使用 $N (f, ϵ)$ 的单调性，第三步使用 $N (f, ϵ)$ 的单调性和设置 (48)，第四步使用不等式 (44)，第五步使用条件 (49), (50)。□

4.4. Slow approximation of smooth functions by shallow networks
4.4.浅层网络对平滑函数的缓慢逼近

In this section we show that, in contrast to deep ReLU networks, shallow ReLU networks relatively inefficiently approximate sufficiently smooth ( $C^{2}$ ) nonlinear functions. We remark that Liang and Srikant (2016) prove a similar result assuming global convexity instead of smoothness and nonlinearity.
在本节中，我们将证明，与深度 ReLU 网络相比，浅层 ReLU 网络相对低效地逼近了足够平滑 ( $C^{2}$ ) 的非线性函数。我们注意到，Liang 和 Srikant（2016）在假设全局凸性而非平滑性和非线性的情况下证明了类似的结果。

Theorem 6 定理 6

Let $f \in C^{2} ({[0, 1]}^{d})$ be a nonlinear function (i.e., not of the form $f (x_{1}, \dots, x_{d}) \equiv a_{0} + \sum_{k = 1}^{d} a_{k} x_{k}$ on the whole ${[0, 1]}^{d}$ ). Then, for any fixed $L$ , a depth- $L$ ReLU network approximating $f$ with error $ϵ \in (0, 1)$ must have at least $c ϵ^{- 1 ∕ (2 (L - 2))}$ weights and computation units, with some constant $c = c (f, L) > 0 .$
假设 $f \in C^{2} ({[0, 1]}^{d})$ 是一个非线性函数（即在 ${[0, 1]}^{d}$ 整体上不是 $f (x_{1}, \dots, x_{d}) \equiv a_{0} + \sum_{k = 1}^{d} a_{k} x_{k}$ 的形式）。那么，对于任意固定的 $L$ ，以误差 $ϵ \in (0, 1)$ 近似 $f$ 的深度 $L$ ReLU 网络必须至少有 $c ϵ^{- 1 ∕ (2 (L - 2))}$ 个权值和计算单元，并有某个常数 $c = c (f, L) > 0 .$

Proof 证明

Since $f \in C^{2} ({[0, 1]}^{d}$ and $f$ is nonlinear, we can find $x_{0} \in {[0, 1]}^{d}$ and $v \in R^{d}$ such that $x_{0} + x v \in {[0, 1]}^{d}$ for all $x \in [- 1, 1]$ and the function $f_{1} : x \mapsto f (x_{0} + x v)$ is strictly convex or concave on $[- 1, 1]$ . Suppose without loss of generality that it is strictly convex: (51) $min_{x \in [- 1, 1]} f_{1}^{''} (x) = c_{1} > 0 .$ Suppose that $\tilde{f}$ is an $ϵ$ -approximation of function $f$ , and let $\tilde{f}$ be implemented by a ReLU network $η$ of depth $L$ . Let ${\tilde{f}}_{1} : x \mapsto \tilde{f} (x_{0} + x v)$ . Then ${\tilde{f}}_{1}$ also approximates $f_{1}$ with error not larger than $ϵ$ . Moreover, since ${\tilde{f}}_{1}$ is obtained from $\tilde{f}$ by a linear substitution $x = x_{0} + x v$ , ${\tilde{f}}_{1}$ can be implemented by a ReLU network $η_{1}$ of the same depth $L$ and with the number of units and weights not larger than in $η$ (we can obtain $η_{1}$ from $η$ by replacing the input layer in $η$ with a single unit, accordingly modifying the input connections, and adjusting the weights associated with these connections). It is thus sufficient to establish the claimed bounds for $η_{1}$ .
由于 $f \in C^{2} ({[0, 1]}^{d}$ 和 $f$ 是非线性的，我们可以找到 $x_{0} \in {[0, 1]}^{d}$ 和 $v \in R^{d}$ ，使得 $x_{0} + x v \in {[0, 1]}^{d}$ 对于所有 $x \in [- 1, 1]$ 和函数 $f_{1} : x \mapsto f (x_{0} + x v)$ 在 $[- 1, 1]$ 上是严格凸的或凹的。在不失一般性的前提下，假设它是严格凸的： (51) $min_{x \in [- 1, 1]} f_{1}^{''} (x) = c_{1} > 0 .$ 假设 $\tilde{f}$ 是函数 $f$ 的 $ϵ$ 近似值，并且让 $\tilde{f}$ 由深度为 $L$ 的 ReLU 网络 $η$ 实现。让 ${\tilde{f}}_{1} : x \mapsto \tilde{f} (x_{0} + x v)$ 。则 ${\tilde{f}}_{1}$ 也能逼近 $f_{1}$ ，且误差不大于 $ϵ$ 。此外，由于 ${\tilde{f}}_{1}$ 是通过线性替换 $x = x_{0} + x v$ 从 $\tilde{f}$ 得到的，因此 ${\tilde{f}}_{1}$ 可以通过深度 $L$ 相同的 ReLU 网络 $η_{1}$ 来实现，且单元数和权重不大于 $η$ （我们可以通过用一个单元替换 $η$ 中的输入层，相应地修改输入连接，并调整与这些连接相关的权重，从 $η$ 得到 $η_{1}$ ）。因此，我们只需为 $η_{1}$ 建立所声称的边界即可。

By construction, ${\tilde{f}}_{1}$ is a continuous piece-wise linear function of $x$ . Denote by $M$ the number of linear pieces in ${\tilde{f}}_{1}$ . We will use the following counting lemma.
根据构造， ${\tilde{f}}_{1}$ 是 $x$ 的连续片断线性函数。用 $M$ 表示 ${\tilde{f}}_{1}$ 中的线性片段数。我们将使用下面的计数 Lemma。

Lemma 4 例题 4

$M \leq {(2 U)}^{L - 2}$ , where $U$ is the number of computation units in $η_{1}$
$M \leq {(2 U)}^{L - 2}$ ，其中 $U$ 是 $η_{1}$ 中的计算单元数.

Proof 证明

This bound, up to minor details, is proved in Lemma 2.1 of Telgarsky (2015). Precisely, Telgarsky’s lemma states that if a network has a single input, connections only between neighboring layers, at most $m$ units in a layer, and a piece-wise linear activation function with $t$ pieces, then the number of linear pieces in the output of the network is not greater than ${(t m)}^{L}$ . By examining the proof of the lemma we see that it will remain valid for networks with connections not necessarily between neighboring layers, if we replace $m$ by $U$ in the expression ${(t m)}^{L}$ . Moreover, we can slightly strengthen the bound by noting that in the present paper the input and output units are counted as separate layers, only units of layers 3 to $L$ have multiple incoming connections, and the activation function is applied only in layers 2 to $L - 1$ . By following Telgarsky’s arguments, this gives the slightly more accurate bound ${(t U)}^{L - 2}$ (i.e., with the power $L - 2$ instead of $L$ ). It remains to note that the ReLU activation function corresponds to $t = 2$ . □
Telgarsky (2015)的定理 2.1 证明了这一约束，但还有一些小细节。确切地说，特尔加尔斯基的定理指出，如果一个网络只有一个输入，只在相邻层之间有连接，一层中最多有 $m$ 个单元，以及一个片断线性激活函数有 $t$ 个片断，那么该网络输出中的线性片断数不会大于 ${(t m)}^{L}$ 。通过研究该定理的证明，我们可以发现，如果我们在表达式 ${(t m)}^{L}$ 中用 $U$ 代替 $m$ ，那么该定理对于不一定在相邻层之间有连接的网络仍然有效。此外，我们还可以注意到，在本文中，输入和输出单元被视为独立的层，只有第 3 层到 $L$ 层的单元有多个输入连接，并且激活函数只应用于第 2 层到 $L - 1$ 层，从而略微加强约束。根据特尔加尔斯基的论证，这给出了稍微更精确的边界 ${(t U)}^{L - 2}$ （即幂 $L - 2$ ，而不是 $L$ ）。需要注意的是，ReLU 激活函数对应于 $t = 2$ 。□

Lemma 4 implies that there is an interval $[a, b] \subset [- 1, 1]$ of length not less than $2 {(2 U)}^{- (L - 2)}$ on which the function ${\tilde{f}}_{1}$ is linear. Let $g = f_{1} - {\tilde{f}}_{1}$ . Then, by the approximation accuracy assumption, ${sup}_{x \in [a, b]} | g (x) | \leq ϵ$ , while by (51) and by the linearity of ${\tilde{f}}_{1}$ on $[a, b]$ , ${max}_{x \in [a, b]} g^{''} (x) \geq c_{1} > 0$ . It follows that $max (g (a), g (b)) \geq g (\frac{a + b}{2}) + \frac{c_{1}}{2} {(\frac{b - a}{2})}^{2}$ and hence $ϵ \geq \frac{1}{2} (max (g (a), g (b)) - g (\frac{a + b}{2})) \geq \frac{c_{1}}{4} {(\frac{b - a}{2})}^{2} \geq \frac{c_{1}}{4} {(2 U)}^{- 2 (L - 2)},$ which implies the claimed bound $U \geq \frac{1}{2} {(\frac{4 ϵ}{c_{1}})}^{- 1 ∕ (2 (L - 2))}$ . Since there are at least as many weights as computation units in a network, a similar bound holds for the number of weights. □
定理 4 意味着存在一个长度不小于 $2 {(2 U)}^{- (L - 2)}$ 的区间 $[a, b] \subset [- 1, 1]$ ，在这个区间上函数 ${\tilde{f}}_{1}$ 是线性的。设 $g = f_{1} - {\tilde{f}}_{1}$ 。那么，根据近似精确度假设， ${sup}_{x \in [a, b]} | g (x) | \leq ϵ$ ，而根据 (51) 和 ${\tilde{f}}_{1}$ 在 $[a, b]$ 上的线性关系， ${max}_{x \in [a, b]} g^{''} (x) \geq c_{1} > 0$ 。由此得出 $max (g (a), g (b)) \geq g (\frac{a + b}{2}) + \frac{c_{1}}{2} {(\frac{b - a}{2})}^{2}$ ，进而得出 $ϵ \geq \frac{1}{2} (max (g (a), g (b)) - g (\frac{a + b}{2})) \geq \frac{c_{1}}{4} {(\frac{b - a}{2})}^{2} \geq \frac{c_{1}}{4} {(2 U)}^{- 2 (L - 2)},$ ，这意味着所声称的约束 $U \geq \frac{1}{2} {(\frac{4 ϵ}{c_{1}})}^{- 1 ∕ (2 (L - 2))}$ 。由于网络中的权重至少与计算单元一样多，因此权重数也有类似的约束。□

5. Discussion 5.讨论

We discuss some implications of the obtained bounds.
我们讨论了所获边界的一些含义。

Deep vs. shallow ReLU approximations of smooth functions
平滑函数的深层 ReLU 近似与浅层 ReLU 近似

Our results clearly show that deep ReLU networks more efficiently express smooth functions than shallow ReLU networks. By Theorem 1, functions from the Sobolev space $W^{n, \infty} ({[0, 1]}^{d})$ can be $ϵ$ -approximated by ReLU networks with depth $O (ln (1 ∕ ϵ))$ and the number of computation units $O (ϵ^{- d ∕ n} ln (1 ∕ ϵ))$ . In contrast, by Theorem 6, a nonlinear function from $C^{2} ({[0, 1]}^{d})$ cannot be $ϵ$ -approximated by a ReLU network of fixed depth $L$ with the number of units less than $c ϵ^{- 1 ∕ (2 (L - 2))}$ . In particular, it follows that in terms of the required number of computation units, unbounded-depth approximations of functions from $W^{n, \infty} ({[0, 1]}^{d})$ are asymptotically strictly more efficient than approximations with a fixed depth $L$ at least when $\frac{d}{n} < \frac{1}{2 (L - 2)}$ (assuming also $n > 2$ , so that $W^{n, \infty} ({[0, 1]}^{d}) \subset C^{2} ({[0, 1]}^{d})$ ). The efficiency of depth is even more pronounced for very smooth functions such as polynomials, which can be implemented by deep networks using only $O (ln (1 ∕ ϵ))$ units (cf. Proposition 2, Proposition 3 and the proof of Theorem 1). Liang and Srikant describe in Liang and Srikant (2016) some conditions on the approximated function (resembling conditions of local analyticity) under which complexity of deep $ϵ$ -approximation is $O ({ln}^{c} (1 ∕ ϵ))$ with a constant power $c$ .
我们的结果清楚地表明，深度 ReLU 网络比浅层 ReLU 网络更有效地表达平滑函数。根据定理 1，来自 Sobolev 空间 $W^{n, \infty} ({[0, 1]}^{d})$ 的函数可以通过深度为 $O (ln (1 ∕ ϵ))$ 且计算单元数为 $O (ϵ^{- d ∕ n} ln (1 ∕ ϵ))$ 的 ReLU 网络进行 $ϵ$ 近似。相反，根据定理 6，来自 $C^{2} ({[0, 1]}^{d})$ 的非线性函数无法通过固定深度为 $L$ 且单元数小于 $c ϵ^{- 1 ∕ (2 (L - 2))}$ 的 ReLU 网络进行 $ϵ$ 近似。特别是，从所需计算单元数来看，至少当 $\frac{d}{n} < \frac{1}{2 (L - 2)}$ 时，来自 $W^{n, \infty} ({[0, 1]}^{d})$ 的函数的无界深度近似在渐近严格意义上比具有固定深度 $L$ 的近似更有效（假设还有 $n > 2$ ，那么 $W^{n, \infty} ({[0, 1]}^{d}) \subset C^{2} ({[0, 1]}^{d})$ ）。对于多项式等非常平滑的函数，深度的效率更为显著，深度网络只需 $O (ln (1 ∕ ϵ))$ 个单元就能实现（参见命题 2、命题 3 和定理 1 的证明）。Liang 和 Srikant 在 Liang and Srikant (2016) 中描述了近似函数的一些条件（类似于局部解析性条件），在这些条件下，深度 $ϵ$ 近似的复杂度为 $O ({ln}^{c} (1 ∕ ϵ))$ ，幂为 $c$ 。

Continuous model selection vs. function-dependent network architectures
连续模型选择与依赖功能的网络架构对比

When approximating a function by a neural network, one can either view the network architecture as fixed and only tune the weights, or optimize the architecture as well. Moreover, when tuning the weights, one can either require them to continuously depend on the approximated function or not. We naturally expect that more freedom in the choice of the approximation should lead to higher expressiveness.
在用神经网络逼近函数时，我们可以将网络结构视为固定的，只调整权重，也可以同时优化结构。此外，在调整权重时，我们既可以要求权重持续依赖于近似函数，也可以不要求权重持续依赖于近似函数。我们自然希望，在选择近似值时有更大的自由度，从而提高表达能力。

Our bounds confirm this expectation to a certain extent. Specifically, the complexity of $ϵ$ -approximation of functions from the unit ball $F_{1, 1}$ in $W^{1, \infty} ([0, 1])$ is lower bounded by $\frac{c}{ϵ}$ in the scenario with a fixed architecture and continuously selected weights (see Theorem 3). On the other hand, we show in Theorem 2 that this complexity is upper bounded by $O (\frac{1}{ϵ ln (1 ∕ ϵ)})$ if we are allowed to adjust the network architecture. This bound is achieved by finite-depth (depth-6) ReLU networks using the idea of reused subnetworks familiar from the theory of Boolean circuits (Shannon, 1949).
我们的边界在一定程度上证实了这一预期。具体来说，在架构固定、权重连续选择的情况下， $W^{1, \infty} ([0, 1])$ 中单位球 $F_{1, 1}$ 函数的 $ϵ$ 近似复杂度下限为 $\frac{c}{ϵ}$ （见定理 3）。另一方面，我们在定理 2 中证明，如果允许我们调整网络架构，则该复杂度的上限为 $O (\frac{1}{ϵ ln (1 ∕ ϵ)})$ 。利用布尔电路理论（香农，1949 年）中熟悉的重用子网络思想，有限深度（深度-6）ReLU 网络可以实现这一约束。

In the case of fixed architecture, we have not established any evidence of complexity improvement for unconstrained weight selection compared to continuous weight selection. We remark however that, already for approximations with depth-3 networks, the optimal weights are known to discontinuously depend, in general, on the approximated function (Kainen et al., 1999). On the other hand, part b) of Theorem 4 shows that if the network depth scales as $O ({ln}^{p} (1 ∕ ϵ))$ , discontinuous weight selection cannot improve the continuous-case complexity more than by a factor being some power of $ln (1 ∕ ϵ)$ .
在结构固定的情况下，与连续权重选择相比，我们还没有发现无约束权重选择能提高复杂性的证据。不过我们要指出的是，对于深度为 3 的网络近似，已知最优权重一般会不连续地依赖于近似函数（Kainen 等人，1999 年）。另一方面，定理 4 的 b) 部分表明，如果网络深度按 $O ({ln}^{p} (1 ∕ ϵ))$ 的比例缩放，非连续权重选择对连续情况下复杂度的改善不会超过 $ln (1 ∕ ϵ)$ 的某个幂次。

Upper vs. lower complexity bounds
复杂度上限与下限

We indicate the gaps between respective upper and lower bounds in the three scenarios mentioned above: fixed architectures with continuous selection of weights, fixed architectures with unconstrained selection of weights, or adaptive architectures.
我们指出了上述三种情况下各自上下限之间的差距：连续选择权重的固定架构、无约束选择权重的固定架构或自适应架构。

For fixed architectures with continuous selection the lower bound $c ϵ^{- d ∕ n}$ is provided by Theorem 3, and the upper bound $O (ϵ^{- d ∕ n} ln (1 ∕ ϵ))$ by Theorem 1, so these bounds are tight up to a factor $O (ln (1 ∕ ϵ))$ .
对于具有连续选择功能的固定架构，定理 3 提供了下界 $c ϵ^{- d ∕ n}$ ，定理 1 提供了上界 $O (ϵ^{- d ∕ n} ln (1 ∕ ϵ))$ ，因此这些下界在系数 $O (ln (1 ∕ ϵ))$ 以下都很紧凑。

In the case of fixed architecture but unconstrained selection, part b) of Theorem 4 gives a lower bound $c ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ)$ under assumption that the depth is constrained by $O ({ln}^{p} (1 ∕ ϵ))$ . This is only different by a factor of $O ({ln}^{2 p + 2} (1 ∕ ϵ))$ from the upper bound of Theorem 1. Without this depth constraint we only have the significantly weaker bound $c ϵ^{- d ∕ (2 n)}$ (part a) of Theorem 4).
在结构固定但选择不受约束的情况下，假设深度受 $O ({ln}^{p} (1 ∕ ϵ))$ 约束，定理 4 的 b) 部分给出了下界 $c ϵ^{- d ∕ n} {ln}^{- 2 p - 1} (1 ∕ ϵ)$ 。这与定理 1 的上限只相差 $O ({ln}^{2 p + 2} (1 ∕ ϵ))$ 倍。如果没有深度限制，我们只能得到明显较弱的边界 $c ϵ^{- d ∕ (2 n)}$ （定理 4 的 a 部分）。

In the case of adaptive architectures, there is a big gap between our upper and lower bounds. The upper bound $O (\frac{1}{ϵ ln (1 ∕ ϵ)})$ is given by Theorem 2 for $d = n = 1$ . The lower bound, proved for general $d, n$ in Theorem 5, only states that there are $f \in W^{n, \infty} ({[0, 1]}^{d})$ for which the complexity is not $o (ϵ^{- d ∕ (9 n)})$ .
对于自适应架构，我们的上界和下界之间存在很大差距。定理 2 给出了 $d = n = 1$ 的上界 $O (\frac{1}{ϵ ln (1 ∕ ϵ)})$ 。下界在定理 5 中针对一般的 $d, n$ 得到证明，它只说明有 $f \in W^{n, \infty} ({[0, 1]}^{d})$ 的复杂度不是 $o (ϵ^{- d ∕ (9 n)})$ 。

ReLU vs. smooth activation functions
ReLU 与平滑激活函数

A popular general-purpose method of approximation is shallow (depth-3) networks with smooth activation functions (e.g., logistic sigmoid). Upper and lower approximation complexity bounds for these networks Maiorov and Meir (2000), Mhaskar (1996) show that complexity scales as $\sim ϵ^{- d ∕ n}$ up to some $ln (1 ∕ ϵ)$ factors. Comparing this with our bounds in Theorems 1, 2, 4, it appears that deep ReLU networks are roughly (up to $ln (1 ∕ ϵ)$ factors) as expressive as shallow networks with smooth activation functions.
一种流行的通用近似方法是具有平滑激活函数（如 logistic sigmoid）的浅层（深度-3）网络。Maiorov 和 Meir（2000 年）、Mhaskar（1996 年）的研究表明，这些网络的上下限近似复杂度为 $\sim ϵ^{- d ∕ n}$ ，最高可达 $ln (1 ∕ ϵ)$ 。将其与定理 1、2、4 中的近似值进行比较，可以发现深度 ReLU 网络的表现力与具有平滑激活函数的浅层网络大致相当（最多为 $ln (1 ∕ ϵ)$ 个因子）。

6. Conclusion 6.结论

We have established several upper and lower bounds for the expressive power of deep ReLU networks in the context of approximation in Sobolev spaces. We should note, however, that this setting may not quite reflect typical real world applications, which usually possess symmetries and hierarchical and other structural properties substantially narrowing the actually interesting classes of approximated functions (LeCun et al., 2015). Some recent publications introduce and study expressive power of deep networks in frameworks bridging this gap, in particular, graph-based hierarchical approximations are studied in Mhaskar et al. (2016), Mhaskar and Poggio (2016) and convolutional arithmetic circuits in Cohen, Sharir, and Shashua (2015). Theoretical analysis of expressiveness of deep networks taking into account such properties of real data seems to be an important and promising direction of future research.
在索波列夫空间逼近的背景下，我们为深度 ReLU 网络的表现力确定了几个上下限。然而，我们应该注意到，这种设置可能并不完全反映典型的现实世界应用，这些应用通常具有对称性、层次性和其他结构特性，大大缩小了近似函数的实际有趣类别（LeCun 等人，2015 年）。最近的一些出版物介绍并研究了深度网络在弥合这一差距的框架中的表现力，特别是 Mhaskar 等人（2016）、Mhaskar 和 Poggio（2016）研究了基于图的分层逼近，Cohen、Sharir 和 Shashua（2015）研究了卷积算术电路。考虑到真实数据的这些特性，对深度网络的表现力进行理论分析似乎是未来研究的一个重要而有前景的方向。

Acknowledgments 致谢

The author thanks Matus Telgarsky and the anonymous referees for multiple helpful comments on the preliminary versions of the paper. The research was funded by Skolkovo Institute of Science and Technology (project “Recognition of sparse geometric data”, 2016).
作者感谢马图斯-特尔加尔斯基（Matus Telgarsky）和匿名审稿人对论文初稿提出的多条有益意见。本研究得到了斯科尔科沃科学技术研究所的资助（"稀疏几何数据识别 "项目，2016 年）。

References 参考资料

Anthony and Bartlett (2009)
安东尼和巴特利特（2009 年）
Anthony Martin, Bartlett Peter L.
安东尼-马丁、巴特利特-彼得-L.
Neural network learning: Theoretical foundations
神经网络学习：理论基础
Cambridge University Press (2009)
剑桥大学出版社（2009 年）
Google Scholar 谷歌学者
Bartlett et al. (1998) 巴特利特等人（1998 年）
Bartlett Peter L., Maiorov Vitaly, Meir Ron
巴特利特-彼得-L, 马约洛夫-维塔利, 梅尔-龙
Almost linear VC-dimension bounds for piecewise polynomial networks
片断多项式网络的几乎线性 VC 维度边界
Neural Computation, 10 (8) (1998), pp. 2159-2173
神经计算》，10 (8) (1998)，第 2159-2173 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Bianchini and Scarselli (2014)
比安奇尼和斯卡塞利（2014 年）
Bianchini Monica, Scarselli Franco
On the complexity of neural network classifiers: a comparison between shallow and deep architectures
神经网络分类器的复杂性：浅层架构与深层架构的比较
IEEE Transactions on Neural Networks and Learning Systems, 25 (8) (2014), pp. 1553-1565
电气和电子工程师学会神经网络与学习系统论文集》，25 (8) (2014)，第 1553-1565 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Cohen et al. (2015) 科恩等人（2015 年）
Cohen, Nadav, Sharir, Or, & Shashua, Amnon (2015). On the Expressive Power of Deep Learning: A Tensor Analysis. ArXiv preprint ArXiv:1509.05009.
Cohen, Nadav, Sharir, Or, & Shashua, Amnon (2015)。深度学习的表现力：张量分析》。ArXiv preprint ArXiv:1509.05009.
Google Scholar 谷歌学者
Dawson and Nielsen (2006)
道森和尼尔森（2006 年）
Dawson C.M., Nielsen M.A.
The Solovay-Kitaev algorithm
索洛维-基塔耶夫算法
Quantum Information & Computation, 6 (1) (2006), pp. 81-95
量子信息与计算》，6 (1) (2006)，第 81-95 页
CrossRef Google Scholar 谷歌学者
Delalleau and Bengio (2011)
Delalleau 和 Bengio（2011 年）
Delalleau Olivier, Bengio Yoshua
Shallow vs. deep sum-product networks
浅层与深层和积网络
Advances in Neural Information Processing Systems (2011), pp. 666-674
神经信息处理系统进展》（2011 年），第 666-674 页
Google Scholar 谷歌学者
DeVore et al. (1989) DeVore 等人（1989 年）
DeVore Ronald A., Howard Ralph, Micchelli Charles
Optimal nonlinear approximation
最佳非线性近似
Manuscripta Mathematica, 63 (4) (1989), pp. 469-478
Manuscripta Mathematica》，63 (4) (1989)，第 469-478 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Goldberg and Jerrum (1995)
戈德伯格和杰鲁姆（1995 年）
Goldberg Paul W., Jerrum Mark R.
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
以实数为参数的概念类的 Vapnik-Chervonenkis 维度范围
Machine Learning, 18 (2–3) (1995), pp. 131-148
机器学习》，18 (2-3) (1995)，第 131-148 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Kainen et al. (1999) 凯宁等人（1999 年）
Kainen Paul C., Kůrková Věra, Vogt Andrew
凯宁-保罗-C.、库尔科瓦-维拉、沃格特-安德鲁
Approximation by neural networks is not continuous
神经网络的逼近不是连续的
Neurocomputing, 29 (1) (1999), pp. 47-56
神经计算》，29 (1) (1999)，第 47-56 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Kearns and Schapire (1990)
卡恩斯和沙皮尔（1990 年）
Kearns Michael J., Schapire Robert E.
Efficient distribution-free learning of probabilistic concepts
概率概念的高效无分布学习
Foundations of computer science, 1990. Proceedings., 31st annual symposium on, IEEE (1990), pp. 382-391
计算机科学基础，1990 年。第 31 届年度研讨会，IEEE (1990)，第 382-391 页
Google Scholar 谷歌学者
Kitaev et al. (2002) Kitaev 等人（2002 年）
Kitaev A. Yu., Shen A.H., Vyalyi M.N.
KitaevA.Yu.、ShenA.H.、VyalyiM.N.
Classical and quantum computation
经典计算和量子计算
0821832298, American Mathematical Society, Boston, MA, USA (2002)
0821832298，美国数学学会，美国马萨诸塞州波士顿（2002 年）
Google Scholar 谷歌学者
LeCun et al. (2015) LeCun 等人（2015 年）
LeCun Yann, Bengio Yoshua, Hinton Geoffrey
Deep learning 深度学习
Nature, 521 (7553) (2015), pp. 436-444
自然》，521 (7553) (2015)，第 436-444 页
CrossRef View in Scopus Google Scholar
CrossRef 查看 ScopusGoogle Scholar
Liang and Srikant (2016) 梁和斯里康特（2016）
Liang, Shiyu, & Srikant, R. (2016). Why Deep Neural Networks? ArXiv Preprint ArXiv:1610.04161.
Liang, Shiyu, & Srikant, R. (2016)。为什么选择深度神经网络？ArXiv Preprint ArXiv:1610.04161.
Google Scholar 谷歌学者
Maiorov and Meir (2000) Maiorov 和 Meir（2000 年）
Maiorov V.E., Meir Ron
On the near optimality of the stochastic approximation of smooth functions by neural networks
论神经网络随机逼近平滑函数的近似最优性
Advances in Computational Mathematics, 13 (1) (2000), pp. 79-103
计算数学进展》，13 (1) (2000)，第 79-103 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Mhaskar (1996) 马斯卡（1996 年）
Mhaskar H.N.
Neural networks for optimal approximation of smooth and analytic functions
优化平滑函数和解析函数近似的神经网络
Neural Computation, 8 (1) (1996), pp. 164-177
神经计算》，8 (1) (1996)，第 164-177 页
CrossRef View in Scopus Google Scholar
CrossRef 查看 ScopusGoogle Scholar
Mhaskar (1993) 马斯卡（1993 年）
Mhaskar Hrushikesh Narhar
Approximation properties of a multilayered feedforward artificial neural network
多层前馈人工神经网络的逼近特性
Advances in Computational Mathematics, 1 (1) (1993), pp. 61-80
计算数学进展》，1 (1) (1993)，第 61-80 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Mhaskar et al. (2016) Mhaskar 等人（2016 年）
Mhaskar, Hrushikesh, Liao, Qianli, & Poggio, Tomaso (2016). Learning Real and Boolean Functions: When Is Deep Better Than Shallow. ArXiv Preprint ArXiv:1603.00988.
Mhaskar, Hrushikesh, Liao, Qianli, & Poggio, Tomaso (2016).学习实函数和布尔函数：什么时候 "深 "比 "浅 "更好？ArXiv Preprint ArXiv:1603.00988.
Google Scholar 谷歌学者
Mhaskar and Poggio (2016)
Mhaskar 和 Poggio（2016 年）
Mhaskar, Hrushikesh, & Poggio, Tomaso (2016). Deep vs. shallow networks: An approximation theory perspective. ArXiv Preprint ArXiv:1608.03287.
Mhaskar, Hrushikesh, & Poggio, Tomaso (2016).深度网络与浅层网络：近似理论视角。ArXiv Preprint ArXiv:1608.03287.
Google Scholar 谷歌学者
Montufar et al. (2014) 蒙图法尔等人（2014 年）
Montufar Guido F., Pascanu Razvan, Cho Kyunghyun, Bengio Yoshua
MontufarGuido F.、PascanuRazvan、ChoKyunghyun、BengioYoshua
On the number of linear regions of deep neural networks
关于深度神经网络的线性区域数量
Advances in Neural Information Processing Systems (2014), pp. 2924-2932
神经信息处理系统进展》（2014 年），第 2924-2932 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Pinkus (1999) 平卡斯（1999 年）
Pinkus Allan
Approximation theory of the MLP model in neural networks
神经网络中 MLP 模型的近似理论
Acta Numerica, 8 (1999), pp. 143-195
Acta Numerica, 8 (1999), pp.
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Raghu et al. (2016) 拉古等人（2016）
Raghu, Maithra, Poole, Ben, Kleinberg, Jon, Ganguli, Surya, & Sohl-Dickstein, Jascha (2016). On the expressive power of deep neural networks. ArXiv Preprint ArXiv:1606.05336.
Raghu, Maithra, Poole, Ben, Kleinberg, Jon, Ganguli, Surya, & Sohl-Dickstein, Jascha (2016)。论深度神经网络的表现力》。ArXiv Preprint ArXiv:1606.05336.
Google Scholar 谷歌学者
Sakurai (1999) 樱井（1999）
Sakurai Akito 樱井树人
Tight Bounds for the VC-Dimension of Piecewise Polynomial Networks
片断多项式网络 VC 维度的严格界限
Advances in Neural Information Processing Systems (1999), pp. 323-329
神经信息处理系统进展》（1999 年），第 323-329 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Schmidhuber (2015) 施密德胡贝尔（2015）
Schmidhuber Jürgen 施密特胡贝尔-于尔根
Deep learning in neural networks: an overview
神经网络中的深度学习：概述
Neural Networks, 61 (2015), pp. 85-117
神经网络》，61 (2015)，第 85-117 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看
Shannon (1949) 香农（1949 年）
Shannon Claude 香农-克劳德
The synthesis of two-terminal switching circuits
双端开关电路的合成
Bell Labs Technical Journal, 28 (1) (1949), pp. 59-98
贝尔实验室技术期刊》，28 (1) (1949)，第 59-98 页
CrossRef View in Scopus Google Scholar
CrossRef 查看 ScopusGoogle Scholar
Telgarsky (2015)
Telgarsky, Matus (2015). Representation Benefits of Deep Feedforward Networks. ArXiv Preprint ArXiv:1509.08101.
Telgarsky, Matus (2015).深度前馈网络的表征优势》。ArXiv Preprint ArXiv:1509.08101.
Google Scholar 谷歌学者
Telgarsky (2016) 特尔加斯基（2016）
Telgarsky, Matus (2016). Benefits of depth in neural networks. ArXiv Preprint ArXiv:1602.04485.
Telgarsky, Matus (2016).神经网络深度的好处。ArXiv Preprint ArXiv:1602.04485.
Google Scholar 谷歌学者
Vapnik and Chervonenkis (2015)
Vapnik 和 Chervonenkis（2015 年）
Vapnik Vladimir N., Chervonenkis A. Ya
VapnikVladimir N., ChervonenkisA.雅
On the uniform convergence of relative frequencies of events to their probabilities
论事件相对频率向其概率的均匀趋同
Measures of complexity, Springer (2015), pp. 11-30
复杂性的度量》，施普林格出版社（2015 年），第 11-30 页
CrossRef Google Scholar 谷歌学者
Warren (1968) 沃伦（1968）
Warren Hugh E.
Lower bounds for approximation by nonlinear manifolds
非线性流形近似的下限
Transactions of the American Mathematical Society, 133 (1) (1968), pp. 167-178
美国数学学会论文集》，133 (1) (1968)，第 167-178 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

Cited by (1209) 引用 (1209)

MAIAC AOD profiling over the Persian Gulf: A seasonal-independent machine learning approach
波斯湾上空的 MAIAC AOD 分析：与季节无关的机器学习方法
2024, Atmospheric Pollution Research
2024 年，大气污染研究
Aerosol Optical Depth (AOD) across various altitudes is crucial for gaining a comprehensive understanding of aerosol dynamics. However, current methodologies utilizing passive remote sensing and active sensors have limitations in providing precise vertical coverage. In our methodology, we introduce a Seasonal-Independent model employing Machine Learning (ML) algorithms to retrieve AOD values at both 1.5 km and 3 km layers. The propose approach is assessed the performance of various ML algorithms, including XGBoost, Random Forest (RF), Multilayer Perceptron (MLP), and Support Vector Regression (SVR). Remarkably, our study successfully overcame seasonal constraints, yielding impressive $R^{2}$ values of 0.94, 0.93, 0.93, and 0.87 for the 1.5 km layer, and 0.83, 0.79, 0.82, and 0.78 for the 3 km layer across the mentioned models for 2017, 2018 and 2019 data. Evaluating the proposed Seasonal-Independent XGBoost model against CALIOP AOD values for the 2020 data, we observed substantial agreement with $R^{2}$ values of 0.93 and 0.81, and minimal RMSE values of 0.002 and 0.004 for the AODs at 1.5 km and 3 km, respectively. Furthermore, a comparative analysis of trends between estimated and CALIOP AODs revealed a strong resemblance in both altitude layers.
Solving PDEs on unknown manifolds with machine learning
用机器学习解决未知流形上的多项式方程
2024, Applied and Computational Harmonic Analysis
2024，应用与计算谐波分析
This paper proposes a mesh-free computational framework and machine learning theory for solving elliptic PDEs on unknown manifolds, identified with point clouds, based on diffusion maps (DM) and deep learning. The PDE solver is formulated as a supervised learning task to solve a least-squares regression problem that imposes an algebraic equation approximating a PDE (and boundary conditions if applicable). This algebraic equation involves a graph-Laplacian type matrix obtained via DM asymptotic expansion, which is a consistent estimator of second-order elliptic differential operators. The resulting numerical method is to solve a highly non-convex empirical risk minimization problem subjected to a solution from a hypothesis space of neural networks (NNs). In a well-posed elliptic PDE setting, when the hypothesis space consists of neural networks with either infinite width or depth, we show that the global minimizer of the empirical loss function is a consistent solution in the limit of large training data. When the hypothesis space is a two-layer neural network, we show that for a sufficiently large width, gradient descent can identify a global minimizer of the empirical loss function. Supporting numerical examples demonstrate the convergence of the solutions, ranging from simple manifolds with low and high co-dimensions, to rough surfaces with and without boundaries. We also show that the proposed NN solver can robustly generalize the PDE solution on new data points with generalization errors that are almost identical to the training errors, superseding a Nyström-based interpolation method.
Short-term load forecasting based on CEEMDAN and dendritic deep learning
基于 CEEMDAN 和树枝状深度学习的短期负荷预测
2024, Knowledge-Based Systems
2024 年，知识型系统
Short-term load forecasting (STLF) plays a key role in improving the operational efficiency of real-time electricity markets by reducing load uncertainty, optimising the allocation of generation resources and increasing the reliability of electricity supply. Despite significant advances in the field, achieving high accuracy in STLF remains a challenge due to the inherent complexity and volatility of load data. This study proposes a novel STLF method that synergistically combines the strengths of a dendritic neuron model (DNM), long short-term memory, and complete ensemble empirical mode decomposition with adaptive noise (CEEMDAN) to address these challenges. First, historical load data is decomposed into components of different frequencies using CEEMDAN. Then, LSTM is used to extract the temporal characteristics of these load subsequence components in combination with various influencing factors such as temperature and humidity. Uniquely, this study innovatively integrates a dendritic neuron model instead of the traditional fully connected layer, a structural innovation that enhances the model’s ability to explore the intrinsic correlations of the time series data in depth. This allows the model to process and predict each component individually, and then later reconstruct and sum these independent prediction results to obtain a final prediction value with higher accuracy. Experiments are conducted on the Panama electricity load dataset to compare the proposed dendritic learning model with several state-of-the-art models, including CrossFormer and Transformer. The results confirm that the proposed model has significantly better prediction accuracy.
Approximation of functions from Korobov spaces by shallow neural networks
浅层神经网络对科罗波夫空间函数的逼近
2024, Information Sciences
2024 年，信息科学
In this paper, we consider the problem of approximating functions from a Korobov space on ${[- 1, 1]}^{d}$ by ReLU shallow neural networks and present a rate $O (m^{- \frac{2}{5} (1 + \frac{2}{d})} \sqrt{\log m})$ of uniform approximation by networks of m hidden neurons. This is achieved by combining a novel Fourier analysis approach and a probability argument. We apply our approximation theory to a learning algorithm for regression based on ReLU shallow neural networks and derive learning rates of order $O (N^{- \frac{4 (d + 2)}{9 d + 8}} \log N)$ for the excess generalization error with the sample size N when the regression function lies in the Korobov space.
Generalization analysis of deep CNNs under maximum correntropy criterion
最大熵标准下深度 CNN 的泛化分析
2024, Neural Networks 2024, 神经网络
Convolutional neural networks (CNNs) have gained immense popularity in recent years, finding their utility in diverse fields such as image recognition, natural language processing, and bio-informatics. Despite the remarkable progress made in deep learning theory, most studies on CNNs, especially in regression tasks, tend to heavily rely on the least squares loss function. However, there are situations where such learning algorithms may not suffice, particularly in the presence of heavy-tailed noises or outliers. This predicament emphasizes the necessity of exploring alternative loss functions that can handle such scenarios more effectively, thereby unleashing the true potential of CNNs. In this paper, we investigate the generalization error of deep CNNs with the rectified linear unit (ReLU) activation function for robust regression problems within an information-theoretic learning framework. Our study demonstrates that when the regression function exhibits an additive ridge structure and the noise possesses a finite $p$ th moment, the empirical risk minimization scheme, generated by the maximum correntropy criterion and deep CNNs, achieves fast convergence rates. Notably, these rates align with the mini-max optimal convergence rates attained by fully connected neural network model with the Huber loss function up to a logarithmic factor. Additionally, we further establish the convergence rates of deep CNNs under the maximum correntropy criterion when the regression function resides in a Sobolev space on the sphere.
Low dimensional approximation and generalization of multivariate functions on smooth manifolds using deep ReLU neural networks
利用深度 ReLU 神经网络实现平滑流形上多元函数的低维逼近和泛化
2024, Neural Networks 2024, 神经网络
The expressive power of deep neural networks is manifested by their remarkable ability to approximate multivariate functions in a way that appears to overcome the curse of dimensionality. This ability is exemplified by their success in solving high-dimensional problems where traditional numerical solvers fail due to their limitations in accurately representing high-dimensional structures. To provide a theoretical framework for explaining this phenomenon, we analyze the approximation of Hölder functions defined on a $d$ -dimensional smooth manifold $M$ embedded in $R^{D}$ , with $d ≪ D$ , using deep neural networks. We prove that the uniform convergence estimates of the approximation and generalization errors by deep neural networks with ReLU activation functions do not depend on the ambient dimension $D$ of the function but only on its lower manifold dimension $d$ , in a precise sense. Our result improves existing results from the literature where approximation and generalization errors were shown to depend weakly on $D$ .

View all citing articles on Scopus
查看 Scopus 上的所有引用文章

¹: The author thanks Matus Telgarsky for suggesting this part of the theorem.
作者感谢 Matus Telgarsky 提出这部分定理。

View Abstract 查看摘要

[1] Anthony and Bartlett (2009)
安东尼和巴特利特（2009 年）
Anthony Martin, Bartlett Peter L.
安东尼-马丁、巴特利特-彼得-L.
Neural network learning: Theoretical foundations
神经网络学习：理论基础
Cambridge University Press (2009)
剑桥大学出版社（2009 年）
Google Scholar 谷歌学者

[2] Bartlett et al. (1998) 巴特利特等人（1998 年）
Bartlett Peter L., Maiorov Vitaly, Meir Ron
巴特利特-彼得-L, 马约洛夫-维塔利, 梅尔-龙
Almost linear VC-dimension bounds for piecewise polynomial networks
片断多项式网络的几乎线性 VC 维度边界
Neural Computation, 10 (8) (1998), pp. 2159-2173
神经计算》，10 (8) (1998)，第 2159-2173 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[3] Bianchini and Scarselli (2014)
比安奇尼和斯卡塞利（2014 年）
Bianchini Monica, Scarselli Franco
On the complexity of neural network classifiers: a comparison between shallow and deep architectures
神经网络分类器的复杂性：浅层架构与深层架构的比较
IEEE Transactions on Neural Networks and Learning Systems, 25 (8) (2014), pp. 1553-1565
电气和电子工程师学会神经网络与学习系统论文集》，25 (8) (2014)，第 1553-1565 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[4] Cohen et al. (2015) 科恩等人（2015 年）
Cohen, Nadav, Sharir, Or, & Shashua, Amnon (2015). On the Expressive Power of Deep Learning: A Tensor Analysis. ArXiv preprint ArXiv:1509.05009.
Cohen, Nadav, Sharir, Or, & Shashua, Amnon (2015)。深度学习的表现力：张量分析》。ArXiv preprint ArXiv:1509.05009.
Google Scholar 谷歌学者

[5] Dawson and Nielsen (2006)
道森和尼尔森（2006 年）
Dawson C.M., Nielsen M.A.
The Solovay-Kitaev algorithm
索洛维-基塔耶夫算法
Quantum Information & Computation, 6 (1) (2006), pp. 81-95
量子信息与计算》，6 (1) (2006)，第 81-95 页
CrossRef Google Scholar 谷歌学者

[6] Delalleau and Bengio (2011)
Delalleau 和 Bengio（2011 年）
Delalleau Olivier, Bengio Yoshua
Shallow vs. deep sum-product networks
浅层与深层和积网络
Advances in Neural Information Processing Systems (2011), pp. 666-674
神经信息处理系统进展》（2011 年），第 666-674 页
Google Scholar 谷歌学者

[7] DeVore et al. (1989) DeVore 等人（1989 年）
DeVore Ronald A., Howard Ralph, Micchelli Charles
Optimal nonlinear approximation
最佳非线性近似
Manuscripta Mathematica, 63 (4) (1989), pp. 469-478
Manuscripta Mathematica》，63 (4) (1989)，第 469-478 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[8] Goldberg and Jerrum (1995)
戈德伯格和杰鲁姆（1995 年）
Goldberg Paul W., Jerrum Mark R.
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
以实数为参数的概念类的 Vapnik-Chervonenkis 维度范围
Machine Learning, 18 (2–3) (1995), pp. 131-148
机器学习》，18 (2-3) (1995)，第 131-148 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[9] Kainen et al. (1999) 凯宁等人（1999 年）
Kainen Paul C., Kůrková Věra, Vogt Andrew
凯宁-保罗-C.、库尔科瓦-维拉、沃格特-安德鲁
Approximation by neural networks is not continuous
神经网络的逼近不是连续的
Neurocomputing, 29 (1) (1999), pp. 47-56
神经计算》，29 (1) (1999)，第 47-56 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[10] Kearns and Schapire (1990)
卡恩斯和沙皮尔（1990 年）
Kearns Michael J., Schapire Robert E.
Efficient distribution-free learning of probabilistic concepts
概率概念的高效无分布学习
Foundations of computer science, 1990. Proceedings., 31st annual symposium on, IEEE (1990), pp. 382-391
计算机科学基础，1990 年。第 31 届年度研讨会，IEEE (1990)，第 382-391 页
Google Scholar 谷歌学者

[11] Kitaev et al. (2002) Kitaev 等人（2002 年）
Kitaev A. Yu., Shen A.H., Vyalyi M.N.
KitaevA.Yu.、ShenA.H.、VyalyiM.N.
Classical and quantum computation
经典计算和量子计算
0821832298, American Mathematical Society, Boston, MA, USA (2002)
0821832298，美国数学学会，美国马萨诸塞州波士顿（2002 年）
Google Scholar 谷歌学者

[12] LeCun et al. (2015) LeCun 等人（2015 年）
LeCun Yann, Bengio Yoshua, Hinton Geoffrey
Deep learning 深度学习
Nature, 521 (7553) (2015), pp. 436-444
自然》，521 (7553) (2015)，第 436-444 页
CrossRef View in Scopus Google Scholar
CrossRef 查看 ScopusGoogle Scholar

[13] Liang and Srikant (2016) 梁和斯里康特（2016）
Liang, Shiyu, & Srikant, R. (2016). Why Deep Neural Networks? ArXiv Preprint ArXiv:1610.04161.
Liang, Shiyu, & Srikant, R. (2016)。为什么选择深度神经网络？ArXiv Preprint ArXiv:1610.04161.
Google Scholar 谷歌学者

[14] Maiorov and Meir (2000) Maiorov 和 Meir（2000 年）
Maiorov V.E., Meir Ron
On the near optimality of the stochastic approximation of smooth functions by neural networks
论神经网络随机逼近平滑函数的近似最优性
Advances in Computational Mathematics, 13 (1) (2000), pp. 79-103
计算数学进展》，13 (1) (2000)，第 79-103 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[15] Mhaskar (1996) 马斯卡（1996 年）
Mhaskar H.N.
Neural networks for optimal approximation of smooth and analytic functions
优化平滑函数和解析函数近似的神经网络
Neural Computation, 8 (1) (1996), pp. 164-177
神经计算》，8 (1) (1996)，第 164-177 页
CrossRef View in Scopus Google Scholar
CrossRef 查看 ScopusGoogle Scholar

[16] Mhaskar (1993) 马斯卡（1993 年）
Mhaskar Hrushikesh Narhar
Approximation properties of a multilayered feedforward artificial neural network
多层前馈人工神经网络的逼近特性
Advances in Computational Mathematics, 1 (1) (1993), pp. 61-80
计算数学进展》，1 (1) (1993)，第 61-80 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[17] Mhaskar et al. (2016) Mhaskar 等人（2016 年）
Mhaskar, Hrushikesh, Liao, Qianli, & Poggio, Tomaso (2016). Learning Real and Boolean Functions: When Is Deep Better Than Shallow. ArXiv Preprint ArXiv:1603.00988.
Mhaskar, Hrushikesh, Liao, Qianli, & Poggio, Tomaso (2016).学习实函数和布尔函数：什么时候 "深 "比 "浅 "更好？ArXiv Preprint ArXiv:1603.00988.
Google Scholar 谷歌学者

[18] Mhaskar and Poggio (2016)
Mhaskar 和 Poggio（2016 年）
Mhaskar, Hrushikesh, & Poggio, Tomaso (2016). Deep vs. shallow networks: An approximation theory perspective. ArXiv Preprint ArXiv:1608.03287.
Mhaskar, Hrushikesh, & Poggio, Tomaso (2016).深度网络与浅层网络：近似理论视角。ArXiv Preprint ArXiv:1608.03287.
Google Scholar 谷歌学者

[19] Montufar et al. (2014) 蒙图法尔等人（2014 年）
Montufar Guido F., Pascanu Razvan, Cho Kyunghyun, Bengio Yoshua
MontufarGuido F.、PascanuRazvan、ChoKyunghyun、BengioYoshua
On the number of linear regions of deep neural networks
关于深度神经网络的线性区域数量
Advances in Neural Information Processing Systems (2014), pp. 2924-2932
神经信息处理系统进展》（2014 年），第 2924-2932 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[20] Pinkus (1999) 平卡斯（1999 年）
Pinkus Allan
Approximation theory of the MLP model in neural networks
神经网络中 MLP 模型的近似理论
Acta Numerica, 8 (1999), pp. 143-195
Acta Numerica, 8 (1999), pp.
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[21] Raghu et al. (2016) 拉古等人（2016）
Raghu, Maithra, Poole, Ben, Kleinberg, Jon, Ganguli, Surya, & Sohl-Dickstein, Jascha (2016). On the expressive power of deep neural networks. ArXiv Preprint ArXiv:1606.05336.
Raghu, Maithra, Poole, Ben, Kleinberg, Jon, Ganguli, Surya, & Sohl-Dickstein, Jascha (2016)。论深度神经网络的表现力》。ArXiv Preprint ArXiv:1606.05336.
Google Scholar 谷歌学者

[22] Sakurai (1999) 樱井（1999）
Sakurai Akito 樱井树人
Tight Bounds for the VC-Dimension of Piecewise Polynomial Networks
片断多项式网络 VC 维度的严格界限
Advances in Neural Information Processing Systems (1999), pp. 323-329
神经信息处理系统进展》（1999 年），第 323-329 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[23] Schmidhuber (2015) 施密德胡贝尔（2015）
Schmidhuber Jürgen 施密特胡贝尔-于尔根
Deep learning in neural networks: an overview
神经网络中的深度学习：概述
Neural Networks, 61 (2015), pp. 85-117
神经网络》，61 (2015)，第 85-117 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

[24] Shannon (1949) 香农（1949 年）
Shannon Claude 香农-克劳德
The synthesis of two-terminal switching circuits
双端开关电路的合成
Bell Labs Technical Journal, 28 (1) (1949), pp. 59-98
贝尔实验室技术期刊》，28 (1) (1949)，第 59-98 页
CrossRef View in Scopus Google Scholar
CrossRef 查看 ScopusGoogle Scholar

[25] Telgarsky (2015)
Telgarsky, Matus (2015). Representation Benefits of Deep Feedforward Networks. ArXiv Preprint ArXiv:1509.08101.
Telgarsky, Matus (2015).深度前馈网络的表征优势》。ArXiv Preprint ArXiv:1509.08101.
Google Scholar 谷歌学者

[26] Telgarsky (2016) 特尔加斯基（2016）
Telgarsky, Matus (2016). Benefits of depth in neural networks. ArXiv Preprint ArXiv:1602.04485.
Telgarsky, Matus (2016).神经网络深度的好处。ArXiv Preprint ArXiv:1602.04485.
Google Scholar 谷歌学者

[27] Vapnik and Chervonenkis (2015)
Vapnik 和 Chervonenkis（2015 年）
Vapnik Vladimir N., Chervonenkis A. Ya
VapnikVladimir N., ChervonenkisA.雅
On the uniform convergence of relative frequencies of events to their probabilities
论事件相对频率向其概率的均匀趋同
Measures of complexity, Springer (2015), pp. 11-30
复杂性的度量》，施普林格出版社（2015 年），第 11-30 页
CrossRef Google Scholar 谷歌学者

[28] Warren (1968) 沃伦（1968）
Warren Hugh E.
Lower bounds for approximation by nonlinear manifolds
非线性流形近似的下限
Transactions of the American Mathematical Society, 133 (1) (1968), pp. 167-178
美国数学学会论文集》，133 (1) (1968)，第 167-178 页
View in Scopus Google Scholar
在 ScopusGoogle Scholar 中查看

Outline 概要

Cited by (1209) 引用 (1209)

Figures (9) 数字 (9)

Neural Networks 神经网络

Abstract 摘要

Keywords 关键词

1. Introduction 1.导言

2. The ReLU network model
2.ReLU 网络模型

3. Upper bounds 3.上限

3.1. Fast deep approximation of squaring and multiplication
3.1.平方和乘法的快速深度逼近

3.2. Fast deep approximation of general smooth functions
3.2.一般光滑函数的快速深度逼近

3.3. Faster approximations using adaptive network architectures
3.3.利用自适应网络架构实现更快近似

4. Lower bounds 4.下限

4.1. Continuous nonlinear widths
4.1.连续非线性宽度

DeVore et al., (1989), Theorem 4.2
DeVore 等人，（1989 年），定理 4.2

4.2. Bounds based on VC-dimension
4.2.基于 VC 维度的界限

4.3. Adaptive network architectures
4.3.自适应网络架构

Proof of Theorem 5 定理 5 的证明

4.4. Slow approximation of smooth functions by shallow networks
4.4.浅层网络对平滑函数的缓慢逼近

5. Discussion 5.讨论

Deep vs. shallow ReLU approximations of smooth functions
平滑函数的深层 ReLU 近似与浅层 ReLU 近似

Continuous model selection vs. function-dependent network architectures
连续模型选择与依赖功能的网络架构对比

Upper vs. lower complexity bounds
复杂度上限与下限

ReLU vs. smooth activation functions
ReLU 与平滑激活函数

6. Conclusion 6.结论

Acknowledgments 致谢

References 参考资料

Cited by (1209) 引用 (1209)

MAIAC AOD profiling over the Persian Gulf: A seasonal-independent machine learning approach
波斯湾上空的 MAIAC AOD 分析：与季节无关的机器学习方法

Solving PDEs on unknown manifolds with machine learning
用机器学习解决未知流形上的多项式方程

Short-term load forecasting based on CEEMDAN and dendritic deep learning
基于 CEEMDAN 和树枝状深度学习的短期负荷预测

Approximation of functions from Korobov spaces by shallow neural networks
浅层神经网络对科罗波夫空间函数的逼近

Generalization analysis of deep CNNs under maximum correntropy criterion
最大熵标准下深度 CNN 的泛化分析

Low dimensional approximation and generalization of multivariate functions on smooth manifolds using deep ReLU neural networks
利用深度 ReLU 神经网络实现平滑流形上多元函数的低维逼近和泛化

Error bounds for approximations with deep ReLU networks深度 ReLU 网络近似的误差边界

Abstract 摘要

Keywords 关键词

1. Introduction 1.导言

2. The ReLU network model2.ReLU 网络模型

3. Upper bounds 3.上限

3.1. Fast deep approximation of squaring and multiplication3.1.平方和乘法的快速深度逼近

3.2. Fast deep approximation of general smooth functions3.2.一般光滑函数的快速深度逼近

3.3. Faster approximations using adaptive network architectures3.3.利用自适应网络架构实现更快近似

4. Lower bounds 4.下限

4.1. Continuous nonlinear widths4.1.连续非线性宽度

DeVore et al., (1989), Theorem 4.2DeVore 等人，（1989 年），定理 4.2

4.2. Bounds based on VC-dimension4.2.基于 VC 维度的界限

4.3. Adaptive network architectures4.3.自适应网络架构

Proof of Theorem 5 定理 5 的证明

4.4. Slow approximation of smooth functions by shallow networks4.4.浅层网络对平滑函数的缓慢逼近

5. Discussion 5.讨论

Deep vs. shallow ReLU approximations of smooth functions平滑函数的深层 ReLU 近似与浅层 ReLU 近似

Continuous model selection vs. function-dependent network architectures连续模型选择与依赖功能的网络架构对比

Upper vs. lower complexity bounds复杂度上限与下限

ReLU vs. smooth activation functionsReLU 与平滑激活函数

6. Conclusion 6.结论

Acknowledgments 致谢

References 参考资料

Error bounds for approximations with deep ReLU networks
深度 ReLU 网络近似的误差边界

2. The ReLU network model
2.ReLU 网络模型

3.1. Fast deep approximation of squaring and multiplication
3.1.平方和乘法的快速深度逼近

3.2. Fast deep approximation of general smooth functions
3.2.一般光滑函数的快速深度逼近

3.3. Faster approximations using adaptive network architectures
3.3.利用自适应网络架构实现更快近似

4.1. Continuous nonlinear widths
4.1.连续非线性宽度

DeVore et al., (1989), Theorem 4.2
DeVore 等人，（1989 年），定理 4.2

4.2. Bounds based on VC-dimension
4.2.基于 VC 维度的界限

4.3. Adaptive network architectures
4.3.自适应网络架构

4.4. Slow approximation of smooth functions by shallow networks
4.4.浅层网络对平滑函数的缓慢逼近

Deep vs. shallow ReLU approximations of smooth functions
平滑函数的深层 ReLU 近似与浅层 ReLU 近似

Continuous model selection vs. function-dependent network architectures
连续模型选择与依赖功能的网络架构对比

Upper vs. lower complexity bounds
复杂度上限与下限

ReLU vs. smooth activation functions
ReLU 与平滑激活函数