Source-linked AI summary
Universal Approximation with Deep Narrow Networks
Patrick Kidger, Terry Lyons
TL;DR
The paper studies universal approximation by deep, narrow networks, including which activation functions, topologies, and widths permit density. It develops constructive results for general activations and extensions, including nowhere-differentiable functions, Lp approximation, multiple outputs, and width n + m + 1 for most activations.
Problem
Deep, narrow networks raise questions about admissible activation functions, density topologies, and how narrowly the width can be constrained.
Method
The paper uses constructive register-based network constructions with input-register, output-register, and computation neurons in each hidden layer.
Results
The results establish universal approximation for general activation functions, including nowhere-differentiable cases, and show that width n + m + 1 suffices for most activation functions and multiple outputs.
Takeaways & Limitations
The techniques extend deep narrow universal approximation beyond ReLU to pathological activations, multiple outputs, and Lp approximation with p ≥ 1.
Takeaways & Limitations
The paper does not present depth-efficient versions of its constructive approximations because tracking depth against approximation error becomes unclear and requires tracing several underlying proofs.
Abstract
from arXiv · showhide
The classical Universal Approximation Theorem holds for neural networks of arbitrary width and bounded depth. Here we consider the natural `dual' scenario for networks of bounded width and arbitrary depth. Precisely, let $n$ be the number of inputs neurons, $m$ be the number of output neurons, and let $ρ$ be any nonaffine continuous function, with a continuous nonzero derivative at some point. Then we show that the class of neural networks of arbitrary depth, width $n + m + 2$, and activation function $ρ$, is dense in $C(K; \mathbb{R}^m)$ for $K \subseteq \mathbb{R}^n$ with $K$ compact. This covers every activation function possible to use in practice, and also includes polynomial activation functions, which is unlike the classical version of the theorem, and provides a qualitative difference between deep narrow networks and shallow wide networks. We then consider several extensions of this result. In particular we consider nowhere differentiable activation functions, density in noncompact domains with respect to the $L^p$-norm, and how the width may be reduced to just $n + m + 1$ for `most' activation functions.
1. Introduction
The paper contrasts classical shallow-wide approximation with the dual problem of bounded-width, arbitrary-depth networks. It aims to extend density results beyond ReLU to essentially arbitrary activation functions, including polynomials.
- Classical universal approximation uses arbitrary width and bounded depth, with density characterized by nonpolynomial activation functions.
- Deep narrow networks instead have bounded width and arbitrary depth, raising questions about admissible activations, density topologies, and minimum width.
- Prior deep-narrow results mainly studied ReLU because its explicit form and algebraic properties simplify the analysis.
- The article addresses this limitation by considering essentially arbitrary activation functions, including polynomial activations.
- The authors emphasize that deep narrow and shallow wide networks behave distinctly differently.
2. Existing work
Existing work established positive and negative width results largely for ReLU networks, while broader activation-function and Lp approximation cases remained open.
- ReLU deep narrow networks were shown dense in C(K; R^m) at width n + m and in L1(R^n) at width n + 4.
- Previous work also established density for particular ReLU residual-network descriptions in L1(R^n).
- No previously obtained positive results were known for non-ReLU activations or the general Lp(R^n; R^m) case with p ∈ [1, ∞) and multiple outputs.
- For some settings, width n was insufficient for density, while ReLU results also identified insufficiency at width n − 1 on L1([-1, 1]^n).
- Related research also considered classification tasks and distributions on finite discrete domains.
3. Summary of Results
The paper proves universal approximation for broad activation classes with narrow, arbitrarily deep networks and develops extensions to pathological activations, noncompact domains, and smaller widths.
- Main result: Theorem 3.2 establishes density in C(K; R^m) for compact K using width n + m + 2 and any nonaffine continuous activation with a nonzero derivative at some point.
- Main result: The proof treats particular activation classes as special cases rather than relying on ReLU’s explicit form or algebraic properties.
- Polynomial activations: Polynomial activations are included: nonaffine polynomials yield density at width n + m + 2.
- Pathological activations: A bounded continuous nowhere differentiable construction, ρ(x) = sin(x) + w(x)e^-x, also achieves density at width n + m + 1.
- Noncompact domains: For ReLU, width n + m + 1 is dense in Lp(R^n; R^m) for every p ∈ [1, ∞), extending earlier results to narrower width, multiple outputs, and general p.
- Reduced width: Width n + m + 1 suffices for a large class of polynomials and therefore for ‘most’ activation functions.
- Proof scope: The constructive proofs could in principle determine depth as a function of approximation error, but the paper does not present those depth-efficient versions.
4. Universal approximation
The paper constructs deep, narrow networks by preserving inputs through approximate identity neurons and using compact register-based computations. It proves uniform universal approximation for width n+m+2 under broad activation assumptions, with width n+m+1 for several important classes and extensions.
- Preliminaries: Enhanced neurons allow affine pre- and post-processing around the activation without increasing representational power.These affine transformations can be absorbed into adjacent layers.
- Preliminaries: A continuously differentiable activation with a nonzero derivative at one point can uniformly approximate the identity on any compact interval.The approximation ι_h converges uniformly to the identity as h approaches zero.
- Register Model: The Register Model stores inputs and outputs across layers, and for any continuous nonpolynomial activation it is dense in C(K; R^m) with width n+m+1.Its hidden layers use n+m identity neurons and one neuron with activation ρ.
- Square Model: With square activation, two enhanced neurons exactly compute multiplication, enabling multi-layer approximation of polynomial functions.The construction uses (x+y)^2 and (x−y)^2, whose affine difference equals 4xy.
- Square Model: The Square Model is dense in C(K; R^m) at width n+m+1 by preserving input registers while sequentially computing and storing polynomial intermediates.Stone–Weierstrass supplies polynomial approximants, and the constructed network achieves total error at most ε.
5. Conclusion
The paper develops universal approximation results for general activation functions, extending deep narrow network theory beyond ReLU and to multiple outputs and broader norms. Its techniques also cover nowhere-differentiable activations and support conclusions about network width.
- Activation-function selection remains poorly understood despite a broad range of proposed alternatives beyond ReLU.
- The central contribution establishes universal approximation results for general activation functions without relying on ReLU’s explicit form or algebraic properties.The techniques also handle nowhere-differentiable activation functions.
- The results extend previous work to smaller widths, multiple output neurons, and Lp approximation for p ≥ 1 instead of only p = 1.
- Every result shown handles the general case of multiple output neurons, unlike much previous work.
Appendix A. Proof of the Register Model (Proposition 4.2)
The Register Model reorganizes shallow approximating networks into a deep network that preserves inputs, computes hidden-neuron operations sequentially, and accumulates multiple outputs. With width n + m + 1, this construction is dense in C(K; R^m) for continuous nonpolynomial activations.
- Classical approximation: The classical theorem provides shallow networks with arbitrary width that uniformly approximate each component of a continuous vector-valued function on compact K.Each component network g_i approximates f_i within ε under the sup norm.
- Register Model: The Register Model reorganizes neurons from multiple shallow networks into a deep network with width n + m + 1.
- Result: For any continuous nonpolynomial activation, the resulting network class is dense in C(K; R^m).
- Register Model: In-register neurons preserve the n inputs across layers, allowing computation neurons to evaluate the shallow networks’ hidden-neuron operations sequentially.
- Register Model: Out-register neurons use affine parts to accumulate the results associated with each output component across layers.
- Register Model: Figure 2 groups layers so the ith group computes σi,1 through σi,βi while the network receives inputs x1 through xn.
Appendix B. Proof of Theorem 4.16
The proof extends the deep narrow approximation construction to Lp(R^n; R^m) for ReLU networks by localizing approximations with a compactly supported gate. The gate is built from coordinatewise piecewise-affine functions and iterated minima, while the final network clips and combines the shallow approximation.
- Gate construction: Two ReLU layers of two enhanced neurons can exactly represent the coordinatewise gate U_a,b,c,d, and one layer can exactly represent min{x, y} on [0, ∞)^2.
- Theorem 4.16: Theorem 4.16 states that ReLU networks of width n + m + 1 are dense in Lp(R^n; R^m) for every p ∈ [1, ∞).
- Localization: The proof first approximates an Lp function by a compactly supported continuous function and chooses a rectangle J containing its support.
- Output modification: The modified outputs G_i = min{max{g_i, cU}, CU} retain g_i on J, vanish outside K, and transition through K \ J.
- Gate construction: Taking the minimum of coordinatewise gates constructs U, an approximation to the indicator of J supported in K.
- Boundary behavior: The construction tolerates the in-register approximation that records −N for inputs below −N because the corresponding gate value is already zero.
Appendix C. Proof of Proposition 4.17
The proof transfers square-activation approximation to a polynomial activation by rescaling it near a point where its first derivative vanishes and its second derivative is nonzero. Uniform convergence on compact sets and affine absorption then recover the result for the original activation.
- For a polynomial ρ with ρ′(α) = 0 and ρ′′(α) ≠ 0, width n + m + 1 networks are dense in C(K; R^m).
- The rescaled activation ρ_h converges uniformly on compact sets to the square function s(x) = x^2 as h approaches zero.
- Replacing every square activation in a Square Model network with ρ_h produces a network whose output remains arbitrarily close on K for sufficiently small h.
- Because ρ_h differs from ρ only by affine pre- and post-compositions, networks using ρ_h can be represented exactly using ρ.