Source-linked AI summary
Approximating Continuous Functions by ReLU Nets of Minimal Width
Boris Hanin, Mark Sellke
TL;DR
The paper asks how narrow ReLU networks can be while still approximating arbitrary continuous functions, and develops a width-controlled construction with depth governed by the function’s modulus of continuity. It shows that width d_in + d_out suffices for continuous functions, while width d_in cannot uniformly approximate certain continuous functions.
Problem
The paper studies the minimal hidden-layer width needed for arbitrarily accurate approximation of scalar continuous functions of d variables by arbitrarily deep ReLU networks.
Method
The paper defines ReLU networks through successive affine transformations and constructs approximants using max-min representations, without skip connections.
Results
Width d_in + d_out suffices to approximate any continuous function with d_in inputs and d_out outputs, with depth depending on its modulus of continuity; width d cannot uniformly approximate a certain continuous function.
Takeaways & Limitations
For the considered no-skip ReLU networks, increasing width from d_in to d_in + d_out separates a limited approximation regime from universal approximation.
Takeaways & Limitations
The stated width results concern feed-forward ReLU networks without skip connections; allowing skip connections changes the conclusion, since width-1 networks can approximate any continuous function with sufficient depth.
Abstract
from arXiv · showhide
This article concerns the expressive power of depth in deep feed-forward neural nets with ReLU activations. Specifically, we answer the following question: for a fixed $d_{in}\geq 1,$ what is the minimal width $w$ so that neural nets with ReLU activations, input dimension $d_{in}$, hidden layer widths at most $w,$ and arbitrary depth can approximate any continuous, real-valued function of $d_{in}$ variables arbitrarily well? It turns out that this minimal width is exactly equal to $d_{in}+1.$ That is, if all the hidden layer widths are bounded by $d_{in}$, then even in the infinite depth limit, ReLU nets can only express a very limited class of functions, and, on the other hand, any continuous function on the $d_{in}$-dimensional unit cube can be approximated to arbitrary precision by ReLU nets in which all hidden layers have width exactly $d_{in}+1.$ Our construction in fact shows that any continuous function $f:[0,1]^{d_{in}}\to\mathbb R^{d_{out}}$ can be approximated by a net of width $d_{in}+d_{out}$. We obtain quantitative depth estimates for such an approximation in terms of the modulus of continuity of $f$.
1. Introduction
The paper studies how hidden-layer width controls the expressive power of arbitrarily deep ReLU networks. It identifies a sharp width transition and develops an approximation construction with quantitative depth bounds.
- Motivation: The paper asks why neural networks approximate interesting functions effectively, focusing on the minimal width needed for arbitrary-depth ReLU networks to approximate continuous functions.The question is motivated by neural networks’ empirical successes and the still-developing theory of their approximation and trainability.
- Main result: The main result establishes a sharp transition in representational power as hidden-layer widths vary.The paper formalizes ReLU networks through affine transformations followed by coordinatewise ReLU activations.
- Main result: The quantity wmin(din, dout) is the smallest width allowing every continuous function from [0,1]^din to R^dout to be ε-approximated.The definition permits arbitrary depth while bounding every hidden-layer width by w.
- Upper bound: The upper-bound construction approximates any continuous din-input, dout-output function using width din + dout, with depth depending on its modulus of continuity ωf.The modulus records the input scale δ needed to ensure output variation at most ε uniformly.
- Upper bound: For continuous functions on compact K, the resulting network has input dimension din, hidden-layer width din + dout, output dimension dout, and a depth bound involving diam(K) and ωf.The introduction states this estimate as a quantitative consequence of the construction.
- Lower bound: The lower-bound construction gives a continuous function that width-din ReLU networks cannot uniformly approximate below a positive error threshold.The obstruction is tied to compact level sets that disconnect bounded regions from the infinite component and non-constancy inside such level sets.
- Scope: The analysis excludes skip connections; with skips, width-1 networks can approximate any continuous function at arbitrary depth by converting a shallow network into sequential width-1 layers.Thus the stated width transition applies to feed-forward architectures without residual or other skip connections.
2. Proof of the Upper Bound in Theorem 1
The upper-bound proof approximates continuous functions by max-min strings, then realizes those strings with ReLU nets of hidden width d_in + d_out. The continuous construction extends approximation from small balls to arbitrarily large regions using progressively finer geometric additions controlled by the modulus of continuity.
- Max-min approximation: Proposition 3 reduces uniform approximation of continuous functions to constructing a sufficiently long max-min string.Proposition 2 supplies the corresponding ReLU implementation, while Proposition 3 supplies the approximation string.
- ReLU realization: A ReLU net of hidden width d_in + d_out computes any max-min string of length L with depth L.Affine transformations and ReLU layers update the graph representation of the intermediate max-min function, followed by a final projection to the output coordinates.
- Discrete construction: Finite functions can be represented exactly by max-min strings through induction on the number of sample points and repeated corner cutting of their convex hull.An affine separator isolates an extreme point, and componentwise max/min operations restore its prescribed value without changing the other sample values.
- Continuous construction: Continuous approximation differs because the modulus of continuity permits cutting off only small-diameter pieces at a time.The proof therefore enlarges an initially approximated ball by adding small pieces in all directions while preserving ε-accuracy.
- Continuous construction: Lemma 5 extends an ε-approximation from a ball to a slightly larger region, and repeated rotated configurations eventually make the approximation region arbitrarily large.The radius update is strictly increasing, so iterating it sends every positive starting radius to infinity; the planar argument extends to higher dimensions by rotating the configuration into cones.
- Continuous construction: In two dimensions, applying the extension step around a circumference finitely many times completes the upper-bound construction, while dimensions d_in ≥ 3 require only a minor geometric modification.The modification replaces the triangle by a cone obtained by rotation, after which the rest of the argument carries over.
3. Proof of the Lower Bound in Theorem 1
The lower bound constructs continuous functions that width-d ReLU nets cannot uniformly approximate, using topological constraints on their level sets and affine regions.
- Lower-bound construction: For every d_in ≥ 1, there is a continuous f and η > 0 such that every width-d_in ReLU net remains at least η away from f.The obstruction applies to approximation with input dimension d_in, hidden width d_in, and scalar output.
- Lower-bound construction: The construction applies when a compact connected component of a level set separates a bounded region from infinity.A sphere enclosing a ball is given as an example of this geometry.
- Network geometry: Each intermediate network map has an open convex region where all ReLUs are positive and the map is affine.Every bounded level set is contained in this region.
- Network geometry: Any level set that leaves the all-positive region must be unbounded, a property established inductively across the network layers.The induction uses affine behavior inside the preceding positive region and rays generated when a ReLU output vanishes.
- Contradiction: The contradiction splits into two cases: convexity forces an affine-value constraint if the separating set lies inside the positive region, while otherwise a network level set must intersect the separating component.Thus width-d_in networks cannot uniformly approximate the constructed function.