ResNet with one-neuron hidden layers is a Universal Approximator

Introduction

Deep neural networks are central to many recent successes of machine learning, including applications such as computer vision, natural language processing, or reinforcement learning. A common trend in deep learning has been to construct larger and deeper networks, starting from the pioneer convolutional network LeNet , to networks with tens of layers such as AlexNet or VGG-Net , or recent architectures like GoogLeNet/Inception or ResNet , which may contain hundreds or thousands of layers. A typical observation is that deeper networks offer better performance. This phenomenon, at least on the training set, supports the intuition that a deeper network should have more capacity to approximate the target function, and leads to a question that has received increasing interest in the theory of deep learning: can all functions that we may care about be approximated well by a sufficiently large and deep network? In this work, we address this important question for the popular ResNet architecture.

The question of representational power of neural networks has been answered in different forms. Results in the late eighties showed that a network with a single hidden layer can approximate any continuous function with compact support to arbitrary accuracy, when the width goes to infinity . This result is referred to as the universal approximation theorem. Analogous to the classical Stone-Weierstrass theorem on polynomials or the convergence theorem on Fourier series, this theorem implies that the family of neural networks are universal approximators: we can apply neural networks to approximate any continuous function and the accuracy improves as we add more neurons in the width. More importantly, the coefficients in the network can be efficiently learned via back-propagation, providing an explicit representation of the approximation.

This classical universal approximation theorem completely relies on the power of the width increasing to infinity, i.e., “fat” networks. Current “tall” deep learning models, however, are not captured by this setting. Consequently, theoretically analyzing the benefit of depth has gained much attention in the recent literature . The main focus of these papers is to provide examples of functions that can be efficiently represented by a deep network but are hard to represent by shallow networks. These examples require exponentially many neurons in a shallow network to achieve the same approximation accuracy as a deep network with only a polynomial or linear number of neurons. Yet, these specific examples do not imply that all shallow networks can be represented by deep networks, leading to an important question:

If the number of neurons in each layer is bounded, does universal approximation hold when the depth goes to infinity?

This question has recently been studied by for fully connected networks with ReLU activation functions: if each hidden layer has at least $d+1$ neurons, where $d$ is the dimension of the input space, the universal approximation theorem holds as the depth goes to infinity. If, however, at most $d$ neurons can be used in each hidden layer, then universal approximation is impossible even with infinite depth.

In practice, other architectures have been developed to improve empirical results. A popular example is ResNet , which includes an identity mapping in addition to each layer. A first step towards a better theoretical understanding of those empirically successful models is to ask how the above question extends to them. Do the architecture variations make a difference theoretically? Due to the identity mapping, for ResNet, the width of the network remains the same as the input dimension. For a formal analysis, we stack modules of the form shown in Figure 1, and analyze how small the hidden green layers can be. The resulting width of $d$ (blue) or even less (green) stands in sharp contrast with the negative result for width $d$ for fully connected networks in ; their constructions do not transfer. Indeed, our empirical illustrations in Section 2 demonstrate that, empirically, significant differences in the representational power of narrow ResNets versus narrow fully connected networks can be observed. Our theoretical results confirm those observations.

show that ResNet enjoys universal finite-sample expressive power, i.e., ResNet can represent any classifier on any finite sample perfectly. This positive result in the discrete setting motivates our work. Their proof, however, relies on the fact that samples are “far” from each other and hence cannot be used in the setting of full functions in continuous space.

This result implies that, compared to fully connected networks, the identity mapping of ResNet indeed adds representational power for tall networks.

After performing the nonlinear transformation, we add the identity to form the input of the next layer. The resulting ResNet is a combination of several basic residual blocks and a final linear output layer:

Unlike the original architecture , we do not include any convolutional layers, max pooling or batch normalization; the above simplified architecture turns out to be sufficient for universal approximation.

A motivating example

We begin by empirically exploring the difference between narrow fully connected networks, with $d$ neurons per hidden layer, and ResNet via a simple example: classifying the unit ball in the plane.

We artificially create a margin between positive and negative samples to make the classification task easier. We use logistic loss as the loss $\frac{1}{n}\sum\log(1+e^{-y_{i}\hat{y_{i}}})$, where $\hat{y_{i}}=f_{\mathcal{N}}(z_{i})$ is the output of the network on the $i$-th sample. After training, we illustrate the learned decision boundaries of the networks for various depths. Ideally, we would expect the decision boundaries of our models to be close to the true distribution, i.e., the unit ball.

