acceptodds
Under review as a conference paper at ICLR 2027

On the Exact Minimum Width for Universal Approximation with Deep ReLU Networks

Abstract

How narrow can a deep network be while still approximating every continuous map from to ? For ReLU networks, the exact minimum width has been known only in a few cases. We prove that it is exactly whenever , improving the previous upper bound by one, and show that the same holds for GELU, SiLU, Softplus, and other activations that approximate ReLU. Our proof builds on a recent diffeomorphism approach that separates the minimum width into a geometric quantity and the additional width needed to approximate diffeomorphisms. We show that one extra neuron suffices for every continuous nonaffine activation with a nonzero derivative at some point, giving the general upper bound . For ReLU, this extra neuron is necessary when approximating diffeomorphisms on full-dimensional regions, but universal approximation only requires approximation on the lower-dimensional image of . We exploit this distinction to remove the extra neuron when , where . For , we construct embeddings for which the geometric argument fails even after small perturbations. More generally, for all , the minimum width is either or , and we conjecture that it is always .

Primary area:
learning theory
Keywords:
deep neural networks, universal approximation, minimum width, ReLU networks, approximation theory

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_YoerOpenReview ↗
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
  1. 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.

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

  1. 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
  1. 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.?

  1. 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
AuthorsOpenReview ↗

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 sup⁡x∣f(x)∣/(1+∣x∣)\sup_x |f(x)|/(1+|x|) on the continuous functions for which f(x)/(1+∣x∣)f(x)/(1+|x|) has finite limits at both ends of R\mathbb 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.
AuthorsOpenReview ↗

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 k≥2d+2k\geq2d+2, the previous bounds were k≤WReLU(d,k)≤k+1k\leq W_{\mathrm{ReLU}}(d,k)\leq k+1. Since width is integer-valued, removing one neuron closes the entire remaining gap between the necessary and sufficient widths. Theorem 9 establishes WReLU(d,k)=kW_{\mathrm{ReLU}}(d,k)=k throughout this range.

The known lower bound kk is independent of the activation: an affine output from fewer than kk hidden coordinates cannot approximate a target taking k+1k+1 affinely independent values, regardless of depth. At width kk, 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 eje_j is the error after factor jj, the proof of Theorem 8 gives

ej≤aj+bj+ωj(ej−1),e_j\leq a_j+b_j+\omega_j(e_{j-1}),

where aja_j is the graph-approximation error, bjb_j is the error from changing direction, and ωj\omega_j 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?

Reviewer_pMZ4OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the minimum width Wσ(d,k)W_\sigma(d,k) for deep networks of arbitrary depth to universally approximate continuous maps [0,1]d→Rk[0,1]^d \to \mathbb{R}^k. Building on the diffeomorphism framework, it proves three main results: (i) for any continuous nonaffine activation differentiable with nonzero derivative at one point, width r+1r+1 approximates every C2C^2 diffeomorphism of Rr\mathbb{R}^r, giving Wσ(d,k)≤w(d,k)+1W_\sigma(d,k) \le w(d,k)+1; (ii) ReLU networks of width rr converging on a full-dimensional convex region must be affine there, so the extra neuron is necessary on such regions; (iii) on the embedded dd-dimensional cube the extra neuron is unnecessary when r≥2d+2r \ge 2d+2, yielding the exact value WReLU(d,k)=kW_{\mathrm{ReLU}}(d,k) = k for k≥2d+2k \ge 2d+2, which transfers to GELU, SiLU, and other ReLU-emulating activations.

Critical strengths
  • Solid, exact result on a long-standing question. The paper closes an infinite family of minimum-width problems (k≥2d+2k \ge 2d+2) with matching upper and lower bounds, improving the previous bound by exactly the one open neuron. Minimum width is a fundamental expressivity question in machine learning theory, and exact values are rare.
  • Clean conceptual dichotomy. The separation between approximation on full-dimensional regions (where ReLU provably needs the extra neuron, Theorem 3) and on the embedded dd-dimensional cube (where it does not, for r≥2d+2r \ge 2d+2) is genuinely illuminating and explains why previous bounds carried the +1+1.
  • Rigor and reproducibility. Full proof with external results as explicit hypotheses is an unusually strong verification standard; the paper is also well organized and easy to follow, with helpful figures and Table 1.
Critical weaknesses

In my opinion, the paper has no major weaknesses. Some minor points:

  • The results are purely expressivity statements: no depth/parameter rates, as the authors acknowledge. The practical relevance to deployed networks is indirect.
  • The headline exact value applies only when k≥2d+2k \ge 2d+2, i.e., output dimension more than twice the input dimension, which is an unusual regime in practice; the practically common regimes (k≤2dk \le 2d) remain open.
  • The main construction leans heavily on strong external theorems (Teshima et al. factorization, Palais extension, Hirsch density); the paper's novelty is in their combination plus the good-direction/graph-update argument, which should be stated even more prominently as the key new ingredient.
