Minimum Width for Universal Approximation

Introduction

The study of the expressive power of neural networks investigates what class of functions neural networks can/cannot represent or approximate. Classical results in this field are mostly focused on shallow neural networks. An example of such results is the universal approximation theorem (Cybenko, 1989; Hornik et al., 1989; Pinkus, 1999), which shows that a neural network with fixed depth and arbitrary width can approximate any continuous function on a compact set, up to arbitrary accuracy, if the activation function is continuous and nonpolynomial. Another line of research studies the memory capacity of neural networks (Baum, 1988; Huang and Babri, 1998; Huang, 2003), trying to characterize the maximum number of data points that a given neural network can memorize.

After the advent of deep learning, researchers started to investigate the benefit of depth in the expressive power of neural networks, in an attempt to understand the success of deep neural networks. This has led to interesting results showing the existence of functions that require the network to be extremely wide for shallow networks to approximate, while being easily approximated by deep and narrow networks (Telgarsky, 2016; Eldan and Shamir, 2016; Lin et al., 2017; Poggio et al., 2017). A similar trade-off between depth and width in expressive power is also observed in the study of the memory capacity of neural networks (Yun et al., 2019; Vershynin, 2020).

General activations.

Limitations of prior arts.

Note that none of the existing works succeeds in closing the gap between the upper bound (at least $d_{x}+d_{y}$) and the lower bound (at most $d_{x}+1$). This gap is significant especially for applications with high-dimensional codomains (i.e., large $d_{y}$) such as image generation (Kingma and Welling, 2013; Goodfellow et al., 2014), language modeling (Devlin et al., 2019; Liu et al., 2019), and molecule generation (Gómez-Bombarelli et al., 2018; Jin et al., 2018). In the prior arts, the main bottleneck for proving an upper bound below $d_{x}+d_{y}$ is that they maintain all $d_{x}$ neurons to store the input and all $d_{y}$ neurons to construct the function output; this means every layer already requires at least $d_{x}+d_{y}$ neurons. In addition, the proof techniques for the lower bounds only consider the input dimension $d_{x}$ regardless of the output dimension $d_{y}$.

2 Summary of results

We mainly focus on characterizing the minimum width of ReLU networks for universal approximation. Nevertheless, our results are not restricted to ReLU networks; they can be generalized to networks with general activation functions. Our contributions can be summarized as follows.

Our proof techniques for tight upper bounds are not restricted to ReLU networks. In Theorem 4, we extend our results to general activation functions covered in Kidger and Lyons (2020).

3 Organization

We first define necessary notation in Section 2. In Section 3, we formally state our main results and discuss their implications. In Section 4, we present our “coding scheme” for proving upper bounds on the minimum width in Theorems 1, 3 and 4. In Section 5, we prove the lower bound in Theorem 2 by explicitly constructing a counterexample. Finally, we conclude the paper in Section 6. We note that all formal proofs of Theorems 1–4 are presented in Appendix.

Problem setup and notation

Throughout this paper, we consider fully-connected neural networks that can be described as an alternating composition of affine transformations and activation functions. Formally, we consider the following setup: Given a set of activation functions $\Sigma$, an $L$-layer neural network $f$ of input dimension $d_{x}$, output dimension $d_{y}$, and hidden layer dimensions $d_{1},\dots,d_{L-1}$For simplicity of notation, we let $d_{x}=d_{0}$ and $d_{y}=d_{L}$. is represented as

where $\rho_{i}\in\Sigma$. While we mostly consider the cases where $\Sigma$ is a singleton (e.g., $\Sigma=\{\textsc{ReLU}\}$), we also consider the case where $\Sigma$ contains both ReLU and Step activation functions as in Theorem 3. We denote a neural network with $\Sigma=\{\rho\}$ by a “$\rho$ network” and a neural network with $\Sigma=\{\rho_{1},\rho_{2}\}$ by a “$\rho_{1}$+$\rho_{2}$ network.” We define the width $w$ of $f$ as the maximum over $d_{1},\dots,d_{L-1}$.

For describing the universal approximation of neural networks, we say $\rho$ networks (or $\rho_{1}$+$\rho_{2}$ networks) of width $w$ are dense in $C(\mathcal{X},\mathcal{Y})$ if for any $f^{*}\in C(\mathcal{X},\mathcal{Y})$ and $\varepsilon>0$, there exists a $\rho$ network (or a $\rho_{1}$+$\rho_{2}$ network) $f$ of width $w$ such that $\|f^{*}-f\|_{\infty}\leq\varepsilon$. Likewise, we say $\rho$ networks (or $\rho_{1}$+$\rho_{2}$ networks) are dense in $L^{p}(\mathcal{X},\mathcal{Y})$ if for any $f^{*}\in L^{p}(\mathcal{X},\mathcal{Y})$ and $\varepsilon>0$, there exists a $\rho$ network (or a $\rho_{1}$+$\rho_{2}$ network) $f$ such that $\|f^{*}-f\|_{p}\leq\varepsilon$.