Figure 2 shows the results. For the fully connected networks (top row), the learned decision boundaries have roughly the same shape for different depths: the approximation quality seems to not improve with increasing depth. While one may be inclined to argue that this is due to local optimality, our observation agrees with the results in :

In other words, the level set of a narrow fully connected network is either unbounded or has measure zero.

The proof is a direct application of Theorem 2 of , see Appendix E. Thus, even when the depth goes to infinity, a narrow fully connected network can never approximate a bounded region. Here we only show the case $d=2$ because we can easily visualize the data; the same observation will still hold in higher dimensions. A even stronger result has been developed very recently showing that any connected component of the decision boundaries obtained by a narrow fully connected network is unbounded .

The decision boundaries for ResNet appear strikingly different: despite the even narrower width of one, from 2 hidden layers onwards, the ResNet represents the indicator of a bounded region. With increasing depth, the decision boundary seems to converge to the unit ball, implying that Proposition 2.1 cannot hold for ResNet. These observations motivate the universal approximation theorem that we will show in the next section.

Universal approximation theorem

In this section, we present the universal approximation theorem for ResNet with one-neuron hidden layers. We sketch the proof in the one-dimensional case; the induction for higher dimensions relies on similar ideas and builds on it.

Sketch of the proof when 𝒅=𝟏𝒅1\bm{d=1}.

We start with the one-dimensional case, which is central to our construction. As mentioned above, it is sufficient to approximate piecewise constant functions. Given a piecewise constant function $h$, there is a subdivision $-\infty<a_{0}<a_{1}<\cdots<a_{M}<+\infty$ such that

where $h_{k}$ is the constant value on the $k$-th subdivision $I_{k}=[a_{k-1},a_{k})$. We will approximate $h$ via trapezoid functions of the following form, shown in Figure 3.

A trapezoid function is a simple continuous approximation of the indicator function. It is constant on the segment $I_{k}^{\delta}=[a_{k-1}+\delta,a_{k}-\delta]$ and linear in the $\delta$-tolerant region $I_{k}\backslash I_{k}^{\delta}$. As $\delta$ goes to zero, the trapezoid function tends point-wisely to the indicator function.

A natural idea to approximate $h$ is to construct a trapezoid function on each subdivision $I_{k}$ and to then sum them up. This is the main strategy used in to show a universal approximation theorem for fully connected networks with width at least $d+1$. However, this strategy is not applicable for the ResNet structure because the summation requires memory of past components, and hence requires additional units in every layer. The width constraint of ResNet due to the identity mapping makes the difference here.

In contrast, we construct our approximation in a sequential way: we build the components of the trapezoid function one after another. Due to the sequential construction, we can only build increasing trapezoid functions as shown in Figure 4. Such functions are trapezoidal on each subdivision $I_{k}$ and the constant value on $I_{k}^{\delta}$ increases when $k$ grows. The construction relies on the following basic operations:

The following operations are realizable by a single basic residual block of ResNet with one neuron:

where $R$ represents the input layer in the basic residual block and $R^{+}$ the output layer.

Geometrically, operation (a) allows us to shift the function by a constant; operation (b) allows us to remove the level set $\{R\geq c\}$ or $\{R\leq c\}$ and operation (c) can be used to adjust the slope. With these basic operations at hand, we construct the increasing trapezoid function by induction on the subdivisions. For any $m\in[0,M]$, we construct a function $R_{m}$ satisfying

$R_{m}$ is a trapezoid function on each $I_{k}$, for any $k=1,\cdots,m$.

$R_{m}=(k+1)\|h\|_{\infty}\,\,$ on $\,\,I_{k}^{\delta}=[a_{k-1}+\delta,a_{k}-\delta]$ for any $k=1,\cdots,m$.

$R_{m}$ is bounded on $(-\infty,a_{m}]$ by $0\leq R_{m}\leq(m+1)\|h\|_{\infty}$.

$R_{m}(x)=-\frac{(m+1)\|h\|_{\infty}}{\delta}(x-a_{m})$ if $x\in[a_{m},+\infty)$,

