Minimum Width for Deep, Narrow MLP: A Diffeomorphism Approach

Identity function) Yes, Condition 1 provides a sufficient condition for this, as established in Lemma 4.1 of [1]. We will add this clarification to the paper.

$n\ge d_x, d_y$) Thank you for pointing this out. We will include this condition in the revised version.

Typos) Thank you for identifying the errors. We will correct them accordingly.

Misconception) In the proof of Lemma 2.4 of [2], the equation $\det(\nabla \Phi) > 0$ does not imply that $\Phi$ is a diffeomorphism.

References

[1] Kidger, Patrick, and Terry Lyons. "Universal approximation with deep narrow networks." Conference on learning theory. PMLR, 2020.

[2] Li, Li’Ang, et al. "Minimum width of leaky-ReLU neural networks for uniform universal approximation." International Conference on Machine Learning. PMLR, 2023.

Regarding Technical Barrier) Thank you for pointing this out. We will add definitions of several technical terms, including diffeomorphism, embedding, and certain topological and algebraic concepts used in Section 4.5.

Usefulness of our results) It is true that, at the current stage, the optimal width is achieved only in specific cases. However, our framework—which reduces the problem of identifying the optimal width to analyzing the quantity $w(n,m)$—is fundamental. Many existing lower bounds (at least for networks with Leaky ReLU activation) can be naturally interpreted and easily rederived within our framework.

For instance, the lower bound presented in Kim et al. (2024) can be reproduced by constructing a non-injective continuous function with $d$-dimensional inputs and $2d$-dimensional outputs. We believe that future work on width-based universal approximation should build upon this foundational framework.

Definition 3.1) Regarding Definition 3.1, note that $B$ is not required to contain $A$, so the definition is slightly different from the standard notion of density.

Thank you for the response and clarifications. My concerns have been addressed, I believe this paper should be accepted and have updated my score.

Question 1) It is true that our paper focuses on the uniform norm. However, the uniform norm lies at the core of robustness of neural networks and provides a meaningful setting in which to study the universal approximation property. Most existing works on the universal approximation property (UAP) primarily study the uniform norm or the $L^p$ norm.

Question 2) It is not accurate to claim that the assumptions made about the activation functions may not hold. All commonly used activation functions in practice satisfy our assumptions. In fact, the assumption is so mild that it is actually difficult to construct an activation function that violates it. We would appreciate it if you could provide an example of an activation function that does not satisfy the assumption.

Question 3) Our study is aimed at providing a theoretical validation of the minimum width required for universal approximation, and it does not attempt to provide empirical validation.

Please proof that the paper [https://arxiv.org/pdf/2308.15873] is not under other submission. Also, why the paper is missed? Please explain it.

I just reviewed the discussion about the arXiv paper. To avoid any potential information leaks, I decided not to open it. My understanding is that the reviewer found a paper with the same title under a certain submission template. This alone does not prove whether or not you have submitted the paper to another venue or journal—many people use templates simply because they like the style.

However, if the paper is the same but the authors are different, then we are dealing with plagiarism, and the paper should be rejected at a later stage.

My main question to the authors is the following:

Has any part, or the entirety, of this work been submitted to another venue or journal? This includes submissions in the pre-review and revision phases.

If the authors can open the link provided by the reviewer, do they believe they should cite it?

If it is an unpublished version of their own paper, they should not cite it.

If it is a timestamped paper by someone else that includes their results, they must either provide proof of concurrent work—ideally published in a journal, which is better suited for such cases.

If it is work produced afterward, then it is unethical to claim novelty.

I have tried to adhere to traditional principles here.

Would the authors be subject to desk rejection if it is clear they have violated the rules? Please be aware that the reviewer may be criticized by the AC if this turns out to be their own mistake.

Let us keep everyone accountable to their corresponding responsibilities.

Question 1 and 2) While Teshima et al. use affine coupling flows and single-coordinate transformations as fundamental building blocks, our approach relies solely on MLPs, which highlights the additional difficulty of our setting. Also

The choice of affine coupling flows and single-coordinate diffeomorphisms is motivated by technical considerations, allowing us to build upon the existing work of Teshima et al. This approach reduces the problem of approximating an entire diffeomorphism to approximating specific functions in which only one coordinate is modified. This structure facilitates approximation by deep narrow neural networks.

Question 3($\alpha(\sigma)$)) We believe that the overhead term $\alpha$ can be reduced. There is no particular reason to believe that the Leaky ReLU activation function is inherently more powerful than other commonly used activation functions. In fact, for ReLU networks, it has been shown that a width of $d_x + d_y$ is sufficient, whereas our method currently requires an additional $+1$ term.

Question 4(Other network architectures) We believe that skip connections can improve the minimum width requirement. Consider a structure of the form $I + n(x)$, where $n \in \Delta^{\sigma}_{d,d,d}$. Suppose we aim to approximate an arbitrary function $f$. Let $f_2$ be a $C^1$ function that is close to $f$. Then, a function of the form $-I + \varepsilon f_2$ can be a diffeomorphism for sufficiently small $\varepsilon$, and can be approximated by $n$. Therefore, the summation $I + (-I+ \varepsilon f_2) =\varepsilon f_2$ can be approximated by deep narrow MLPs with skip connections. When composed with suitable affine transformations at the final layer, this construction enables the approximation of arbitrary continuous functions. This suggests that skip connections help the universal approximation while potentially reducing the required network width.

