We thank the reviewer for their positive evaluation and thoughtful feedback. We answer the reviewer’s question below.

In practice, both and norms are too weak because derivatives are not guaranteed to converge. For example, can we state the universality in a Sobolev space?

We thank the reviewer for this interesting question. For the Sobolev $W^{1,q}$-norm with small $q<d_x$, by the Sobolev embedding theorem, the Sobolev space $W^{1,q}(\mathbb{R}^{d_x})$ can be embedded into $L^p(\mathbb{R}^{d_x})$ with $q=pd_x/(d_x-p)$. Hence, in this case, universal approximation under $W^{1,q}$-norm reduces to our result. However, we do not know whether our minimum width bounds extend to $q\ge d_x$. We think finding the minimum width under general Sobolev spaces is a very interesting problem and would like to pursue it as a future research direction.

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 below.

It does not occur to me what is the sense of the first assertion in lemma 7. Isn't that obvious?

As the reviewer pointed out, $w_{\sigma}\ge\max\\{d_x,d_y\\}$ is a trivial lower bound. We wrote it to formally show that our upper bound on the minimum width is tight. We will write that this bound can be easily derived in the final draft.

Lemma 10, the symbol for the ball should be introduced.

The notation $\mathcal B$ for the ball is defined in the first paragraph of Section 2 (Line 118). Nevertheless, for better readability, we will add a pointer to this definition after Lemma 10 in the final draft.

How does one see that ReLu is not squashable in order to explicitly show that there is no contradiction to Lu et al (NeurIPS 2017)? A formal argument given in the appendix would be solicited.

Here, we clarify the following claim: “Our minimum width $\max\\{d_x,d_y,2\\}$ for squashable functions does not contradict the lower bound $d_x+1$ for ReLU networks in (Lu et al., 2017) since ReLU is not squashable.” If this comment is not what the reviewer considered, please let us know.

We note that the lower bound $d_x+1$ in (Lu et al., 2017) considers the entire Euclidean space $\mathbb R^{d_x}$ while we consider a compact subset in $\mathbb R^{d_x}$. In fact, the tight minimum width for ReLU on a compact domain is known to be $\max\\{d_x,d_y,2\\}$ (Kim et al., 2024), which is smaller than the minimum width $\max\\{d_x+1,d_y\\}$ for ReLU on $\mathbb R^{d_x}$ (Park et al., 2021). Namely, we can have the minimum width $\max\\{d_x,d_y,2\\}$ for ReLU regardless of its non-squashability.

This is only a preprint, should however be mentioned: [1] Dennis Rochau et al., New advances in universal approximation with neural networks of minimal width. The authors should comment shortly on their minimal internal depth 1 achieved, as this has implications for the universal approximation theory of autoencoders, cf [1]

We appreciate the reviewer for suggesting an interesting connection between our results and autoencoders, and providing an intriguing paper. According to Dennis et al., we also found that our construction has an autoencoder structure (i.e., minimal internal width 1). We will cite this paper and add a related discussion, including a new lower bound for the supremum norm in (Dennis et al.), to the final draft.

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 below.

While previous papers have not exhaustively covered all activation functions, it is straightforward to deduce results for many activation functions from existing findings.

We do not think that tight minimum width results for general activation functions (e.g., nonaffine analytic) can be straightforwardly deduced from existing results that only consider ReLU and its variants (Park et al., 2021b; Cai, 2023; Kim et al., 2024). For example, Cai (2023) showed the minimum width for Leaky-ReLU networks using the following two results: (1) Neural ODEs can approximate any $L^p$ functions [1], (2) Leaky-ReLU networks can approximate any neural ODEs [2]. Here, (2) requires an activation to either have a strictly monotone breakpoint or have two asymptotic lines with different nonzero slopes. Namely, their proof technique does not directly extend to general activation functions such as nonaffine analytic functions.

In addition, Park et al. (2021b) and Kim et al. (2024) proved the minimum width for networks using ReLU or ReLU-like activation functions using the properties of ReLU (and its variants): it maps the negative inputs to (approximately) zero while the positive input is preserved by an (approximate) identity map. However, general activation functions do not have such properties, and hence, how to extend their constructions to general activation functions is unclear.