where $\displaystyle\|h\|_{\infty}=\max_{k=1\cdots M}|h_{k}|$ is the infinity norm and $\delta>0$ measures the quality of the approximation. A geometric illustration of $R_{m}$ is shown in Figure 5. On the first $m$ subdivisions, $R_{m}$ is the restriction of the desired increasing trapezoid function. On $[a_{m},+\infty)$, the function $R_{m}$ is a very steep linear function with negative slope that enables the construction of next subdivision.

Given $R_{m}$, we sequentially stack three residual blocks to build $R_{m+1}$:

$R_{m}^{+}=\max\left\{R_{m},-\left(1+\frac{1}{m+1}\right)R_{m}\right\}$;

$R_{m}^{++}=\min\left\{R_{m}^{+},-R_{m}^{+}+\frac{(m+2)\|h\|_{\infty}}{\delta}(a_{m+1}-a_{m})\right\}$;

$R_{m+1}=\min\{R_{m}^{++},(m+2)\|h\|_{\infty}\}$.

Figure 5 illustrates the effect of these blocks: the first operation flips the linear part on $[a_{m},+\infty)$ by adjusting the slope, the second operation folds the linear function in the middle of $[a_{m},a_{m+1}]$, and finally we cut off the peak at the appropriate level $(m+2)\|h\|_{\infty}$.

An important consideration is that we need to keep the function on previous subdivisions unchanged while building the next trapezoid function. We achieve this by increasing the function values. The different values will be the basis for adjusting the function value in each subdivision to the final value of the target function we want to approximate. Before proceeding with the adjustment, we remark that $R_{M}$ goes to $-\infty$ as $x\to\infty$. This negative “tail” is easily removed by performing a cut-off operation via the max operator. This gives us the desired increasing trapezoid function $R_{M}^{*}$.

To adjust the function values on the intervals $I_{k}^{\delta}$, we identify the $I_{k}^{\delta}$ via the level sets of $R_{M}^{*}$. This works because, by construction, $R_{M}^{*}=(k+1)\|h\|_{\infty}$ on $I_{k}^{\delta}$. More precisely, we define the level sets $L_{k}=\{k\|h\|_{\infty}<R_{M}^{*}\leq(k+1)\|h\|_{\infty}\}$ (for $k=0,\cdots,M$) and adjust them one by one from highest to lowest value: for any $k=M,\cdots,1$, we sequentially build

Figure 6 shows an illustration. In particular, the first step only scales the top level set because the ReLU activation $[R_{M}-M|h|_{\infty}]_{+}$ is active if and only if $x\in L_{M}$. The coefficients are appropriately selected such that after the scaling, the constant in $I_{M}^{\delta}$ matches $h_{M}$. Hence, we have

Next, we set the second largest level set to $h_{M-1}$, and so on. As a result, the function $R_{0}^{*}$, obtained after rescaling all the level sets is the desired approximation of the piecewise constant function $h$. Concretely, we show that $R_{0}^{*}$ satisfies

$R_{0}^{*}=0$ on $(-\infty,a_{0}]$ and $[a_{M},+\infty)$.

$R_{0}^{*}=h_{k}\,\,$ on $\,\,I_{k}^{\delta}=[a_{k-1}+\delta,a_{k}-\delta]$ for any $k=1,\cdots,M$.

$R_{0}^{*}$ is bounded with $-\|h\|_{\infty}\leq R_{0}^{*}\leq\|h\|_{\infty}$.

The detailed proof is deferred to the appendix. Importantly, our construction is valid for any small enough $\delta$ satisfying $\displaystyle 0<2\delta<\min_{k=1,\cdots,M}\{a_{k}-a_{k-1}\}$. Hence, the approximation error, which is bounded by

can be made arbitrarily small by taking $\delta$ to . This completes the proof.

Extension to higher dimensions.

The last step of the one-dimensional construction is performed by sliding through all the grid cells and adjusting the function value sequentially. This procedure can be done regardless of the dimension. Therefore, it suffices to build a $d$-dimensional grid indicator function, which is a generalization of the increasing trapezoid function in high dimension space, see Definition B.4.

We perform an induction over dimensions and the main idea is to sum up an appropriate one-dimensional grid indicator function and an appropriate $d-1$ dimensional grid indicator function, as illustrated in Figure 7.

