Approximating Continuous Functions by ReLU Nets of Minimal Width

Introduction

Over the past several years, artificial neural networks, especially deep networks, have become the state of the art in a wide variety of machine learning tasks. These tasks include important benchmark problems in machine vision ([KSH12]) and machine translation ([SVL14, WSC+16]) as well as superhuman performance at games such as Go [SHM+16]. Despite these varied and striking successes, a theory of why neural nets provide such good approximations to interesting functions and can be effectively trained is only beginning to take shape.

While non-linear activations help neural nets express a wide variety of functions, repeated non-linearities can also “garble” the signal, leading to a loss of mutual information between the input and the activations at various hidden layers. Such an information theoretic point of view on neural nets has recently been systematically taken up in the work of Tishby with Shwartz-Ziv, Moshkovitz, and Zaslavsky [ST17, MT17, TZ15]. In the present article, we answer a basic information theoretic question about neural nets. Namely, for each $d\geq 1,$ what is the minimal width $w_{\text{min}}(d)$ so that neural nets whose hidden layers have width at least $w_{\text{min}}(d)$ and arbitrary depth can approximate arbitrarily well any scalar continuous function of $d$ variables? We treat only neural nets with a popular and particularly simple activation function called rectified linear units, defined

It have been known since the 1980’s (e.g. the work of Cybenko [Cyb89] and Hornik-Stinchcombe-White [HSW89]) that feed-forward neural nets with a single hidden layer can approximate essentially any function if the hidden layer is allowed to be arbitrarily wide. Such results hold for a wide variety of activations, including $\operatorname{ReLU}.$ However, part of the recent renaissance in neural nets, is the empirical observation that deep neural nets tend to achieve greater expressivity per parameter than their shallow cousins. There are now a number of rigorous results about this so-called expressive power of depth [ABMM16, MLP16, LTR17, MP16, PLR+16, RPK+17, RT17, Tel15, Tel16, Tel17, Yar16]. We refer the reader to §3 in [Han17] for a discussion of the relationships between some of these articles.

The main result of this article shows a sharp transition in the representational power of deep feed-forward neural nets with $\operatorname{ReLU}$ activations as a function of the widths of their hidden layers. To state it, we need some notation. We say that $\mathcal{N}$ is a feed-forward neural net with $\operatorname{ReLU}$ activations, input dimension $d_{in}$, output dimension $d_{out}$, and widths $d_{in}=d_{1},d_{2},\ldots,d_{k},d_{k+1}=d_{out}$ (a $\operatorname{ReLU}$ net for short) if it computes a function $f_{\mathcal{N}}$ of the form

The main result of this article is the following estimate for $w_{\text{min}}(d_{in},d_{out}).$

Proving the upper bound $w_{\text{min}}(d_{in},d_{out})\leq d_{in}+d_{out}$ in Theorem 1 requires a novel construction by which any continuous function with $d_{in}$ input variables and $d_{out}$ output variables can be approximated to arbitrary precision by a $\operatorname{ReLU}$ net with width $d_{in}+d_{out}$ and depth depending on its modulus of continuity $\omega_{f}$. Recall that $\omega_{f}(\delta)\leq\varepsilon$ when $|x-y|\leq\delta$ implies that $|f(x)-f(y)|\leq\varepsilon$ uniformly over all inputs $x,y.$ Since $\omega_{f}$ need not be continuous or bijective, define

We refer the reader to Proposition 3 for the precise statement. The construction is carried out in §2. In contrast, obtaining the lower bound

Our construction in §3 only requires that the function have some compact level set (connected component of a fiber $f^{-1}(a)$) and be non-constant inside that level set.

The first author would like to thank Zhangyang Wang for several stimulating discussions about extending the results in this article to allowing residual connections and to more general activations. We are also grateful to Dmitry Yarotsky for pointing out several inaccuracies and a mistake (now corrected) in the proof of Lemma 6 in a previous version.

Proof of the Upper Bound in Theorem 1

where each $\sigma_{i}$ is either a coordinate-wise max or a min.

The statement (3) follows immediately from the following two propositions.

Nonetheless, Proposition 3 is of a rather different nature since we are allowed to take only max and min of two affine functions at a time.

We may assume without loss of generality that $K$ is contained in the positive orthant:

since we can always shift the input to a neural net by a fixed vector. Let us fix a max-min string