Questions for authors
  • Your lower bound w(d,k)≤Wσ(d,k)w(d,k) \le W_\sigma(d,k) (Proposition 12) requires σ\sigma to be a limit of smooth increasing functions. For nonmonotone activations such as GELU or SiLU, is anything better than max⁡{d,k}\max\{d,k\} known or plausible? Could GELU's nonmonotonicity actually reduce the minimum width below w(d,k)w(d,k) at some (d,k)(d,k)?
1 comment
AuthorsOpenReview ↗

Response to reviewer pMZ4

Thank you for your positive assessment and for raising the distinction between monotone and nonmonotone activations. The revised paper makes the scope of the lower bound, the main contribution, and the limitations explicit.

1. Lower bounds for GELU and SiLU.

Proposition 12 does not apply to GELU or SiLU. A limit of increasing functions on every compact interval is nondecreasing, whereas both activations are nonmonotone. In the proof of Proposition 12, the increasing smooth approximants make the lifted hidden maps injective immersions. That step is unavailable for a nonmonotone activation.

For σ∈{GELU,SiLU}\sigma\in\{\mathrm{GELU},\mathrm{SiLU}\}, the bounds established by the arguments in this paper are

\leq W_{\mathrm{ReLU}}(d,k) \leq\min\{d+k,w(d,k)+1\}.$$ The first inequality follows from the input and output affine bottlenecks and does not require monotonicity. The second follows from ReLU emulation. This transfer is one-sided: reproducing ReLU networks with $\sigma$ networks does not transfer a lower bound for ReLU to $\sigma$. The lower bounds for continuous monotone activations in Kim et al. and Rochau et al. do not resolve this question. Kim et al.'s $L^p$ theorem also covers GELU and SiLU when $d+k\geq3$, but the resulting lower bound is then just $\max\{d,k\}$; it gives no improvement over the bottleneck bound for our uniform problem. Appendix A now distinguishes these activation and norm assumptions. See [Kim et al., Theorems 2 and 3](https://arxiv.org/pdf/2309.10402). For $k\geq2d+2$, Corollary 10 gives the matching upper bound $k$, so $$W_\sigma(d,k)=w(d,k)=k.$$ Thus nonmonotonicity cannot reduce the width below $w(d,k)$ in this regime. Elsewhere, our results do not establish $W_\sigma(d,k)\geq w(d,k)$. A concrete unresolved comparison in our framework is $(d,k)=(1,2)$: $w(1,2)=W_{\mathrm{ReLU}}(1,2)=3$, while the bounds above give $$2\leq W_\sigma(1,2)\leq3.$$ Nonmonotonicity permits folding and removes the injectivity argument used for the geometric lower bound. It therefore leaves open the possibility of a smaller width. We do not have a construction proving such a reduction for GELU or SiLU, or a lower bound excluding it. Appendix A and Section 6 now state this as an open question. The conjecture remains specifically about ReLU. **2. Scope, practical relevance, and the new geometric ingredient.** We agree that $k\geq2d+2$ is a restricted dimension regime and that our result gives no depth or parameter bounds or training guarantees. The introduction states the dimension threshold, and Section 6 explains these limitations. The theorem determines the smallest hidden width compatible with universality in that regime; it does not establish parameter efficiency for deployed architectures. The broader range is only partially understood for ReLU: some cases, including scalar outputs, are already settled, while many vector-output cases and $k=2d+1$ remain open. The introduction and the opening of Section 5 now highlight the new step. The construction chooses a good direction for the actual image of the network built so far, implements the next graph update at width $r$, and uses preservation of finite affine coverings to repeat the argument. The published embedding, extension, and factorization results supply the geometric framework. The graph-update construction and the choice of directions at successive network images are what remove the extra neuron.
Reviewer_N21xOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the minimum width for uniform universal approximation of continuous functions from [0,1]d[0,1]^d to Rk\mathbb R^k. Its main results is WReLU(d,k)=kW_{\mathrm{ReLU}}(d,k)=k for k≥2d+2k \ge 2d+2 for ReLU networks, which improves the previous upper bound by one neuron. To achieve this, the proof chooses a good direction for the current network image at each step. The paper also studies approximation of diffeomorphisms and extends the width result to activations that emulate ReLU.

Critical strengths
  1. Although the improvement is only one neuron, the central question is whether that neuron is necessary. Showing that the output dimension alone is sufficient when k≥2d+2k\ge 2d+2 is a meaningful contribution and the main reason for my positive recommendation.

  2. I find the choice of a good direction for the actual network image useful. The proof tracks the image produced by the approximation built so far and uses its finite affine covering to find a direction along which points do not overlap. This explains how the network can perform the next update without increasing its width.

Critical weaknesses

Assuming Theorem 4 of Teshima et al. (2020) is correct, the arguments in this paper appear sound to me. However, the blueprint (in the supplementary material) identifies issues with intermediate statements in the cited proof while maintaining that the theorem itself remains valid. It refers to an independent argument in a Markdown file (discovery/2026-09-13-cited-hypotheses-audit.md), but I could not find this file in the submitted supplementary material. Since this factorization supports Theorems 1 and 8, and consequently Theorem 9, the absence of the referenced argument makes it difficult to assess how the issues identified in the blueprint are resolved.