For ResNet blocks, we believe skip connections lead to a similar reduction effect. For instance, under the $L^p$ norm, the optimal minimum width for approximating a function with $d$-dimensional input and output is $d$ for MLPs [3], whereas for ResNet blocks, it can be as low as $1$ [2].

For convolutional neural networks, defining the notion of minimum width is more subtle. In the CNN literature (e.g., [1]), the number of channels is often used as a proxy for width. In that context, an affine transformation is constructed from an input shape $c_x \times d_1 \times d_2$ to an output shape, and the problem effectively reduces to computing the minimum width for an input dimension $d_x = c_x d_1 d_2$ and output dimension $d_y = c_y d_1 d_2$ as the representing power of deep narrow CNN is almost same to that of deep narrow MLPs.

Believing that the optimal minimum width for MLPs is asymptotically

then the corresponding width for CNNs would follow the same form:

This implies similar minimum width for the CNNs.

We expect analogous improvements in representational power for RNNs using similar reasoning.

Question 5) The quantity $w(n, m, \sigma)$ represents the minimum intermediate dimension required to preserve the information of an arbitrary function with $n$-dimensional input and $m$-dimensional output.
For example, consider the identity function $I \in C(\mathbb{R}^2, \mathbb{R}^2)$ and suppose it is decomposed as $I = g \circ f$, where $f \in C(\mathbb{R}^2, \mathbb{R})$ and $g \in C(\mathbb{R}, \mathbb{R}^2)$.
Since the identity function is injective, $f$ must also be injective.
This leads to a contradiction, because the intermediate dimension (in this case, 1) is too small to preserve the complexity of the original function.

More specifically, the difficulty of diesntagling manifold structure of self-intersecting function is captured by $w(n,m,\sigma)$. The more self-intersections the target function has, the harder it becomes to disentangle it in the intermediate dimension.

Question 5 & 6) Yes, the issue is that intersections are not robust under perturbations. We believe that the optimal minimum width satisfies $w(k,2k-1) = 2k+1$ when $k$ is odd because there exists a 2-to-1 self-intersection structure of cycles. However, we are currently unaware of any tools that can preserve such intersection structures under small perturbations in the uniform norm. We are also uncertain whether obstruction theory provides a suitable framework for handling this issue. If the reviewer is aware of any relevant concepts or techniques, we would greatly appreciate any suggestions.

Related Works) Thank you for the valuable references. We will add it to related works section.

Typos) Thank you for pointing out the typos. We will correct them. Regarding Definition A.3, $\tau$ should be chosen such that the resulting element is a diffeomorphism.

References

[1] Hwang, Geonho, and Myungjoo Kang. "Universal Approximation Property of Fully Convolutional Neural Networks with Zero Padding." arXiv preprint arXiv:2211.09983 (2022).

[2] Lin, Hongzhou, and Stefanie Jegelka. "Resnet with one-neuron hidden layers is a universal approximator." Advances in neural information processing systems 31 (2018).

[3] Shin, Jonghyun, et al. "Minimum width for universal approximation using squashable activation functions." arXiv preprint arXiv:2504.07371 (2025).

Question 1) Sorry for the confusion. The statement “required width for approximation” in Lines 153–154 refers to the minimal width required to approximate any arbitrary continuous function using diffeomorphisms, as formulated in Equation (12), not the width of neural networks. We will revise the statement from “Now, we quantify the required width for approximation” to “Now, we quantify the required geometric width for approximation” to clarify this point.

Question 2) Lemma 4.3 requires only smoothness.

Question 3) Thank you for pointing this out. While we appreciate your observation, we respectfully note that the topological and algebraic components of the proof are not entirely straightforward, as they involve several subtle challenges. We will add the following proof outline to clarify our approach:

In [1]., it was shown that any diffeomorphism can be approximated by a composition of single coordinate transformations. Therefore, it suffices to prove that deep narrow MLPs can approximate any such single coordinate transformation (see Definition A.3 for the formal definition). This is established in Lemma B.1. With the exception of the Leaky-ReLU case, the proof is relatively direct.

For the Leaky-ReLU case, we progressively extend the class of functions that can be approximated. Using Lemma B.3, we show that any increasing scalar function can be approximated by width-1 Leaky-ReLU networks. This result implies that any width-$d$ neural network with increasing activation functions can be approximated by a Leaky-ReLU network of the same width (see Corollary B.4).

Building on this, we prove in Lemma B.5 that any ACF (see Definition A.4) can be approximated by deep narrow MLPs. Finally, Lemma B.6 shows that any single coordinate transformation can, in turn, be approximated by an ACF.

[1] Teshima, Takeshi, et al. "Coupling-based invertible neural networks are universal diffeomorphism approximators." Advances in Neural Information Processing Systems 33 (2020): 3362-3373.