Minimum width for universal approximation

Notably, using our new proof technique, we overcome the limitation of existing upper bounds that require width at least $d_{x}+d_{y}$. Our construction first encodes the $d_{x}$ dimensional input vectors into one-dimensional codewords, and maps the codewords to target codewords using memorization, and decodes the target codewords to $d_{y}$ dimensional output vectors. Since we construct the map from input to target using scalar codewords, we bypass the need to use $d_{x}+d_{y}$ hidden nodes. More details are found in Section 4. Proofs of the lower bounds are deferred to Appendices B.1, B.3.

Uniform approximation with ReLU.

Theorem 2 translates to $w_{\min}=3$, and the upper bound $w_{\min}\leq 3=d_{x}+d_{y}$ is given by Hanin and Sellke (2017). The key is to prove a lower bound $w_{\min}\geq 3$, i.e., width $2$ is not sufficient. Recall from Section 1.1 that all the known lower bounds are limited to showing that width $d_{x}$ is insufficient for universal approximation. A closer look at their proof techniques reveals that they heavily rely on the fact that the hidden layers have the same dimensions as the input space. As long as the width $w>d_{x}$, their arguments break because such a network maps the input space into a higher-dimensional space.

Although only for $d_{x}=1$ and $d_{y}=2$, we overcome this limitation of the prior arts and show that width $w=2>d_{x}$ is insufficient for universal approximation, by providing a counterexample. We use a novel topological argument which comes from a careful observation on the image created by ReLU operations. In particular, we utilize the property of ReLU that it projects all negative inputs to zero, without modifying any positive inputs. We believe that our proof will be of interest to readers and inspire follow-up works. Please see Section 5 for more details.

Uniform approximation with ReLU+Step.

Theorem 2 and Theorem 3 indicate that the minimum width for universal approximation is indeed dependent on the choice of activation functions. This is also in contrast to the classical results where ReLU networks of depth $2$ are universal approximators (Leshno et al., 1993), i.e., the minimum depths for universal approximation are identical for both ReLU networks and ReLU+Step networks.

Theorem 3 comes from a similar proof technique as Theorem 1. Due to its discontinuous nature, the Step activation can be used in our encoder to quantize the input without introducing uniform norm errors. Lower bounds on $w_{\min}$ can be proved in a similar way as Theorem 1 (see Appendices B.1, B.2).

General activations.

Our proof technique for upper bounds in Theorems 1 and 3 can be easily extended to networks using general activations. Indeed, we prove the following theorem, which shows that adding a width of $1$ is enough to cover the networks with general activations.

Please notice that unlike other theorems, Theorem 4 only proves an upper bound $w_{\min}\leq\max\{d_{x}+2,d_{y}+1\}$. We note that Theorem 4 significantly improves over the previous upper bound of width $d_{x}+d_{y}+1$ by (Kidger and Lyons, 2020, Remark 4.10).

Tight upper bound on minimum width for universal approximation

In this section, we present the main idea for constructing networks achieving the minimum width for universal approximation, and then sketch the proofs of upper bounds in Theorems 1, 3, and 4.

We now illustrate the main idea underlying the construction of neural networks that achieve the minimum width. To this end, we consider an approximation of a target continuous function $f^{*}\in C(^{d_{x}},^{d_{y}})$; however, our main idea can be easily generalized to other domain, codomain, and $L^{p}$ functions. Our construction can be viewed as a coding scheme in essence, consisting of three parts: encoder, memorizer, and decoder. First, the encoder encodes an input vector to a one-dimensional codeword. Then, the memorizer maps the codeword to a one-dimensional target codeword that is encoded with respect to the corresponding target $f^{*}(x)$. Finally, the decoder maps the target codeword to a target vector which is sufficiently close to $f^{*}(x)$. Note that one can view the encoder, memorizer, and decoder as functions mapping from $d_{x}$-dimension to $1$-dimension, then to $1$-dimension, and finally to $d_{y}$-dimension.

The spirit of the coding scheme is that the three functions can be constructed using the idea of the prior results such as (Hanin and Sellke, 2017). Recall that Hanin and Sellke (2017) approximate any continuous function mapping $n$-dimensional inputs to $m$-dimensional outputs using ReLU networks of width $n+m$. Under this intuition, we construct the encoder, the memorizer, and the decoder by ReLU+Step networks (or ReLU networks) of width $d_{x}+1,2,d_{y}$, respectively; these constructions result in the tight upper bound $\max\{d_{x}+1,d_{y}\}$. Here, the decoder requires width $d_{y}$ instead of $d_{y}+1$, as we only construct the first $d_{y}-1$ coordinates of the output, and recover the last output coordinate from a linear combination of the target codeword and the first $d_{y}-1$ coordinates.