is the graph of $g.$ Note that the final $\operatorname{ReLU}$ is trivial since $g$ is non-negative. Appending a final layer $(x_{1},\ldots,x_{d_{in}},y_{1},\ldots,y_{d_{out}})\mapsto\left(y_{1},\ldots,y_{d_{out}}\right)$ yields the desired net. ∎

2. Proof of Proposition 3

where the max and min are componentwise. By construction, $\widehat{g}(s_{0})=f(s_{0}).$ Further, because $t$ is large, $\widehat{g}(s)=f(s)$ for $s\in S\backslash\{s_{0}\}$. Hence $\widehat{g}$ and $f$ agree on $S$, completing the proof. ∎

such that $K$ is contained in the infinite planar sector $\angle BAC$. Then if there exists a max-min string $g$ with

then there also exists a max-min string $\widehat{g}$ with

Next, by the definition of $\omega^{-1}_{f},$ we have

We now show that this estimate continues to hold for $x\in K$ as well. We claim that on $K\cup\triangle ABC$ we have

Indeed, suppose that ray $Ax$ has length $n\omega^{-1}_{f}(\varepsilon)+r$ for integer $n$ and real remainder $r<\omega^{-1}_{f}(\varepsilon)$. Then by the triangle inequality we have

Therefore, $\widehat{g}-\varepsilon\leq f\leq\widehat{g}+\varepsilon,$ as desired. ∎

We now turn to the details of the proof of Proposition 3. We will explain how to approximate our fixed continuous function $f$ by a max-min string on a ball of radius $R>0$ centered at the origin. We will use Lemma 5 to show that we can approximate $f$ on successively larger and larger balls. Observe that if $r\leq\omega^{-1}_{f}(\varepsilon)$ then

so that the constant max-min string $f(0)$ is an $\varepsilon$-approximation to $f$ on the small ball $B_{\omega^{-1}_{f}(\varepsilon)}(0)$. To prove that we can approximate $f$ on larger balls, suppose $g$ is a max-min string on ${d_{in}}$ variables that approximates $f$ to within $\varepsilon$ on the ball $B_{r}(0)$ with $r\geq w_{f}^{-1}(\varepsilon).$ We use Lemma 5 to construct a new max-min string $\widehat{g}$ which uniformly $\varepsilon$-approximates $f$ on a ball of slightly larger radius

Since for every $\varepsilon>0,$ the function $R_{r,\varepsilon}$ is strictly increasing in $r$ it cannot have a fixed point and the $k-$fold composition $R_{r,\varepsilon}^{(k)}$ sends any $r>0$ to infinity with $k.$ Using this procedure repeatedly therefore allows us to increase $r$ without bound and will complete the proof. Our approach is illustrated in Figures 1 and 2.

We begin with the construction when ${d_{in}}=2$ and will explain the simple modification for ${d_{in}}\geq 3$ below. For each $r^{\prime}>r$ and any two sufficiently close points $X,Y$ on the boundary of $B_{r}$, let $X^{\prime},Y^{\prime}$ be the intersections of line $XY$ with the boundary circle of $B_{r^{\prime}}(P)$. Also, denote by $Z$ be the intersection of the tangents to $B_{r^{\prime}}$ through $X^{\prime},Y^{\prime}$ (see Figure 1). Then $B_{r}$ is contained in the planar sector $\angle X^{\prime}ZY^{\prime}$, and the diameter of $\triangle X^{\prime}ZY^{\prime}$ can be made arbitrarily small by taking $r^{\prime}$ close to $r$ and $X$ close to $Y.$ In particular, for every $r\geq\omega^{-1}_{f}(\varepsilon),$ we take

This choice for $|XY|$ is valid because $|XY|\leq\omega^{-1}_{f}(\varepsilon)\leq r$, so we can indeed find points $X,Y$ at this distance with no problem. Then

We also know that $|X^{\prime}Z|=|Y^{\prime}Z|\leq|X^{\prime}Y^{\prime}|=\omega^{-1}_{f}(\varepsilon)$ because $|X^{\prime}Y^{\prime}|=\omega^{-1}_{f}(\varepsilon)\leq r\leq r^{\prime}$, implying obtuseness of $\triangle X^{\prime}ZY^{\prime}$ at $Z$. Thus,

Lemma 5 therefore shows that there exists a max-min string $g^{\prime}$ that uniformly $\varepsilon$ approximates $f$ on $K^{\prime}=\triangle X^{\prime}Y^{\prime}Z\cup B_{r}.$ Notice that $K^{\prime}$ contains the circular sector of $B_{R_{r,\varepsilon}}$ cut out by the rays $OX$ and $OY.$ Finally, consider a $\delta-$net $\{p_{i}\}$ on the circumference of $B_{r}$ with

