Optimal Minimum Width for the Universal Approximation of Continuously Differentiable Functions by Deep Narrow MLPs

Novelty) Thank you for your comment. The idea of approximating diffeomorphisms using deep narrow MLPs and control theory was first introduced in [1]. And later in [2], the authors applied this property to study universal approximation under the uniform norm. However, their conclusion was partially incorrect due to a flawed treatment of diffeomorphisms. In [9], the concept of approximating continuous functions using diffeomorphisms is rigorously estabilished. However, the authors do not provide lower bounds that are applicable in practical settings. Moreover, due to their proof technique being tailored to the uniform norm, the result cannot be directly generalized to the Sobolev norm setting.

In our work, we adopt a framework based on control theory and extend the results to the Sobolev norm setting. We believe that introducing the Sobolev norm into the minimum width literature is itself a novel contribution, as it offers a useful tool—such as the robustness of topological structures—for establishing lower bounds. Demonstrating this property is also one of our key contributions. Moreover, we provide a rigorous characterization of the relationship between the optimal minimum width and $\Omega(n,m)$ in the Sobolev norm.

Most importantly, by employing concepts from real projective spaces and the Borsuk–Ulam theorem, we establish—for the first time—a nontrivial optimal lower bound in cases that had not been previously proven. To the best of our knowledge, this is the first instance in which such a bound is derived using geometric concepts, including real projective spaces and the Borsuk–Ulam theorem. We believe this is where the novelty of our work lies.

Regarding the ResNet case, we will add relevant references [3–5] to the related work section. In particular, [4] employs a similar control-theoretic technique for approximation. If there are additional references we have missed, we would appreciate your suggestions.

Significance) Thank you for pointing this out. We will add the following sentences to the introduction:

However, there has been a scarce number of papers that study norms involving derivatives of functions in the setting of deep narrow MLPs. Many deep learning techniques directly penalize the difference between the derivative of the target function and that of the network. These include Sobolev Training [6], Physics-Informed Neural Networks (PINNs) [7], and Generative Adversarial Networks with Gradient Penalty [8].

Vague Conditions) We will revise the statement as follows:

In some cases, the lower bound coincides with the upper bound, thus identifying the optimal minimum width. This includes interesting cases such as (8,8) and (16,8). The exact pairs to which our result applies can be found in Theorem 5.9.

The proof of Lemma A.1) Thank you for identifying the error. We will revise the proof and add a footnote as suggested by the reviewer.

Minor Issues) We will correct these as noted.

References

[1] Duan, Yifei, et al. "Vanilla Feedforward Neural Networks as a Discretization of Dynamical Systems." arXiv preprint arXiv:2209.10909 (2022).

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

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

[4] Aizawa, Yuto, Masato Kimura, and Kazunori Matsui. "Universal approximation properties for an ODENet and a ResNet: Mathematical analysis and numerical experiments." arXiv preprint arXiv:2101.10229 (2020).

[5] Tabuada, Paulo, and Bahman Gharesifard. "Universal approximation power of deep residual neural networks through the lens of control." IEEE Transactions on Automatic Control 68.5 (2022): 2715-2728.

[6] Czarnecki, Wojciech M., et al. "Sobolev training for neural networks." Advances in neural information processing systems 30 (2017).

[7] Raissi, Maziar, Paris Perdikaris, and George E. Karniadakis. "Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations." Journal of Computational physics 378 (2019): 686-707.

[8] Arjovsky, Martin, Soumith Chintala, and Léon Bottou. "Wasserstein generative adversarial networks." International conference on machine learning. PMLR, 2017.

[9] Hwang, Geonho. "Minimum width for deep, narrow mlp: A diffeomorphism approach." arXiv preprint arXiv:2308.15873 (2023).

Notations) Thank you for pointing out. We will ensure that the notation $d_x, d_y$​ is used consistently throughout the paper.

Typo) Thank you for pointing out the typo. We will fix it.

Essentialness of $C^1$) We believe the assumption is essential.
Since $L^{\infty}$ is not separable (i.e., it does not have a countable dense subset), neural networks with continuous activation functions(which form only a countable-dimensional function class) cannot approximate all functions in this space.
Similarly, the space of continuous functions with bounded derivatives is also non-separable.
As a result, neural networks with $C^1$ activation functions cannot approximate certain functions in that space.
Therefore, it is necessary to restrict the function space to a $C^1$-function space with a countable basis.

Extension to Higher-Order) Thank you for the insightful question. We believe that if $k \geq 2$, the same optimal minimum width as in the case $k = 1$ (our setting) still holds. Since the topology of $W^{k,\infty}$ becomes finer for $k \geq 2$, the lower bound remains valid. For the upper bound, we expect that Lemma B.7 can be generalized to the $k \geq 2$ case, albeit with some tedious calculations.