Next, we describe the operation of each part. We explain their neural network constructions in subsequent subsections.

In other words, given any $x\in[0,1)$, $q_{n}(x)$ preserves the first $n$ bits in the binary representation of $x$ and discards the rest; $x=1$ is mapped to $1-2^{-n}$. Note that the error from the quantization is always less than or equal to $2^{-n}$.

In other words, $\mathtt{encode}_{K}(x)$ quantizes each coordinate of $x$ by a $K$-bit binary representation and concatenates the quantized coordinates into a single scalar value having a $(d_{x}K)$-bit binary representation. Note that if one “decodes” a codeword $\mathtt{encode}_{K}(x)$ back to a vector $\hat{x}$ asHere, $\mathtt{encode}_{K}^{-1}$ denotes the preimage of $\mathtt{encode}_{K}$ and $\mathcal{C}_{K}^{d_{x}}$ is the Cartesian product of $d_{x}$ copies of $\mathcal{C}_{K}$.

then $\|x-\hat{x}\|_{\infty}\leq 2^{-K}$. Namely, the “information loss” incurred by the encoding can be made arbitrarily small by choosing large $K$.

Memorizer.

where $q_{K}$ is applied coordinate-wise for a vector. We note that $\mathtt{memorizer}_{K,M}$ is well-defined as each $\mathtt{encode}_{K}(x)\in\mathcal{C}_{d_{x}K}$ corresponds to a unique $q_{K}(x)\in\mathcal{C}_{K}^{d_{x}}$. Here, one can observe that the target of the memorizer contains the information of the target value since \mathtt{encode}_{M}\big{(}f^{*}\circ q_{K}(x)\big{)} contains information of $f^{*}$ at a quantized version of $x$, and the information loss due to quantization can be made arbitrarily small by choosing large enough $K$ and $M$.

Decoder.

The decoder decodes each codeword generated by the memorizer by the function $\mathtt{decode}_{M}:\mathcal{C}_{d_{y}M}\rightarrow\mathcal{C}_{M}^{d_{y}}$ defined as

Combining $\mathtt{encode}$, $\mathtt{memorize}$, and $\mathtt{decode}$ completes our coding scheme for approximating $f^{*}$. One can observe that our coding scheme is equivalent to $q_{M}\circ f^{*}\circ q_{K}$ which can approximate the target function $f^{*}$ within any $\varepsilon>0$ error, i.e.,

In the remainder of this section, we discuss how each part of the coding scheme can be implemented with a neural network using ReLU+Step activations (Section 4.2), ReLU activation (Section 4.3), and other general activations (Section 4.4).

2 Tight upper bound on minimum width of ReLU+Step networks (Theorem 3)

First, the encoder consists of quantization functions $q_{K}$ and a linear transformation. However, as $q_{K}$ is discontinuous and cannot be uniformly approximated by any continuous function, we utilize the discontinuous Step activation to exactly construct the encoder via a ReLU+Step network of width $d_{x}+1$. On the other hand, the memorizer and the decoder maps a finite number of scalar values (i.e., $\mathcal{C}_{d_{x}K}$ and $\mathcal{C}_{d_{y}M}$, respectively) to their target values/vectors. Such maps can be easily implemented by continuous functions (e.g., via linear interpolation), and hence, can be exactly constructed by ReLU networks of width $2$ and $d_{y}$, respectively, as discussed in Section 4.1. Note that Step is used only for constructing the encoder.

In summary, all parts of our coding scheme can be exactly constructed by ReLU+Step networks of width $d_{x}+1$, $2$, and $d_{y}$. Thus, the overall ReLU+Step network has width $\max\{d_{x}+1,d_{y}\}$. Furthermore, it can approximate the target continuous function $f^{*}$ within arbitrary uniform error by choosing sufficiently large $K$ and $M$. We present the formal proof in Appendix A.1.

3 Tight upper bound on minimum width of ReLU networks (Theorem 1)

Since the memorizer and the decoder can be exactly constructed by ReLU networks, we only discuss the encoder here. As we discussed in the last section, the encoder cannot be uniformly approximated by continuous functions (i.e., ReLU networks). Nevertheless, it can be implemented by continuous functions except for a subset of the domain around the discontinuities, and this subset can be made arbitrarily small in terms of the Lebesgue measure. That is, we construct the encoder using a ReLU network of width $d_{x}+1$ for $^{d_{x}}$ except for a small subset, which enables us to approximate the encoder in the $L^{p}$-norm. Combining with the memorizer and the decoder, we obtain a ReLU network of width $\max\{d_{x}+1,d_{y}\}$ that approximates the target function $f^{*}$ in the $L^{p}$-norm. We present the formal proof in Appendix A.2.