The summation gives the desired shape inside each grid cell. However, it also makes some regions positive that were previously zero. We address this issue via another separate level set property: there is a threshold $T$ such that a) the function value inside each $I_{k}^{\delta}$ is larger than $T$; b) the function values outside the grid cells are smaller than $T$. Therefore, the desired grid indicator function can be obtained by performing a max operator with the threshold $T$, i.e., cutting off the smaller values and setting them to zero (see Appendix C).

Number of neurons/layers.

A straightforward consequence of our construction is that we can approximate any piecewise constant function to arbitrary accuracy with a ResNet of $O(\text{number of grid cells})$ hidden units/layers. The most space-consuming procedure is the function adjusting procedure which requires going through each of the grid cells one by one. Nevertheless, it is worth remarking that this procedure can be parallelized if we allow more hidden units per layer.

Deriving an exact relationship between the original target function $f$ and the required number of grid cells is nontrivial and is highly dependent on characteristics of $f$. In particular, when the function $f$ is continuous, this number is related to the modulus of continuity of $f$ defined by

where $K$ is any compact set and $r$ represents the radius of the discretization. Given a desired approximation accuracy $\epsilon$, we need to

second, determine $r$ such that $\omega_{K}(r)\leq\epsilon/\text{Vol}(K)$.

Then, the number of grid cells is $O(1/r^{d})$. This dependence is suboptimal in the exponent, and it may be possible to improve it using a similar strategy as . Also, by imposing stronger smoothness assumptions, this number may be reducible dramatically . These improvements are not the main focus of this paper, and we leave them for future work.

Discussion and concluding remarks

In this paper, we have shown the universal approximation theorem of the ResNet structure with one unit per hidden layer. This result stands in contrast to recent results on fully connected networks, for which universal approximation fails with width $d$ or less. To conclude, we add some final remarks and implications.

While we achieve universal approximation with only one hidden neuron in each basic residual block, one may argue that the structure of ResNet still passes the identity to the next layer. This identity map could be counted as $d$ hidden units, resulting in a total of $d+1$ hidden unites per residual block, and could be viewed as making the network a width ($d+1$) fully connected network. But, even from this angle, ResNet corresponds to a compressed or sparse version of a fully connected network. In particular, a width ($d+1$) fully connected network has $O(d^{2})$ connections per layer, whereas only $O(d)$ connections are present in ResNet thanks to the identity map. This “overparametrization” of fully connected networks may be a patrial explanation why dropout has been observed to be beneficial for such networks. By the same argument, our result implies that width ($d+1$) fully connected networks are universal approximators, which is the minimum width needed .

Why does universal approximation matter?

As shown in Section 2, a width $d$ fully connected network can never approximate a compact decision boundary even if we allow infinite depth. However, in high dimensional space, it is very hard to visualize and check the obtained decision boundary. The universal approximation theorem then provides a sanity check, and ensures that, in principle, we are able to capture any desired decision boundary.

Training efficiency.

The universal approximation theorem only guarantees the possibility of approximating any desired function, but it does not guarantee that we will actually find it in practice by running SGD or any other optimization algorithm. Understanding the efficiency of training may require a better understanding of the optimization landscape, a topic of recent attention .

Here, we try to provide a slightly different angle. By our theory, ResNet with one-neuron hidden layers is already a universal approximator. In other words, a ResNet with multiple units per layer is in some sense an over-parametrization of the model, and over-parametrization has been observed to benefit optimization . This might be one reason why training a very deep ResNet is “easier” than training a fully connected network. A more rigorous analysis is an interesting direction for future work.

Generalization.

Since a universal approximator is able to fit any function, one might expect it to overfit very easily. Yet, it is commonly observed that deep networks generalize surprisingly well on the test set. The explanation of this phenomenon is orthogonal to our paper, however, knowing the universal approximation capability is an important building block of such a theory. Moreover, the above-mentioned “over-parametrization” implied by our results may play a role too.

To conclude, we have shown a universal approximation theorem for ResNet with one-neuron hidden layers. This theoretically distinguishes them from fully connected networks. To some extent, our construction also theoretically motivates the current practice of going deeper and deeper in the ResNet architecture.

References

Appendix A Notations and preliminary