[1] Li et al., "Deep learning via dynamical systems: An approximation perspective." Journal of the European Mathematical Society, 2022.

[2] Duan et al., "Vanilla Feedforward Neural Networks as a Discretization of Dynamical Systems." Journal of Scientific Computing 101, no. 3 (2024): 82.

The proof strategy in this paper is essentially no different from those in earlier works, especially the encode-memorize-decode techniques considered in Park (2021) or the earlier bit extraction techniques. Therefore, I believe this paper is an incremental contribution and is not suitable for publication in a top conference like ICML.

We strongly disagree that our proof strategy is not different from those in earlier works. As we mentioned in the previous response, the existing constructions by Park et al., (2021b) highly rely on specific properties of ReLU and its variants, which cannot be found in general activation functions. To show the tight minimum width for a general class of activation functions, we propose a completely different condition for activation functions called squashable (Definition 1), and our proofs are based on this condition.

Since we are using different properties of activation functions, our constructions of the encoder and decoder significantly differ from prior ones. Our decoder construction is based on a novel filling-curve argument (Definition 2) that did not appear in prior constructions. Our encoder explicitly slices the input domain along each coordinate via a width $d_x$ network using the squashability, while prior constructions use either a larger width $d_x+1$ (Park et al., 2021) or only prove the existence of a proper slicing (Kim et al., 2024) based on the properties of ReLU.

The cited papers are not discussed in detail in this paper, especially Park (2021), Cai (2023), and Kim (2024).

While we compared our bound with the bounds in (Park, 2021b; Cai, 2023; Kim, 2024) in Sections 1.1–1.2, following the reviewer’s comment, we will add the above discussions and thoroughly compare our proof techniques with prior ones in the final draft.

The activation functions considered in this paper are related to the Step function, yet the paper does not mention the study on Step activation functions in Park (2021).

Park et al. (2021b) showed that if a network can use both ReLU and Step, the minimum width for universal approximation under the supremum norm is $\max\\{d_x+1,d_y\\}$. Here, they use the discontinuity of the Step function, which enables them to derive the tight minimum width under the supremum norm. On the other hand, our activation functions of interest (i.e., those satisfying Conditions 1 and 2) are continuous and do not have additional ReLU; hence, the proof completely differs from the existing ReLU+Step network result. We will add this discussion to the final draft.

The first time I encountered the equation $\max\\{d_x,d_y,2\\}$ was in Cai (2023), but it is not listed in Table 1.

Following the reviewer’s comment, we will add the bound $\max\\{d_x,d_y,2\\}$ by Cai (2023) to Table 1 in the final draft.

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 positive evaluation and valuable comments. We address the reviewer’s concern and clarify our contribution below.

The result itself is an incremental contribution, extending known results that already covered most popular activation functions, to wider set of activation functions.

While prior works derived tight minimum width for ReLU and its variant, we believe that studying general activation functions is not incremental since (1) prior results do not cover popular non-ReLU-like activation functions such as sigmoid, tanh, and sin, and (2) minimum width results for general activation functions can be applied to any new activation functions that can be used in future as long as they satisfy our conditions. We believe that our result can be used to better understand the fundamental limit of narrow networks.

In addition, we would like to note that our result is not a simple extension of prior works that only consider ReLU and its variants (Park et al., 2021b; Cai, 2023; Kim et al., 2024). For example, the proof of the Leaky-ReLU result by Cai (2023) heavily relies on the property of Leaky-ReLU: it contains at least one break point and is strictly monotone near that point. Namely, their proof technique cannot be directly extended to general activation functions such as nonaffine analytic functions. Likewise, Park et al. (2021b) and Kim et al. (2024) rely on the properties of ReLU (and its variants): it maps the negative inputs to (approximately) zero while the positive input is preserved by an (approximate) identity map. However, general activation functions do not have such properties, and how to extend their constructions to general activation functions was unclear.

To show tight bounds for general activation functions, we propose a novel condition on activation functions (Condition 2) that is satisfied by all nonaffine analytic functions and a class of piecewise functions, and explicitly construct a universal approximator of the minimum width based on that condition. We will add this discussion to the final draft.

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