4 Tightening upper bound on minimum width for general activations (Theorem 4)

Tight lower bound on minimum width for universal approximation

If $x\in\mathcal{S}$, then $x^{\prime}=x$.

If $x^{\prime}\neq x$, then $x^{\prime}\in\mathcal{T}^{\prime}$.

Lemma 5 follows from the fact that output of ReLU is identity to nonnegative coordinates, and is zero to negative coordinates. In particular, $a_{1},b_{1}$ and $a_{2},b_{2}$ in Lemma 5 correspond to the axes of the “modified” coordinate system before applying $\sigma$. Under the same property of ReLU, Lemma 6 states that if a point $x$ is surrounded by a set $\mathcal{T}$, after applying $\phi^{-1}\circ\sigma\circ\phi$, either the point stays at the same position and surrounded by the image of $\mathcal{T}$ or intersects with the image of $\mathcal{T}$. Based on these observations, we are now ready to introduce our counterexample.

2 Counterexample

Conclusion

The universal approximation property of width-bounded networks is one of the fundamental problems in the expressive power theory of deep learning. Prior arts attempt to characterize the minimum width sufficient for universal approximation; however, they only provide upper and lower bounds with large gaps. In this work, we provide the first exact characterization of the minimum width of ReLU networks and ReLU+Step networks. In addition, we observe interesting dependence of the minimum width on the target function classes and activation functions, in contrast to the minimum depth of classical results. We believe that our results and analyses would contribute to a better understanding of the performance of modern deep and narrow network architectures.

Acknowledgements

CY acknowledges financial supports from NSF CAREER Grant Number 1846088 and Korea Foundation for Advanced Studies.

References

Appendix A Proofs of upper bounds

In this section, we first provide proofs of upper bounds in Theorems 1, 3, 4. Throughout this section, we denote the coordinate-wise ReLU by $\sigma$ and we denote the $i$-th coordinate of an output of a function $f(x)$ by $(f(x))_{i}$.

Our construction is based on the three-part coding scheme introduced in Section 4.1. First, consider constructing a ReLU+Step network for the encoder. From the definition of $q_{K}$, one can observe that the mapping is discontinuous and piece-wise constant. Hence, the exact construction (or even the uniform approximation) of the encoder requires the use of discontinuous activation functions such as Step (recall its definition $x\mapsto\mathbf{1}[x\geq 0]$). We introduce the following lemma for the exact construction of $q_{K}$. The proof of Lemma 8 is presented in Appendix A.4.

For constructing the encoder via a ReLU+Step network of width $d_{x}+1$, we apply $q_{K}$ to each input coordinate, by utilizing the extra width $1$ and using Lemma 8. Once we apply $q_{K}$ for all input coordinates, we apply the linear transformation $\sum\nolimits_{i=1}^{d_{x}}q_{K}(x_{i})\times 2^{-(i-1)K}$ to obtain the output of the encoder.

On the other hand, the memorizer only maps a finite number of scalar inputs to the corresponding scalar targets, which can be easily implemented by piece-wise linear continuous functions. We show that the memorizer can be exactly constructed by a ReLU network of width 2 using the following lemma. The proof of Lemma 9 is presented in Appendix A.5.

Likewise, the decoder maps a finite number of scalar inputs in $\mathcal{C}_{d_{y}M}$ to corresponding target vectors in $\mathcal{C}_{M}^{d_{y}}$. Here, each coordinate of a target vector corresponds to some consequent bits of the binary representation of the input. Under the similar idea used for our implementation of the memorizer, we show that the decoder can be exactly constructed by a ReLU network of width $d_{y}$ using the following lemma. The proof of Lemma 10 is presented in Appendix A.6.

A.2 Proof of tight upper bound in Theorem 1

Namely, if we construct a ReLU network $f$ such that $\|f^{\prime}-f\|_{p}\leq\frac{\varepsilon}{2}$, then it completes the proof. Throughout this proof, we assume that the support of $f^{\prime}$ is a subset of $^{d_{x}}$ and its codomain to be $^{d_{y}}$ which can be easily generalized to arbitrary compact support and arbitrary codomain, respectively.

We approximate $f^{\prime}$ by a ReLU network using the three-part coding scheme introduced in Section 4.1. We will refer to our implementations of the three parts as $\mathtt{encode}_{K}^{\dagger}(x)$, $\mathtt{memorize}_{K,M}^{\dagger}$, and $\mathtt{decode}_{M}^{\dagger}$. That is, we will approximate $f^{\prime}$ by a ReLU network