In this section, we set up the notations and prepare some tools towards the universal approximation theorem. We first define the class of piecewise constant functions with compact support and finite many discontinuities.

$h=0$ outside $I=[a^{1}_{0},a^{1}_{M_{1}}]\times[a^{2}_{0},a^{2}_{M_{2}}]\times\cdots\times[a^{d}_{0},a^{d}_{M_{d}}]$.

$h$ is constant on each small cube $[a^{1}_{i_{1}},a^{1}_{i_{1}+1})\times[a^{2}_{i_{2}},a^{2}_{i_{2}+1})\times\cdots\times[a^{d}_{i_{d}},a^{d}_{i_{d}+1})$.

Theorem A.2 is a well known result directly derived from the definition of Lebesgue measure. As a result, it is sufficient to prove that ResNet can approximate any piecewise constant function arbitrarily well, which is the main objective of the following proof. We start by showing some basic operations allowed by ResNet with one unit per hidden layer.

The following operations are realizable by a single basic residual block of ResNet with one neuron:

where $R$ represents the input layer in the basic residual block and $R^{+}$ the output layer.

It is easy to see that (c) implies (a) and (b). We now prove (c). Indeed, the following coefficient do the job: given $\alpha,\beta\in R$,

These basic operations are extensively used in the following construction. Intuitively, operation (a) allows us to shift the function; operation (b) allows us to cut off the level set $\{R\geq c\}$ or $\{R\leq c\}$ and operation (c) is more complex, which can be used to adjust the slope.

Appendix B Warm Up: One Dimension case

We start with the one dimension case. As we mentioned, it is sufficient to approximate piecewise constant functions. Given a piecewise constant function $h$, there is a subdivision $-\infty<a_{0}<a_{1}<\cdots<a_{M}<+\infty$ such that

where $h_{k}$ is the constant value on the $k$-th subdivision $I_{k}=[a_{k-1},a_{k})$. We are going to approximate $h$ using trapezoid function.

Given a piecewise constant function $h$, for any $\delta>0$ satisfying $2\delta<\min_{k=1,\cdots,M}\{a_{k}-a_{k-1}\}$, there exists a ResNet $R$ such that

$R(x)=0$ for $x\in(-\infty,a_{0})$ and $x\in[a_{M},+\infty)$.

$R(x)=h_{k}$ for $x\in I_{k}^{\delta}=[a_{k-1}+\delta,a_{k}-\delta]$, for $k=1,\cdots,M$.

$R$ is bounded with $-\|h\|_{\infty}\leq R\leq\|h\|_{\infty}$.

We first construct the increasing trapezoid function $R_{M}^{*}$, as shown in Figure 9. It is a trapezoid function on each $I_{k}$ with “increasing” value.

We construct the increasing trapezoid function by induction on the subdivisions. For any $m\in[0,M]$, we construct a ResNet $R_{m}$ such that

$R_{m}$ is a trapezoid function on each $I_{k}$, for any $k=1,\cdots,m$.

$R_{m}=(k+1)\|h\|_{\infty}\,\,$ on $\,\,I_{k}^{\delta}=[a_{k-1}+\delta,a_{k}-\delta]$ for any $k=1,\cdots,m$.

$R_{m}$ is bounded on $(-\infty,a_{m}]$ by $0\leq R_{m}\leq(m+1)\|h\|_{\infty}$.

$R_{m}(x)=-\frac{(m+1)\|h\|_{\infty}}{\delta}(x-a_{m})$ if $x\in[a_{m},+\infty)$.

When $m=0$, we start with the identity function and sequentially build

$R^{+}=\max\{x,a_{0}\}=x+[a_{0}-x]_{+}$. (Cut off $x\leq a_{0}$)

$R_{0}=R^{++}-\frac{(\|h\|_{\infty}+\delta)}{\delta}[R^{++}]_{+}$.

We provide a geometric interpretation in Figure 10 and it is easy to see that C1-C5 holds.

Now we proceed by induction. Assume that $R_{m}$ is constructed, we will stack more modules of one-neuron residual blocks on top of $R_{m}$ to build $R_{m+1}$. More precisely, we use $R_{m}$ as input and sequentially perform

$R_{m}^{+}=R_{m}+\left(2+\frac{1}{m+1}\right)[-R_{m}]_{+}$.

