- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates the exact minimum width required for universal approximation by deep ReLU neural networks. The authors prove that the minimum width is exactly k when the output dimension satisfies k \geq 2d+2, where d is the input dimension. This result improves the previously known upper bound and extends to several activation functions, including GELU, SiLU, and Softplus.
The main theoretical contributions include a general upper bound on the minimum width for continuous nonaffine activations, a rigidity result for approximating diffeomorphisms with narrow ReLU networks, and a geometric characterization of the width required for universal approximation. The authors also investigate the remaining open case k=2d+1 and identify limitations of their construction.
The results are supported by rigorous mathematical proofs and formal verification in Lean 4. The paper provides a theoretical contribution to understanding the expressive power of deep neural networks.
Critical strengths
- Rigorous theoretical contributions.
The paper establishes the exact minimum width for universal approximation by deep ReLU networks when k \geq 2d+2, closing an open problem in this parameter regime. The authors also derive a general upper bound for a broad class of activation functions, including nonaffine polynomial activations. These results extend existing universal approximation theory and provide new insights into the expressive power of narrow neural networks.
- Novel geometric approach and formal verification.
The paper develops a geometric approach based on diffeomorphism approximation and the distinction between full-dimensional and lower-dimensional domains. This framework explains when an additional neuron is necessary and provides a systematic method for establishing minimum-width results. Furthermore, the mathematical results are formalized in Lean 4, strengthening confidence in the rigor and reliability of the theoretical contributions.
Critical weaknesses
- Insufficient discussion of related work and originality.
The argument used in Proposition 23 appears closely related to ideas developed in the earlier paper “A Global Universality of Two-Layer Neural Networks with ReLU Activations.” However, this work is not cited or discussed. The authors should clarify the relationship between these results and explain which aspects of their approach are genuinely new. A more careful comparison with existing approximation-theoretic results is important for assessing the originality of the paper.
- Limited implications for practical neural network architectures.
Although the paper establishes exact minimum-width results for universal approximation, the analysis allows arbitrary network depth and does not provide quantitative estimates on the depth or number of parameters required to achieve a prescribed approximation accuracy. Consequently, it remains unclear whether the improvement of the minimum width by one neuron leads to meaningful gains in parameter efficiency or practical network design. This limits the practical significance of the theoretical findings.
Questions for authors
- Relationship to existing diffeomorphism approximation results.
The proof techniques appear closely related to those developed by Teshima et al. (NeurIPS 2020), particularly the decomposition of general diffeomorphisms into compositions of affine maps and single-coordinate transformations. Although this result is cited and used in the paper, could the authors clarify which parts of the proposed approximation framework are fundamentally new and which follow from existing results? In particular, how does the present approach extend the theoretical framework of Teshima et al.?
- Significance of the minimum-width improvement.
The main result improves the minimum-width upper bound from k+1 to k for k\geq 2d+2. Could the authors clarify the broader theoretical significance of this improvement? In particular, does the proposed construction provide any insight into the depth or parameter complexity required to achieve a prescribed approximation accuracy?
6 comments
Response to reviewer Yoer (2/2)
3. Sharpness of the width bound and depth complexity.
Determining sharp width bounds is of considerable theoretical interest in its own right: it identifies the minimum width needed for universal approximation, regardless of how much depth is available. For , the previous bounds were . Since width is integer-valued, removing one neuron closes the entire remaining gap between the necessary and sufficient widths. Theorem 9 establishes throughout this range.
The known lower bound is independent of the activation: an affine output from fewer than hidden coordinates cannot approximate a target taking affinely independent values, regardless of depth. At width , our theorem guarantees approximation of every continuous target to arbitrary accuracy. It therefore identifies the exact threshold at which universality becomes possible. Corollary 10 attains the same threshold for GELU, SiLU, Softplus, and the other ReLU-emulating activations covered by the paper. No smaller width can be universal, even with a different activation or greater depth.
Depth and parameter complexity concern the cost of achieving a given accuracy once universality is possible. We do not claim parameter savings or training guarantees at fixed accuracy. The construction does identify what a quantitative depth analysis must control. If is the error after factor , the proof of Theorem 8 gives
where is the graph-approximation error, is the error from changing direction, and is a modulus of continuity of the exact factor on a suitable compact neighborhood. This estimate lets us assign an error budget to each stage. Converting that budget into a depth bound would require bounding the number of factors and the number of max-min updates needed to approximate each graph height. Those quantities depend on the chosen embedding, its extension, and the regularity of the inverse projections. We have not derived such rates for specified regularity classes, and Section 6 states this limitation. The exact minimum-width result holds independently of those quantitative costs.
Thank you for the clarification. Could the proof of the sharp width bound extend from an input cube to a compact smooth manifold embedded in Euclidean space? If the argument does not carry over, which step presents the main obstruction?
Response to reviewer Yoer (1/2)
Thank you for recognizing the theoretical contributions and the geometric approach. We have clarified the relation to prior work and the significance of the sharp width threshold. Our main result determines the smallest possible hidden width for universality in an infinite family of input-output dimensions.
1. Proposition 23 and the work of Hatano et al.
Thank you for bringing this work to our attention. Appendix F now cites Hatano, Ikeda, Ishikawa, and Sawano, “A Global Universality of Two-Layer Neural Networks with ReLU Activations”. Their Theorem 1.1 proves density of scalar two-layer ReLU networks with unrestricted width in the norm supx∣f(x)∣/(1+∣x∣) on the continuous functions for which f(x)/(1+∣x∣) has finite limits at both ends of R. Their proof uses shifted ReLUs to construct piecewise-linear functions. We now explicitly credit this standard ingredient in Proposition 23.
Proposition 23 combines an exact representation with a matching approximation lower bound for the vector-valued curve
\operatorname{ReLU}(t-2)\bigr),\qquad t\in[0,3].$$ Three hidden neurons represent this curve exactly. Its values at $0,1,2,3$ are affinely independent, whereas every network with last hidden width at most two has its image in an affine plane. Affine independence persists under sufficiently small perturbations, so even arbitrary depth and a varying output plane cannot produce arbitrarily accurate width-two approximants. This establishes exact approximation width three for the target; the unrestricted-width scalar density theorem does not address that lower bound. Appendix F presents Proposition 23 as an illustrative exact-width example, and the main theorems are proved independently of it. Proposition 24 then gives a different construction showing that even a robustly nonprojectable arc can have exact width three. **2. Contributions beyond the diffeomorphism decomposition.** Teshima et al. provide the decomposition into affine maps and single-coordinate diffeomorphisms, and we build on the projected-embedding framework of Li et al. and Hwang. Our contribution is to control the hidden width of ordinary fully connected networks implementing this framework. The decomposition alone does not establish the width-$r$ approximation theorem on the embedded input cube. For general activations, Theorem 1 implements the single-coordinate updates using $r$ state coordinates and one reusable computational neuron. Iterated ridge functions cover nonaffine polynomial activations, and replacing the identity coordinates by rescaled copies of $\sigma$ requires differentiability with nonzero derivative at only one point. This gives $W_\sigma(d,k)\leq w(d,k)+1$, reducing the two-neuron overhead in Hwang's general-activation bound under weaker assumptions. The introduction distinguishes this result from the earlier one-neuron bound for nonpolynomial activations of class $C^{1,1}$. For ReLU, the central new step is the combination of Lemmas 6 and 7 in Theorem 8. At each stage, the actual image of the network constructed so far lies in finitely many affine subspaces of dimension at most $d$. When $r\geq2d+2$, a direction with injective projection can be chosen arbitrarily close to the coordinate direction of the next factor. The image can then be represented as a graph over $r-1$ coordinates, and a width-$r$ block updates its height. Tracking the actual approximating image at every stage makes this step repeatable without adding a computational neuron. Theorem 3 supplies the complementary obstruction: a diffeomorphism of $\mathbb R^r$ that is nonaffine on a full-dimensional convex region cannot be approximated there by width-$r$ ReLU networks. Together with Theorem 1, this makes the width $r+1$ sharp for $C^2$ diffeomorphisms in that setting. Theorems 3 and 8 thus explain when the extra neuron is necessary and when the geometry of the approximation set allows it to be removed. The introduction and Section 5 now make these contributions explicit. Appendix H also supplies a self-contained proof of the precise compact-set factorization used in the argument.