However, unlike our construction of ReLU+Step networks in Section A.1, Step is not available, i.e., uniform approximation of $q_{K}$ is impossible. Nevertheless, one can approximate $q_{K}$ with some continuous piece-wise linear function by approximating regions around discontinuities with some linear functions. Under this idea, we introduce the following lemma. The proof of Lemma 11 is presented in Appendix A.7.

By Lemma 11, there exist a ReLU network $\mathtt{encode}_{K}^{\dagger}$ of width $d_{x}+1$ and $\mathcal{D}_{\gamma}\subset^{d_{x}}$ such that $\mu(\mathcal{D}_{\gamma})<\gamma$,

We approximate the encoder by $\mathtt{encode}_{K}^{\dagger}$. Here, we note that inputs from $\mathcal{D}_{\gamma}$ would be mapped to arbitrary values by $\mathtt{encode}_{K}^{\dagger}$. Nevertheless, it is not critical to the error $\|f^{\prime}-f\|_{p}$ as $\mu(\mathcal{D}_{\gamma})<\gamma$ can be made arbitrarily small by choosing a sufficiently small $\gamma$.

To achieve this, we design the memorizer for $c\in\mathcal{C}_{d_{x}K}$ using Lemma 9 and based on (4) as

We note that such a design incurs an undesired error that a subset of $\mathcal{E}_{K}:=[1-2^{-K},1]^{d_{x}}$ might be mapped to zero after applying $\mathtt{memorize}_{K,M}^{\dagger}$. Nevertheless, mapping $\mathcal{E}_{K}$ to zero is not critical to the error $\|f^{\prime}-f\|_{p}$ as $\mu(\mathcal{E}_{K})<2^{-d_{x}K}$ can be made arbitrarily small by choosing a sufficiently large $K$.

Finally, we bound the error $\|f^{\prime}-f\|_{p}$ utilizing the following inequality:

By choosing sufficiently large $K,M$ and sufficiently small $\gamma$, one can make the RHS smaller than $\varepsilon/2$ as $\sup_{x\in^{d_{x}}}\|f^{\prime}(x)\|_{p}<\infty$. This completes the proof of the tight upper bound in Theorem 1.

A.3 Proof of Theorem 4

Before describing our construction, we first introduce the following lemma.

We note that Proposition 4.9 by Kidger and Lyons (2020) only ensures $\|y_{2}(x)-f^{*}(x)\|_{\infty}\leq\varepsilon$; however, its proof provides $\|y_{1}(x)-x\|_{\infty}\leq\varepsilon$ as well.

The proof of Theorem 4 also utilizes our coding scheme; here, we approximate ReLU network constructions $\mathtt{encode}_{K}^{\dagger}$, $\mathtt{memorize}_{K,M}^{\dagger}$, and $\mathtt{decode}_{M}^{\dagger}$ in Appendix A.2 by $\rho$ networks. Using Lemma 12, for any $\varepsilon_{1}>0$, we approximate $\mathtt{encode}_{K}^{\dagger}$ by a $\rho$ network $\mathtt{encode}_{K}^{\ddagger}$ of width $d_{x}+2$ so that

and $\mathtt{memorize}_{K,M}^{\ddagger}(\mathcal{I}_{2})\subset[-\varepsilon_{2},1+\varepsilon_{2}]$. We note that $\mathtt{memorize}_{K,M}^{\ddagger}(\mathcal{I}_{2})\subset[-\varepsilon_{2},1+\varepsilon_{2}]$ is possible as there exists $\mathtt{memorize}_{K,M}^{\dagger}$ (i.e., a ReLU network) such that $\mathtt{memorize}_{K,M}^{\dagger}(\mathcal{I}_{2})\subset$ by Lemma 9.

For approximating the decoder, we introduce the following lemma. The proof of Lemma 13 is presented in Appendix A.8.

Namely, $f(\mathcal{I})\subset[-\varepsilon,1+\varepsilon]^{d_{y}}$.

and $\mathtt{decode}_{M}^{\ddagger}(\mathcal{I}_{3})\in[-\varepsilon_{3},1+\varepsilon_{3}]^{d_{y}}$.

We approximate $f^{\prime}$ by a $\rho$ network $f$ of width $\max\{d_{x}+2,d_{y}+1\}$ defined as