$R_{m}^{++}=R_{m}^{+}-2\left[R_{m}^{+}-{(m+2)\|h\|_{\infty}}\frac{a_{m+1}-a_{m}}{2\delta}\right]_{+}$.

$R_{m+1}=\min\{R_{m}^{++},(m+2)\|h\|_{\infty}\}$.

A geometric interpretation of the construction is shown in Figure 11.

The first operation flips the linear part on $[a_{m},+\infty)$ by adjusting the slope. By induction, $R_{m}$ is positive on $(-\infty,a_{m}]$ and it is a negative linear function on $[a_{m},+\infty)$. Thus,

The second operation folds the linear function in the middle of $[a_{m},a_{m+1}]$. We show that the ReLU function is active if and only if $x\geq\frac{a_{m}+a_{m+1}}{2}$.

When $x<a_{m}$, $R_{m}^{+}=R_{m}$, then by C4

Thus the $[\,\,\,\,]_{+}$ in the update (b) of $R^{++}$ is not active on $x<a_{m}$, meaning $R_{m}^{++}(x)=R_{m}^{+}(x)=R_{m}(x)$ when $x<a_{m}$.

When $x\geq a_{m}$, $R_{m}^{+}$ is a linear function with positive slope, which is increasing. Therefore, the $[\,\,\,\,]_{+}$ in the update (b) is active only when $x\geq\frac{a_{m}+a_{m+1}}{2}$.

Finally, we cut off the peak of $R_{m}^{++}$ at the appropriate level $(m+2)\|h\|_{\infty}$ which yields $R_{m+1}$. We deduce the following expression of $R_{m+1}$:

It is then easy to check conditions C1-C5 holds, which enrolls the induction.

Before moving on, we remark that $R_{M}$ goes to $-\infty$ as $x\to\infty$. This negative “tail” is easily removed by performing a cut-off operation via the max operator:

which sets all the negative values to zero. This gives us the desired increasing trapezoid function $R_{M}^{*}$. One of the main properties of the increasing trapezoid function is that $R_{M}^{*}$ takes different value on different $I_{k}^{\delta}$. This allows us to adjust the function value of different level sets separately. More concretely, we define level sets $L_{k}$ by

It is easy to see that $I_{k}^{\delta}\subset L_{k}$ for any $k\geq 1$. The main idea is to sequentially adjust the function value on different level sets $L_{k}$. We start adjusting the top level set $L_{M}$ by performing

The ReLU activation $[R_{M}^{*}-M\|h\|_{\infty}]_{+}$ is active if and only if $x\in L_{M}$, which means the function values on other level sets are unchanged. Moreover, when $x\in I_{M}^{\delta}$, $R_{M}^{*}=(M+1)\|h\|_{\infty}$ which immediately implies $R_{M-1}^{*}(x)=h_{M}$. As a result, we have

Then we adjust the next level set, and so on.

More formally, for any $k=M,\cdots,1$, we sequentially construct

The $k$-th subdivision $I_{k}^{\delta}$ is set to value $h_{k}$ by moving from $R_{k}^{*}$ to $R_{k-1}^{*}$. We show by induction that $R_{k}^{*}$ satisfies

$R_{k}^{*}=0$ on $(-\infty,a_{0}]$ and $[a_{M},+\infty)$.

$R_{k}^{*}=h_{j}\,\,$ on $\,\,I_{j}^{\delta}$ for any $j=M,\cdots,k+1$.

$R_{k}^{*}=(j+1)\|h\|_{\infty}\,\,$ on $\,\,I_{j}^{\delta}$ for any $j=k,\cdots,1$.

$R_{k}^{*}$ is bounded with $-\|h\|_{\infty}\leq R_{k}^{*}\leq(k+1)\|h\|_{\infty}$.

It is clear that $R_{M}^{*}$ satisfies these properties. Assume that they are valid for $R_{k}^{*}$, then from (5),

In particular, remarking that $0\leq k\|h\|_{\infty}$ and $h_{j}\leq\|h\|_{\infty}\leq k\|h\|_{\infty}$ for any $j=M,\cdots k+1$. We have

This implies $R_{k-1}^{*}$ satisfies (a) and (c). To show (b), it remains to show $R_{k-1}^{*}=h_{k}$ on $I_{k}^{\delta}$, which is a direct consequence of (5). Finally, (d) holds by remarking that

