Minimum width for universal approximation using ReLU networks on compact domain

We thank the reviewer for their positive evaluation and valuable feedback. We address all comments of the reviewer, and provide pointers to the corresponding updates in the revised draft. All the updates are color-coded in the revised version.

A similar tight result was achieved in Cai 2023 for the special case of Leaky-ReLU.

We would like to emphasize that the construction for achieving the tight minimum width of Leaky-ReLU networks for $L^p$ approximation by Cai (2023) does not generalize to ReLU networks. Cai (2023) constructed a Leaky-ReLU networks of width $\max\\{d_x,d_y,2\\}$ by combining two observations: (1) $L^p$ functions can be approximated by neural ODEs (Li et al., 2022) and (2) neural ODEs can be approximated by Leaky-RELU networks of width $\max\\{d_x,d_y,2\\}$ (Duan et al., 2022). However, the second observation requires the strict monotonicity of Leaky-ReLU networks, which does not extend to ReLU ones. To bypass this issue and show the tight minimum width for ReLU networks, we propose a completely different approach based on the characteristics of ReLU networks (Lemmas 5 and 7), which further extends to other (possibly non-monotone) ReLU-Like activation functions. We have clarified this difference in the revised draft (page 4 in Section 3).

The gap between known upper and lower bounds is merely an additive constant.

Although our results improve constant factors of existing bounds on the minimum width, we believe that our results are important contributions to the expressive power of neural networks. As the reviewer pointed out, our Theorems 1 and 2 provide a tight minimum width of networks using various activation functions for $L^p$ approximation. We think such tight characterization enables us to understand how the expressive power of neural networks can be affected by problem setups: for example, our Theorems 1 and 2 show dichotomy between the minimum widths for $L^p$ approximation on the whole Euclidean space and compact sets. To our knowledge, such a separation result was previously unknown in terms of the minimum width.

Theorem 3 also generalizes dichotomy between $L^p$ and uniform approximation to general activation functions and general input/output dimensions. Furthermore, we recently found that Theorem 3 is tight when $2d_x=d_y$ for Leaky-ReLU networks, together with the matching upper bound $\max\\{2d_x+1,d_y\\}$ [Hwang, 2023]. We think our tight minimum width results can help better understand the universal approximability of deep and narrow neural networks.

We have added the new tight minimum width result using Theorem 3 to the revised draft (page 3 in Section 1.2 and page 5 in Section 3).

[Hwang, 2023] Minimum Width for Deep, Narrow MLP: A Diffeomorphism Approach, arXiv preprint 2308.15873

On separation between the whole Euclidean space and compact subset.

We thank the reviewer for providing a reference [Lu, 2021] that we were not aware of. We have cited this work in the discussion about the separation between the whole Euclidean space and compact subset in our revised draft (page 4 in Section 3).

[Lu, 2021] A note on the representation power of ghhs, Zhou Lu, arXiv preprint 2101.11286

We would be happy to clarify any concerns or answer any questions that may come up during the discussion period.

We thank the reviewer for their positive evaluation and thoughtful feedback. We address all comments of the reviewer, and provide pointers to the corresponding updates in the revised draft. All the updates are color-coded in the revised version.

More details and rigor in the construction in Lemma 6's proof.

We thank the reviewer for pointing this out. Following the reviewer’s comment, we have added details to the proof of Lemma 6 in the revised draft (pages 14-16 in Appendix B.4).

Impact of metric entropy on minimal width.

We are not sure if we correctly understand the definition of the metric entropy that you were considering, but we try to answer with the following definition, which appears in the covering argument in statistics: $\log N(X,\delta)$ where $N(X,\delta)$ denotes the minimum number of $\delta$-balls that can cover $X$ (i.e., the logarithm of the covering number). We consider $L^p$ approximation in this answer. If this problem setup is not what the reviewer was considering, please let us know.

As the reviewer pointed out, any map from a single point (of the zero metric entropy) to a real number can be exactly represented by a ReLU network of width one. We think this observation extends to any domain of zero Lebesgue measure (including any finite sets) since we can ignore such sets in $L^p$ approximation; ignoring them incurs zero $L^p$ error. Under this observation, one interesting question we think is that “what if our error use a different measure, other than the Lebesgue one?” For example, the Cantor set $\mathcal C$ has zero Lebesgue measure but can have non-zero $d$-dimensional Hausdorff measure for $d<\log(2)/\log(3)$. In such a case, for universal approximation, we expect that ReLU networks of width one are insufficient since they can only represent monotone functions. Here, since the value $\log(2)/\log(3)$ is the Minkowski dimension of the Cantor set defined as $d_M(\mathcal C):=\lim_{\delta\to0^+} (\log N(\mathcal C,\delta))/(\log(1/\delta))$, one may find a connection between the metric entropy and the minimum width for universal approximation under a Hausdorff measure. We believe investigating the universal approximation property of neural networks under various measures is an interesting future research direction.