Here, for any $\eta>0$, by choosing sufficiently large $K,M$, sufficiently large $\mathcal{I}_{2},\mathcal{I}_{3}$, and sufficiently small $\varepsilon_{1},\varepsilon_{2},\varepsilon_{3}$ so that $\omega_{f^{\prime}}(2^{-K})+2^{-M}\leq\frac{\eta}{2}$ and \omega_{\mathtt{decode}_{M}^{\ddagger}}\big{(}\omega_{\mathtt{memorize}_{K,M}^{\ddagger}}(\varepsilon_{1})+\varepsilon_{2}\big{)}+\varepsilon_{3}\leq\frac{\eta}{2}, we have

where $\omega_{\mathtt{memorize}_{K,M}^{\ddagger}}$ and $\omega_{\mathtt{decode}_{M}^{\ddagger}}$ are defined on $\mathcal{I}_{2}$ and $\mathcal{I}_{3}$, respectively.

Finally, we bound the error $\|f^{\prime}-f\|_{p}$ utilizing the following inequality:

By choosing sufficiently small $\varepsilon_{1},\varepsilon_{2},\varepsilon_{3},\gamma$, sufficiently large $K,M$, and sufficiently large $\mathcal{I}_{2},\mathcal{I}_{3}$, one can make the RHS smaller than $\varepsilon/2$ due to (5) and the fact that $\sup_{x\in^{d_{x}}}\|f^{\prime}(x)\|_{p}<\infty$. This completes the proof of Theorem 4.

A.4 Proof of Lemma 8

This directly implies that $f(x)=q_{K}(x)$ for all $x\in$ and completes the proof of Lemma 8.

A.5 Proof of Lemma 9

Then, from Lemma 14, there exists a ReLU network $f$ of width 2 such that $f^{\dagger}(x)=f(x)$ for all $x\in\mathcal{X}$. Since $\mathcal{X}\subset[x^{(0)},x^{(N+1)}]=\mathcal{I}$ and f^{\dagger}(\mathcal{I})\subset\big{[}\min f^{*}(\mathcal{X}),\max f^{*}(\mathcal{X})\big{]}, this completes the proof of Lemma 9.

Suppose that $f^{*}$ is linear on intervals $[\min\mathcal{I},x_{1}),[x_{1},x_{2}),\dots,[x_{P-1},\max\mathcal{I}]$ and parametrized as

Then, the following construction of $f$ completes the proof of the mathematical induction:

where $K:=\min_{i}\min_{x\in\mathcal{I}}\{a_{i}\times x+b_{i}\}$. This completes the proof of Lemma 14. ∎

A.6 Proof of Lemma 10

Before describing our proof, we first introduce the following lemma. The proof of Lemma 15 is presented in Appendix A.9.

and $\mathcal{D}_{M,\delta}:=\bigcup_{i=1}^{2^{M}-1}(i\times 2^{-M}-\delta,i\times 2^{-M}).$ Furthermore, it holds that

A.7 Proof of Lemma 11

To begin with, we introduce the following Lemma. The proof of Lemma 16 is presented in Appendix A.10.

Note that we use $q_{K}(x)$ for denoting the coordinate-wise $q_{K}$ for a vector $x$.

Now, we define $\mathcal{D}_{\gamma}:=(^{d_{x}}\setminus[\alpha,1-\alpha]^{d_{x}})\cup\mathcal{D}_{K,\delta,d_{x}}\subset^{d_{x}}$. Then, from constructions of $h_{1}$ and $h_{2}$, we have

where we use the fact that $(1,\dots,1)\notin\mathcal{D}_{K,\delta,d_{x}}$ and $q_{K}((1,\dots,1))=(1-2^{-K},\dots,1-2^{-K})$.

Finally, we construct a ReLU network $f$ of width $d_{x}+1$ as

In addition, if we choose sufficiently small $\alpha$ and $\delta$ so that $\mu(\mathcal{D}_{\gamma})<\gamma$, then $f$ satisfies all conditions in Lemma 11. This completes the proof of Lemma 11.

A.8 Proof of Lemma 13

The proof of Lemma 13 is almost identical to that of Lemma 10. In particular, we approximate the ReLU network construction of iterative $d_{y}-1$ applications of $g$ (see Appendix A.6 for the definition of $g$) by a $\rho$ network of width $d_{y}+1$. To this end, we consider a $\rho$ network $h$ of width $3$ approximating $g$ on some interval $\mathcal{J}$ within $\alpha$ error using Lemma 12. Then, one can observe that iterative $d_{y}-1$ applications of $h$ (as in Appendix A.6) results in a $\rho$ network $f$ of width $d_{y}+1$. Here, passing through the identity function can be approximated using a $\rho$ network of width $1$, i.e., same width to ReLU networks (see Lemma 4.1 by Kidger and Lyons (2020) for details). Furthermore, since $h$ is uniformly continuous on $\mathcal{J}$, it holds that $\|f(c)-\mathtt{decode}_{M}(c)\|_{\infty}\leq\varepsilon$ for all $c\in\mathcal{C}_{d_{y}M}$ and $f(\mathcal{I})\subset[-\varepsilon,1+\varepsilon]^{d_{y}}$ by choosing sufficiently large $\mathcal{J}$ and sufficiently small $\alpha$ so that $\omega_{h}(\cdots\omega_{h}(\omega_{h}(\alpha)+\alpha)\cdots)+\alpha\leq\varepsilon$.We consider $\omega_{h}$ on $\mathcal{J}$. This completes the proof of Lemma 13.