This completes the induction. Therefore the last function $R_{0}^{*}$ is the desired approximation of $h$. More precisely, we have shown that

$R_{0}^{*}=0$ on $(-\infty,a_{0}]$ and $[a_{M},+\infty)$.

$R_{0}^{*}=h_{k}\,\,$ on $\,\,I_{k}^{\delta}=[a_{k-1}+\delta,a_{k}-\delta]$ for any $k=1,\cdots,M$.

$R_{0}^{*}$ is bounded with $-\|h\|_{\infty}\leq R_{0}^{*}\leq\|h\|_{\infty}$.

which can be made arbitrarily small by choosing an appropriate $\delta$. This completes the proof. ∎

The only property of the increasing trapezoid function that we have used in the proof is the property of separate level sets. The increasing function value is an artifact that facilitates the sequential construction.

However, the concept of monotonicity does not generalize in high dimensions. Instead, we are going to introduce a notion called grid indicator function.

In $d$ dimension space, a hypercube is the Cartesian product of $d$ bounded intervals, i.e.

For small enough $\delta$, we denote $I^{\delta}$ as the $\delta$-interior of $I$, namely

$g(x)=0$ if $x\notin\cup_{k=1}^{M}I_{k}$.

$g(x)=g_{k}$ if $x\in I_{k}^{\delta}$, for any $k=1,..M$.

In other words, $g$ can be viewed as an approximation of the indicator function, which in addition takes different function value on different hypercubes. For instance, the increasing trapezoid function is a grid indicator function when $d=1$.

Appendix C Extension to high dimension

We extend our proof to high dimensions by following the same path as our one dimensional construction. We first construct a high dimensional grid indicator function and then adjust the function value on each grid cell one after another. It is worth remarking that this last step of function adjustment is performed by sliding through all the grid cells and adjusting the function value sequentially, which can be done regardless of the dimension. Therefore, the main effort is to build the high dimensional grid indicator function, which enjoys the separate level set property.

where $M_{1:d}=\prod_{i=1}^{d}M_{i}$ denotes the total number of hypercubes and each $I_{k}$ is a $d$-dimensional hypercube of the form

for some $i_{1}\in[1,M_{1}]$, $i_{2}\in[1,M_{2}]$, $\cdots$, $i_{d}\in[1,M_{d}]$. Moreover, we denote

$R(x)=h_{k}$ for $x\in I_{k}^{\delta}$, which is the $\delta$-interior of the $k$-th grid cell $I_{k}$.

$R$ is bounded with $-\|h\|_{\infty}\leq R\leq\|h\|_{\infty}$.

We are going to perform an induction on the dimension $d$. The case $d=1$ is true by the analysis in Section B. Now assume that it is true for $d-1$, which means we are able to approximate any $d-1$ dimensional piecewise constant function. The key idea is to view a $d$-dimensional hypercube as the product of a one dimensional interval and a $(d-1)$-dimensional hypercube. More precisely, we denote

Therefore each $I_{k}$ can be represented by $J_{i}\times K_{l}$, for some $i\in[1,M_{1}]$ and $l\in[1:M_{2:d}]$. We are going to construct a $d-1$ dimensional grid indicator function and a one dimensional network grid indicator function independently.

By induction, there exists a $d-1$ dimensional ResNet $R_{d-1}$ such that

$R_{d-1}(x_{2:d})=0$ if $x_{2:d}\notin K=\cup K_{l}$

$R_{d-1}(x_{2:d})=(l+1)\|h\|_{\infty}$ for $x_{2:d}\in K_{l}^{\delta}$.

$R_{d-1}$ is bounded with $-(M_{2:d}+1)\|h\|_{\infty}\leq R_{d-1}\leq(M_{2:d}+1)\|h\|_{\infty}$.

We have abused the notation to use $x_{2:d}$ to denote a $d-1$-dimensional vector. Even though $R_{d-1}$ is $d-1$ dimensional, we can extend it to a $d$ dimensional network by setting the weight of the first coordinate to zero, see Figure 13.

Next, we construct an increasing trapezoid function $R_{1}$ on the first coordinate $x_{1}$ such that

$R_{1}$ is a trapezoid function on each $J_{i}$, for $i=1\cdots M_{1}$.