Questions for authors
  1. Please identify the intermediate statements in the cited proof that require correction and include the independent argument referenced in the blueprint. In particular, please show that the corrected argument establishes the precise factorization used here, with the required assumptions and regularity on the prescribed compact set. A brief explanation in the manuscript would also help readers understand why these corrections do not affect the results of this paper.

  2. The related-work discussion appears to understate the scope of Kim et al. (2024) by describing their result as a ReLU lower bound in the comparison with Rochau et al. (2025). Kim et al. (Theorem 3) already cover any fixed continuous monotone activation when (d<k\le 2d). In this regime, Rochau et al. (Theorem 47 and Remark 48) extend the result to networks using arbitrary combinations of continuous monotone activations. Please revise this comparison and check the other related-work descriptions for similar inaccuracies concerning activation assumptions and the scope of the cited results.

2 comments
AuthorsOpenReview ↗

Response to reviewer N21x

Thank you for your overall positive assessment of our work. We also appreciate your pointing out the missing argument and the inaccurate description of Kim et al.'s result, and agree that the factorization used by our proofs must be justified in the material available to reviewers.

1. Missing factorization argument and the statements requiring correction.

The submitted blueprint referred to an internal audit that was not available in the supplementary archive. We apologize for this oversight. Appendix H, Proposition 26, now gives a self-contained proof, also included in Section 22 of the revised blueprint. The supplementary material now includes the full proof and the Lean code.

The issues concern two steps in the proof of Theorem 4 in Teshima et al. (2020). First, Appendix C identifies the full group of compactly supported diffeomorphisms with its identity component. This identification is not valid in general. Consequently, Lemma 12 (also stated as Lemma 2), Corollary 1, and Theorem 5 cannot be used with their stated scope over the entire group; the argument concerns maps in the identity component. Second, the cutoff vector field in Lemma 7 is only guaranteed to be spatially C1C^1 under the stated C2C^2 hypothesis on the original map, so the flow argument does not by itself establish the claimed C2C^2 regularity of the extension. Teshima et al.'s Theorem 4 also assumes ambient dimension at least two; our one-dimensional case is treated separately in Appendix B.

The precise statement needed here is the following:

Let r≥1r\geq1, let D:Rr→RrD:\mathbb R^r\to\mathbb R^r be a C2C^2 diffeomorphism, and let K⊂RrK\subset\mathbb R^r be compact. On KK, DD agrees exactly with a finite composition of invertible affine maps and compactly supported C2C^2 single-coordinate diffeomorphisms. After permuting coordinates, each nonlinear factor has the form T(x,y)=(x,τ(x,y))T(x,y)=(x,\tau(x,y)), with ∂yτ>0\partial_y\tau>0 and τ(x,⋅)\tau(x,\cdot) a bijection of R\mathbb R for every xx.

The independent proof now provided in Appendix H avoids both issues and establishes the factorization used by Theorems 1 and 8, and hence Theorem 9.

We have also formalized the C2C^2 compact-set factorization, including compact support, C2C^2 inverses, and positive active-coordinate derivatives. The new theorem compact_factorization discharges the former TeshimaFactorization and ShearFactorization hypotheses; Theorems 1, 8, and 9 therefore no longer rely on an assumed factorization. The other cited results remain explicit hypotheses. The blueprint states the verification scope and explains the correspondence between the written and formal proofs.

2. Scope of Kim et al. and Rochau et al.

You are correct. Kim et al. (2024, Theorem 3) already establish Wσ(d,k)≥k+1W_\sigma(d,k)\geq k+1 for d<k≤2dd<k\leq2d for any fixed continuous monotone activation. Their stated hypothesis is uniform approximability by continuous injections. Rochau et al. (2025, Theorem 47 and Remark 48) allow arbitrary combinations of continuous monotone activations and give the lower bound max⁡{d,k}+1\max\{d,k\}+1 for k≤2dk\leq2d. Section 1 now states this comparison with the exact theorem references.

We have also checked the activation and approximation assumptions in the related-work discussion. In particular, Section 1 now specifies the fixed Leaky-ReLU slope range (0,1)∪(1,∞)(0,1)\cup(1,\infty). In Section 5, the previous upper bound k+1k+1 is stated specifically for GELU, SiLU, and Softplus. The fixed ELU/SELU cases covered by Remark 21 are stated separately, with their parameter ranges.

Thank you for the clarification. I will maintain my original score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank all the reviewers for their careful reading and constructive comments. We have revised the manuscript, with changes highlighted in blue, and updated the supplement. Appendix H now provides a self-contained proof of the factorization used in our main results, and the Lean formalization and accompanying blueprint have been updated accordingly. We have also clarified the relationship to prior work and the theoretical significance of the sharp width bounds. We address each reviewer's questions in the corresponding review thread.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.