A.9 Proof of Lemma 15

We first clip the input to be in $$using the following ReLU network of width$1$.

completes the proof. Note that as $(g(x))_{2}\leq x=(g(x))_{1}$ for all $x\in$, $f(x)\in[0,1-2^{-M}]\times$. Now, we describe how to construct $g_{2^{M}}$ by a ReLU network. One can observe that $(g_{1}(x))_{2}=0$ and

for all $x$, i.e., alternating applications of $\min\{\cdot,\cdot\}$ and $\max\{\cdot,\cdot\}$. Finally, we introduce the following definition and lemma.

We note that Proposition 2 by Hanin and Sellke (2017) itself only ensures $y_{2}=f^{*}(x)$; however, its proof provides $y_{1}=x$ as well.

From the definition of the max-min string, one can observe that $(g_{2^{M}}(x))_{2}$ is a max-min string. Hence, by Lemma 17, there exists a ReLU network $g$ of width $2$ such that $g(x)=g_{2^{M}}(x)=q_{M}(x)$ for all $x\in\mathcal{D}_{K,\delta}$. This completes the proof of Lemma 15.

A.10 Proof of Lemma 16

Appendix B Proofs of lower bounds

where $\pi_{\mathcal{H}}$ denotes the projection onto $\mathcal{H}$. As projection is contraction and the distance between any two points are at most $\sqrt{2}$, it holds that for any $\mathcal{H}$,

for $p<2$. This completes the proof of Lemma 18. ∎

B.2 Proof of tight lower bound in Theorem 3

Without loss of generality, we assume that $f$ has $d_{x}$ hidden neurons at each layer except for the output layer and all affine transformations in $f$ are invertible (see Section 5.1).

Our main idea is to utilize properties of level sets of width-$d_{x}$ ReLU+Step networks (Hanin and Sellke, 2017) defined as follows: Given a network $f$ of width $d_{x}$, we call a connected component of $f^{-1}(y)$ for some $y$ as a level set. Level sets of ReLU+Step networks have a property described by the following lemma. We note that the statement and the proof of Lemma 19 is motivated by Lemma 6 of (Hanin and Sellke, 2017).

Let $f$ be a Step+ReLU network of width $d_{x}$ containing at least one Step. Then, for any level set $\mathcal{S}$ of $f$, $\mathcal{S}$ is unbounded unless it is empty.

Now, we continue the proof of the tight lower bound in Theorem 3 based on Lemma 19. We note that our argument is also from the proof of the lower bound in Theorem 1 of (Hanin and Sellke, 2017).

Then, for $a=\frac{1}{4}$ and $b=0$, one can observe that $(f^{*})^{-1}(a)$ is a sphere of radius $\frac{1}{2}$ centered at $(f^{*})^{-1}(b)=\{(\frac{1}{2},\dots,\frac{1}{2})\}$. Namely, any path from $(f^{*})^{-1}(b)$ to infinity must intersect with $(f^{*})^{-1}(a)$. Now, suppose that a ReLU+Step network $f$ of width $d_{x}$ satisfies that $\|f^{*}-f\|_{\infty}\leq\frac{1}{16}$. Then, the level set of $f$ containing $(\frac{1}{2},\dots,\frac{1}{2})$ must be unbounded by Lemma 19, and hence, must intersect with $(f^{*})^{-1}(a)$. However, as $f^{*}\circ(f^{*})^{-1}(a)=\frac{1}{4}$ and $f^{*}\circ(f^{*})^{-1}(b)=0$, this contradicts with $\|f^{*}-f\|_{\infty}\leq\frac{1}{16}$. This completes the proof of the tight lower bound $\max\{d_{x}+1,d_{y}\}$ in Theorem 3.

B.3 Proof of tight lower bound in Theorem 1

Note that this statement can be easily generalized to an arbitrary codomain. To derive the statement, we prove a stronger statement: For any ReLU network $f$ of width $d_{x}$, either

where $f=0$ denotes that $f$ is a constant function mapping any input to zero. Then it leads us to the desired result directly. Without loss of generality, we assume that $f$ has $d_{x}$ hidden neurons at each layer except for the output layer and all affine transformations in $f$ are invertible (see Section 5.1).