$R_{1}(x_{1})=\left(M_{2;d}+1+\frac{i}{M_{1}+1}\right)\|h\|_{\infty}$ for $x_{1}\in J_{i}^{\delta}$.

$R_{1}$ is bounded with $0\leq R_{1}\leq(M_{2:d}+2)\|h\|_{\infty}$.

We concatenate $R_{1}$ with $R_{d-1}$ in a dimensional network. This is possible since $R_{1}$ only operates on the first coordinate while $R_{d-1}$ operates on the last $d-1$ coordinates, see Figure 14.

Thanks to the identity mapping, we can pass the information forward even though the weights are set to zero. Thus, in the last layer of the above network, we get $R_{1}(x_{1})$ in the first neuron and $R_{d-1}(x_{2:d})$ in one of the last $d-1$ neurons. Now we are going to couple these two neurons by summing them up. For technical reasons, we need to ensure the positiveness of $R_{d-1}$, which can be easily obtained by performing a max operator

Then we sum up $R_{1}$ and $R_{d-1}^{+}$ by performing

We show that a separation level set property holds respect to the $d$-dimensional grid cell $I=\cup_{k=1}^{M_{1:d}}I_{k}$. More precisely,

When $x\notin I$, one of the function $R_{1}$, $R_{d-1}^{+}$ vanishes, thus

When $x\in I_{k}^{\delta}=J_{i}^{\delta}\times K_{l}^{\delta}$, then

As a result, by performing a “cut and shift” operation:

$R_{1}^{*}=\left(l+\frac{i}{M_{1}+1}\right)\|h\|_{\infty}$ on $J_{i}^{\delta}\times K_{l}^{\delta}$.

$R_{1}^{*}$ is bounded with $0\leq R_{1}^{*}\leq(M_{2:d}+1)\|h\|_{\infty}$.

In particular, different pairs $(i,l)$ gives different value of $R_{1}^{*}$. Therefore $R_{1}^{*}$ is a $d$-dimensional grid indicator function of the desired hypercube $I$. Then it suffices to perform the function adjustment procedure on each individual grid cell to obtain the final approximation, as in the one dimensional case. This completes the proof. ∎

Appendix D Experimental settings

In this section, we provide more details of the experimental setting in the unit ball classification problem.

The training/testing samples are $2$-dimensional vectors. We say $x$ is a positive sample if $\|x\|_{2}\leq 1$ and $x$ is a negative sample sample if $2\leq\|x\|_{2}\leq 3$. The training set consists of $10^{2}$ positive samples and $2*10^{2}$ negative samples, being randomly generated.

About the training algorithm.

We train the network with logistic loss using SGD with momentum. We run the algorithm for 10 epochs and we observe that after 5-8 epochs the loss on the training set saturates.

Visualizing the decision boundaries.

After training, we learn a function $f_{\mathcal{N}}$ based on the neural network. To visualize the decision boundary, we randomly sampled $2*10^{3}$ points in the ball $B(0,5)$ and use red point to represent positive predictions $\{f_{\mathcal{N}}>0\}$ and blue points to represent negative predictions $\{f_{\mathcal{N}}\leq 0\}$.

Appendix E Proof of Proposition 2.1

We recall Proposition 2.1 in the main paper and prove it based on the result developed in .

In other words, the level set of a “narrow” fully connected network is either unbounded or has measure null.

When $d=1$, one hidden unit fully connected network $f_{\mathcal{N}}$ is always monotone. Thus the statement holds.

When $d\geq 2$. We apply Lemma 1 of : if a fully connected network $\mathcal{N}$ with ReLU activation has at most $d$ neurons per hidden layer, then

We are going to stack one more layer on top of $\mathcal{N}$ to build a new network $\mathcal{N}^{+}$ which thresholds its negative part.

More precisely, we take the exact same coefficients as $\mathcal{N}$ and duplicate the last linear transformation into two ReLU activation functions such that

Since $\mathcal{N}^{+}$ is also a fully connected network with at most $d$ neurons per hidden layer, the lemma 1 of also applies to $\mathcal{N}^{+}$. Therefore,

Again the case when it is zero directly implies $\lambda(P)=0$. Moreover, $f_{\mathcal{N}^{+}}$ is upper bounded by one, which yields