We believe that the main obstruction to proving the upper bound lies in Lemma B.2. To approximate affine transformations using nonlinear activation functions in the $W^{k,\infty}$ norm, additional arguments are needed. For instance, in the case $k = 2$, if there exists a point $x$ such that $\sigma'(x) \neq 0$ and $\sigma''(x) = 0$, a result analogous to Lemma B.2 can be established.
Such an activation function may potentially be constructed by composing simpler activation functions.

Extending these results to the case $k > 2$ would be an interesting direction for future research.

Limitations) Thank you for pointing out the limitations. We will add to the paper noting that our result is non-constructive and asymptotic in nature.

Regarding the motivation) Thank you for the valuable advice. We will add the following paragraphs to the introduction:

1. The choice of neural network architecture plays a crucial role in determining performance. However, in practice, architectural decisions are often made through trial and error. It is therefore important to provide theoretical guidance on what should be avoided and how to select appropriate width and depth based on the input space, target function, and specific tasks. In particular, from the perspective of approximation power, identifying the minimum width required for universal approximation is a key question.

2. However, there has been a scarce number of papers that study norms involving derivatives of functions in the setting of deep narrow MLPs. Many deep learning techniques directly penalize the difference between the derivative of the target function and that of the network. These include Sobolev Training [1], Physics-Informed Neural Networks (PINNs) [2], and Generative Adversarial Networks with Gradient Penalty [3].

Regarding the presentation) Thank you for the detailed advice.

• We will defer the equational definition of deep narrow MLPs and the definition of the set of MLPs to the appendix.
• We will also incorporate a verbal explanation of $w$, as suggested by the reviewer.
• Additionally, we will include definitions of immersion, submersion, diffeomorphism, embedding, and transversality in the appendix.
• The formal definition of the flow of a vector field will be defered to the appendix.
• We will focus mainly on explaining the concepts or strategies of the proofs, rather than including all detailed proofs.

Domain of the approximation) Thank you for the insightful question. In our setting, $U$ is not assumed to be compact; it is typically an open set, such as $\mathbb{R}^n$. The space $W_{\textrm{loc}}^{1,\infty}(U; \mathbb{R}^m)$ is defined via local behavior: for a precompact set $V\Subset U$, we consider the restriction of functions to $V$ and $W^{1,\infty}(V; \mathbb{R}^m)$ norm.

In other words, the two statements are equivalent:

• $C^1(\mathbb{R}^n; \mathbb{R}^m)$ can be universally approximated in the $W_{\textrm{loc}}^{1,\infty}(\mathbb{R}^n; \mathbb{R}^m)$ norm.
• For any precompact set $V\Subset \mathbb{R}^n$, $C^1(V; \mathbb{R}^m)$ can be universally approximated in the $W^{1,\infty}(V; \mathbb{R}^m)$ norm.

In short, this is simply a precise way of stating that we can approximate any $C^1$ function in the Sobolev norm on any compact subset.

We will clarify this point in the revised version of the paper to avoid confusion and to make the domain of approximation more explicit.

References

[1] Czarnecki, Wojciech M., et al. "Sobolev training for neural networks." Advances in neural information processing systems 30 (2017).

[2] Raissi, Maziar, Paris Perdikaris, and George E. Karniadakis. "Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations." Journal of Computational physics 378 (2019): 686-707.

[3] Arjovsky, Martin, Soumith Chintala, and Léon Bottou. "Wasserstein generative adversarial networks." International conference on machine learning. PMLR, 2017.

I thank the authors for their response and for their answers to my question about the approximation domain. I maintain my recommendation for acceptance, encouraging the authors to make the revisions/clarifications that we discussed.

Regarding the varying activation functions) Thank you for the valuable advice. In fact, the use of varying activation functions was primarily motivated by the elegance of Equation (33) in Theorem 4.6:

We believe that, for certain activation functions, a set of varying activation functions could potentially be replaced by a single fixed activation function. However, we have not been able to find a concrete example demonstrating this. We consider this an interesting direction for future research. We will also improve the writing related to the activation function to better convey the content.

Regarding the contradiction to [Johnson2018]) Yes, in the case of $\sigma = \mathrm{LR}$, the activation function can be a Leaky ReLU with a different value of $\beta$ at each layer. However, this does not imply a contradiction with the result of [Johnson 2018], even when the activation function is fixed. This is because Theorem 4.1 concerns the approximation of diffeomorphisms specifically, rather than arbitrary continuous functions.

Algebraic Topology Literature) To the best of our knowledge, there is no existing reference that explicitly defines the quantity $\Omega$. However, several studies offer valuable insights that contribute to understanding or computing the value of $\Omega$. We have made an effort to compile and list all known values of $\Omega$ in the paper, based on our current understanding of geometry and topology.