More general implications.

We thank the reviewer for this suggestion. As the reviewer pointed out, all of our results hold for an arbitrary compact domain in the Euclidean space. Using the extension lemmas provided by the reviewer, we have made this point clearer in the revised draft (page 5 in Section 3).

Improving minimal width estimates for general nonlinearities.

We appreciate the reviewer for this suggestion. [Zhang et al., 2023] approximate ReLU networks using a network using a class of activation functions by scaling the width and depth of a network with multiplicative factors 3 and 2. Applying this result to our Theorem 1 gives us an upper bound $3\max\\{d_x,d_y,2\\}$ on the minimum width. However, we found that this bound exceeds the known upper bound $\max\\{d_x+2,d_y+1\\}$ in Theorem 4 by Park et al. (2021).

On the other hand, our results easily extend to other network architectures: recurrent neural networks (RNNs) and bidirectional recurrent neural networks (BRNNs). For these networks, we consider universally approximating the space of $L^p$ functions that maps a length $T$ sequence of $d_x$-dimensional vectors to a length $T$ sequence of $d_y$-dimensional vectors, denoted by $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$. Since the $t$-th output of RNN is always a function of the first to $t$-th inputs, for RNNs, we consider universally approximating the space of such functions, called past-dependent $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$, while we consider $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$ for BRNNs.

We recently showed that the minimum width of RNNs to be dense in past-dependent $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$ is exactly $\max\\{d_x,d_y,2\\}$ if the activation function is one of ReLU, SOFTPLUS, Leaky-RELU, ELU, CELU, SELU, GELU, SILU, and MISH; here GELU, SILU, and MISH require $d_x+d_y\ge3$. In addition, we also show that the minimum width of BRNNs to be dense in $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$ is upper bounded by $\max\\{d_x,d_y,2\\}$ if the activation function is ReLU or in ReLU-Like. We have added these results with formal problem setups and proofs in the revised draft (pages 27-34 in Appendix F).

[Zhang et al., 2023] Deep Network Approximation: Beyond ReLU to Diverse Activation Functions, arXiv preprint arXiv:2307.06555, 2023

We would be happy to clarify any concerns or answer any questions that may come up during the discussion period.

We appreciate the reviewer for their time and effort to provide valuable comments. We address all comments of the reviewer, and provide pointers to the corresponding updates in the revised draft. All the updates are color-coded in the revised version.

This paper only generalizes Leaky-RELU to RELU-LIKE activations, and derives the same result. I think this makes the contribution of this paper incremental.

We believe that our contribution extending Leaky-ReLU to ReLU-Like activation is non-trivial: the existing proof for Leaky-ReLU networks does not extend to ReLU and ReLU-like activation functions (our Theorems 1 and 2). The proof of Cai (2023) for showing the upper bound on the minimum width $\max\\{d_x,d_y,2\\}$ consists of two parts: they (1) approximate $L^p$ functions via neural ODEs following (Li et al., 2022) and (2) approximate neural ODEs via Leaky-RELU networks of width $\max\\{d_x,d_y,2\\}$ by using results in (Duan et al., 2022). Here, the second part heavily relies on the strict monotonicity of Leaky-ReLU, and hence, does not generalize to ReLU. To bypass this issue and show the tight minimum width for ReLU networks, we propose a completely different proof technique (not using neural ODEs) utilizing properties of ReLU networks (Lemmas 5 and 7), which generalizes to (possibly non-monotone) ReLU-Like activation functions. We also note that our Theorems 1 and 2 first show the separation between the whole Euclidean space and compact subset for $L^p$ approximation, which was unknown up to our knowledge.