This completes the proof of the tight upper bound in Theorem 1.

B.4 Proof of Lemma 5

i.e., $x\in\mathcal{S}$, then $\phi^{-1}\circ\sigma\circ\phi(x)=x$. Hence, the first statement of Lemma 5 holds.

Now, consider the second statement of Lemma 5. Suppose that $\langle a_{1},x\rangle+b_{1}\geq 0$ but $\langle a_{2},x\rangle+b_{2}<0$. Then, one can easily observe that $\phi^{-1}\circ\sigma\circ\phi$ maps a ray

containing $x$ to a single point \phi^{-1}\big{(}(\langle a_{1},x\rangle+b_{1},0)\big{)}, which is on $\partial\mathcal{S}$. In addition, similar arguments hold for cases that $\langle a_{1},x\rangle+b_{1}<0$, $\langle a_{2},x\rangle+b_{2}\geq 0$ and $\langle a_{1},x\rangle+b_{1}<0$, $\langle a_{2},x\rangle+b_{2}<0$. This completes the proof of Lemma 5.

B.5 Proof of Lemma 6

Let $x^{*}\notin\mathcal{T}^{\prime}$ be the first point in $\mathcal{P}\cap\partial\mathcal{S}$ in the trajectory of $\mathcal{P}$ starting from $x^{\prime}$. Then, the preimage of $x^{*}$ contains a ray $\mathcal{R}$ starting from $x^{*}$ (see the proof of Lemma 5 for the details) which must not intersect with $\mathcal{T}$; had the ray $\mathcal{R}$ intersected with $\mathcal{T}$, then $\mathcal{R}\cap\mathcal{T}$ must have mapped to $x^{*}$, which contradicts $x^{*}\notin\mathcal{T}^{\prime}$ and the definition of $\mathcal{P}$. Furthermore, from the definition of $x^{*}$, the subpath $\mathcal{P}^{\dagger}$ of $\mathcal{P}$ from $x^{\prime}$ to $x^{*}$ excluding $x^{*}$ satisfies $\mathcal{P}^{\dagger}\subset\text{int}(\mathcal{S})$. Hence, the preimages of $\mathcal{P}^{\dagger}$ and $\mathcal{T}^{\prime}\cap\text{int}(\mathcal{S})$ under $\phi^{-1}\circ\sigma\circ\phi$ stay identical by Lemma 5. This implies that there exist a path $\mathcal{P}^{\dagger}$ from $x$ to $x^{*}$, and then a path $\mathcal{R}$ from $x^{*}$ to infinity, not intersecting with $\mathcal{T}$. This contradicts the assumption of Lemma 6. This completes the proof of the first statement of Lemma 6.

Now, consider the second statement of Lemma 6. By Lemma 5, $x\neq x^{\prime}$ implies that $x\notin\mathcal{S}$ and $x^{\prime}\in\partial\mathcal{S}$. Here, as the preimage of $x^{\prime}$ contains a ray from $x^{\prime}$ containing $x$, this ray must intersect with $\mathcal{T}$ from the assumption of Lemma 6. Hence, $x^{\prime}\in\mathcal{T}^{\prime}$ and this completes the proof of the second statement of Lemma 6.

By combining the proofs of the first and the second statements of Lemma 6, we complete the proof of Lemma 6.

B.6 Proof of Lemma 7

Before starting our proof, we first introduce the following definitions and lemma. The proof of Lemma 21 is presented in Appendix B.7.

$\mathcal{U}$ is a “curve” if there exists $f\in\mathcal{F}(\mathcal{U})$.

$\mathcal{U}$ is a “simple curve” if there exists injective $f\in\mathcal{F}(\mathcal{U})$.

$\mathcal{U}$ is a “loop” if there exists $f\in\mathcal{F}(\mathcal{U})$ such that $f(1)=f(0)$.

$\mathcal{U}$ is a “simple loop” if there exists $f\in\mathcal{F}(\mathcal{U})$ such that $f(1)=f(0)$ and $f$ is injective on $[0,1)$.

$\mathcal{U}$ is a “polygon” if there exists piece-wise linear $f\in\mathcal{F}(\mathcal{U})$ such that $f(1)=f(0)$.

$\mathcal{U}$ is a “simple polygon” if there exists piece-wise linear $f\in\mathcal{F}(\mathcal{U})$ such that $f(1)=f(0)$ and $f$ is injective on $[0,1)$.

which is illustrated by the red dot in Figure 3. Then, we claim the following statement:

To prove the claim (11), we first introduce the following lemma.

B.7 Proof of Lemma 21