The size of this net is $O(r/\omega^{-1}_{f}(\varepsilon)).$ Applying Lemma 5 $O(r/\omega^{-1}_{f}(\varepsilon))$ times and repeating the above argument with $(X,Y)=(p_{i},p_{i+1})$ completes the proof of the upper bound in Theorem 1 when ${d_{in}}=2.$

The argument when ${d_{in}}\geq 3$ is essentially the same. The idea is to take the diagrams depicted and rotate them around the axis $PZ.$ Lemma 5 extends to higher dimensions with the triangle $\triangle ABC$ replaced by the tip of a cone with the same diameter requirement. Such a cone is obtained by rotating $X^{\prime}ZY^{\prime}$ in Figures 1 and 2. The rest of the argument then carries over verbatim.

balls. We get one extra max and min in the max-min string we build to approximate $f$ for each such ball. Thus, at a cost of $\left(\frac{O(r)}{\omega^{-1}_{f}(\varepsilon)}\right)^{{d_{in}}-1}$ many maxes and mins, the radius on which we approximate $f$ increases

Hence, if we fix $R>\omega^{-1}_{f}(\varepsilon),$ then for every $\omega^{-1}_{f}(\varepsilon)\leq r\leq R,$ we have

and to obtain an approximation of $f$ on $B_{R},$ by a max-min we need to extend the approximation of $f$ from a small ball to a larger ball at most $10R^{2}/\omega^{-1}_{f}(\varepsilon)^{2}$ times. The number of maxes and mins required for each extension is $(O(R)/\omega^{-1}_{f}(\varepsilon))^{{d_{in}}-1}$. Hence, the length of the max-min string we construct to approximate $f$ on $B_{R}$ is

We have tacitly neglected the case $d_{in}=1$. This case is the same as $d_{in}=2$ but easier. In fact here we require only

layers, which would naively correspond to $d_{in}=0$. The reason is that a $1$-dimensional ball can be increased in radius by $\omega_{f}^{-1}(\varepsilon)$ by adding only a single external line segment of length $\omega_{f}^{-1}(\varepsilon)$. In the higher dimensional cases, we need to add the external pieces mostly tangentially which requires more layers.

Proof of the Lower Bound in Theorem 1

Fix ${d_{in}}\geq 1,$ and consider a width ${d_{in}}$ $\operatorname{ReLU}$ net

computed by the first $j$ hidden layers of $\mathcal{N}$ are of a rather special form.

For each $j\geq 1$, set $S_{j}$ to be the set of points on which all ReLU evaluations throughout the evaluation of $f_{j}$ are (strictly) positive. Then $S_{j}$ is open and convex, $f_{j}$ is affine on $S_{j}$, and every level set of $f_{j}$ that is bounded is contained in $S_{j}.$

In this case $A$ is a sphere and $B$ is a ball. Suppose $y\in B$ and $f(y)=b\neq a$. Then for $\eta<\frac{|a-b|}{4}$, we show that $f$ is not $\eta$-approximable on $A\cup B$.

Set $c=\frac{a+b}{2}$, and let $C$ be the intersection of $f^{-1}(c)$ with $B$. Since $f$ is continuous, the intermediate value theorem implies that $C$ separates $y$ and $A$. Let $C^{\prime}\subseteq C$ be the boundary of any connected component of $C$ that contains $y$. Informally, $A$ surrounds $C^{\prime}$ which surrounds $y$. Now, suppose some $f_{\mathcal{N}}$ computed by a neural net satisfies

Suppose in the second case that $S_{\mathcal{N}}$ does not contain $C^{\prime}$, so there is $x\in C^{\prime}\backslash S_{\mathcal{N}}$. Then, by Lemma 6, the level set of $f_{\mathcal{N}}$ containing $x$ must be unbounded, and hence must intersect $A$ (as $A$ separates $y$ from $\infty$ and $x\in C^{\prime}$ is reachable from $y$ without intersecting A). This is again a contradiction for $\eta<\frac{|a-c|}{2}=\frac{|a-b|}{4}.$

In both cases, we showed that $f$ and $f_{\mathcal{N}}$ differed significantly; the first case used the affineness of $f_{\mathcal{N}}$ on $S_{\mathcal{N}}$ while the second used the unboundedness of level sets away from $S_{\mathcal{N}}$. We conclude that a width-$d$ net cannot uniformly approximate $f$. $\square$

References