Furthermore, we would like to emphasize that our Theorem 3 is also an important contribution. The best known lower bound on the minimum width for uniform approximation under general $d_x,d_y$ and general activation functions was $\max\\{d_x+1,d_y\\}$ (Johnson, 2019; Park et al., 2021). However, a few exceptional cases indicate that this bound can be improved: $d_y+1 > \max\\{d_x+1,d_y\\}$ is a tight lower bound for ReLU/Leaky-ReLU networks when $d_x=1$ and $d_y=2$ (Park et al., 2021; Cai, 2023). Our Theorem 3 improves existing lower bounds by showing that the minimum width for uniform approximation is at least $d_y+1$ if $d_x < d_y \le 2d_x$ for continuous activation functions that can be uniformly approximated by a sequence of continuous injections. As the reviewer pointed out, Theorem 3 also extends the dichotomy between and uniform approximations to general activation functions and input/output dimensions. In addition, we recently found that Theorem 3 is tight when $d_y=2d_x$ for Leaky-ReLU networks, together with the matching upper bound $\max\\{2d_x+1,d_y\\}$ in [Hwang, 2023]. We think our tight minimum width results can help better understand universal approximability of deep and narrow neural networks.

In the revised draft, we have clarified the difference between the existing Leaky-ReLU network result (Cai, 2023) and ours (page 4 in Section 3), and added the new tight minimum width result for uniform approximation using Theorem 3 (page 3 in Section 1.2 and page 5 in Section 3).

[Hwang, 2023] Minimum Width for Deep, Narrow MLP: A Diffeomorphism Approach, arXiv preprint 2308.15873, 2023

The technical part is not very deep and mostly based on the technical results from previous papers such as (Cai, 2023).

We believe that our technical results are not mostly based on previous papers such as (Cai, 2023). Theorem 1 (and Theorem 2) uses the lower bound $\max\\{d_x,d_y\\}$ from (Cai, 2023); however, this bound can be shown using rather straightforward arguments. If a network has width $d_x-1$, then it must have the form $g(Mx)$ for some continuous function $g:\mathbb R^{d_x-1}\to\mathbb R^{d_y}$ and $M \in \mathbb{R}^{(d_x-1) \times d_x}$. Hence, the network cannot use the full information of inputs and cannot universally approximate, e.g., consider approximating $\\|x\\|_2^2$. Likewise, if a network has width $d_y-1$, then it must have the form $Nh(x)$ for some continuous function $h:\mathbb R^{d_x}\to\mathbb R^{d_y-1}$ and $N\in\mathbb{R}^{d_y\times (d_y-1)}$ and cannot universally approximate, e.g., consider approximating a path that visits all vertices of a $d_y$-dimensional standard simplex along its edges. Combining these two arguments gives us the lower bound $\max\\{d_x,d_y\\}$.

On the other hand, we believe our proof of the upper bound $\max\\{d_x,d_y,2\\}$ in Theorem 1, which we think the most critical part for showing the tight minimum width, is non-trivial and has technical novelty, especially compared to the lower bound. As we previously answered, prior result in (Cai, 2023) does not extend to ReLU (and ReLU-Like activation functions). We use a coding scheme; however, the existing coding-based ReLU network construction achieving the tight minimum width (Park et al., 2021) considers the whole Euclidean space and requires width at least $d_x+1$. Namely, existing results cannot directly show the tight minimum width in our problem setups: ReLU or ReLU-Like activation functions and a compact domain. We would like to also note that Theorem 3, which is also an important contribution of our submission, does not rely on any of previous technical results up to our knowledge.

We have added this discussion to the revised draft (page 5 in Section 3).

Exact minimum width for more architectures used in practice.

We thank the reviewer for this interesting comment. Following the reviewer’s comment, we have explored other network architectures and found that our proof techniques can be used for bounding the minimum width of recurrent neural networks (RNNs) and bidirectional RNNs (BRNNs) for $L^p$ approximation. Specifically, we consider universally approximating the space of $L^p$ functions that maps a length $T$ sequence of $d_x$-dimensional vectors to a length $T$ sequence of $d_y$-dimensional vectors, denoted by $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$. Since the $t$-th output of RNN is always a function of the first to $t$-th inputs, for RNNs, we consider universally approximating the space of such functions, called past-dependent $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$, while we consider $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$ for BRNNs.

We proved that the minimum width of RNNs to be dense in past-dependent $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$ is exactly $\max\\{d_x,d_y,2\\}$ if the activation function is one of ReLU, SOFTPLUS, Leaky-RELU, ELU, CELU, SELU, GELU, SILU, and MISH; here GELU, SILU, and MISH require $d_x+d_y\ge3$ as in Theorem 2. Furthermore, we also show that the minimum width of BRNNs to be dense in $L^p([0,1]^{d_x\times T},\mathbb R^{d_y\times T})$ is upper bounded by $\max\\{d_x,d_y,2\\}$ if the activation function is ReLU or in ReLU-Like.

We have added these new results with corresponding proofs and formal problem setups in the revised draft (pages 27-34 in Appendix F).

We would be happy to clarify any concerns or answer any questions that may come up during the discussion period.