Source-linked AI summary
Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations
Boris Hanin
TL;DR
The paper asks how much width and depth ReLU networks need to approximate continuous functions on [0,1]^d, particularly near the minimal width. It uses piecewise-affine representation and the convexity of ReLU to study convex approximation, proving width d + 1 suffices for continuous convex functions and deriving depth estimates with width d + 3.
Problem
The paper asks whether the width bound for universal approximation is sharp and how efficiently ReLU networks of a given width approximate continuous functions.
Method
The paper combines exact ReLU representations of piecewise-affine functions with convex-function discretization and exploits ReLU activation convexity.
Results
Width d + 1 ReLU networks approximate any continuous convex function on [0,1]^d arbitrarily well, while width d + 3 yields quantitative depth estimates for arbitrary continuous functions.
Takeaways & Limitations
Convexity makes ReLU networks well-adapted to convex-function representation, enabling sharp width results and quantitative depth analysis near minimal width.
Takeaways & Limitations
For general continuous functions, the paper does not obtain quantitative depth estimates at width d + 2; such estimates are available there when f is sufficiently smooth.
Abstract
from arXiv · showhide
This article concerns the expressive power of depth in neural nets with ReLU activations and bounded width. We are particularly interested in the following questions: what is the minimal width $w_{\text{min}}(d)$ so that ReLU nets of width $w_{\text{min}}(d)$ (and arbitrary depth) can approximate any continuous function on the unit cube $[0,1]^d$ aribitrarily well? For ReLU nets near this minimal width, what can one say about the depth necessary to approximate a given function? Our approach to this paper is based on the observation that, due to the convexity of the ReLU activation, ReLU nets are particularly well-suited for representing convex functions. In particular, we prove that ReLU nets with width $d+1$ can approximate any continuous convex function of $d$ variables arbitrarily well. These results then give quantitative depth estimates for the rate of approximation of any continuous scalar function on the $d$-dimensional cube $[0,1]^d$ by ReLU nets with width $d+3.$
1. Introduction
The paper studies how width and depth determine ReLU-network expressivity, emphasizing convex functions as a setting where ReLU structure is especially effective. It proves width-related approximation results and develops depth bounds for representing or approximating functions.
- Width bounds: ωmin(d) ≤ d + 2 is proved, while the authors state forthcoming work will establish ωmin(d) = d + 1.The equality is attributed to forthcoming work rather than proved in this article.
- Research questions: The paper frames ReLU expressivity through two questions: whether the width upper bound is sharp and how efficiently a fixed-width network approximates continuous functions.These questions concern minimal width and the depth needed at or near that width.
- Convex approximation: ReLU nets of width w can approximate any positive convex function on [0,1]^d arbitrarily well.The paper attributes this suitability to the convexity of the ReLU activation.
- Representation method: Every piecewise affine function on [0,1]^d can be exactly represented with hidden-layer width at most d + 3, with depth bounded by its number of affine pieces.This representation result is used in the proof strategy for convex-function approximation.
- Convex representation: Every convex piecewise affine function with N pieces can be represented exactly by a ReLU net with width d + 1 and depth N.This gives a concrete width-depth characterization for an important class of convex functions.
2. Statement of Results
The results establish bounded-width ReLU approximation and exact-representation guarantees, with especially strong width and depth statements for convex functions.
- Continuous functions: w_min(d) ≤ d + 2 for approximating arbitrary continuous functions with bounded-width ReLU nets.The paper also gives width d + 3 nets achieving prescribed precision with quantitative depth estimates.
- Depth estimates: Width d + 3 ReLU nets provide quantitative depth estimates for approximating arbitrary continuous functions to precision ε.The estimates are expressed using the modulus of continuity of the target function.
- Convex functions: d + 1 hidden-layer width suffices to approximate every positive continuous convex function arbitrarily well.The approximating sequence converges uniformly in the C^0 norm.
- Scope of depth estimates: Quantitative depth estimates are unavailable here for fixed continuous functions using width d + 2, except for sufficiently smooth functions.Increasing width to d + 3 yields estimates for general continuous functions, while smooth functions admit estimates at width d + 2.
- Exact representation: Every piecewise affine function computed by a ReLU net has an exact representation with hidden width at most d + 3.The construction represents the function as a difference of positive convex functions.
- Exact representation: Convex piecewise affine functions with N affine pieces are represented exactly using width d + 1 and depth N.This gives a direct complexity-dependent depth bound for convex functions.
3. Relation to Previous Work
The paper places its results alongside shallow universal approximation, depth-based expressivity, and prior bounds for piecewise-linear functions, hierarchical functions, and network size. Its Theorems 1–2 provide quantitative deep-and-narrow analogs with explicit width control.
- Shallow and wide approximation: Single-hidden-layer networks universally approximate scalar functions with arbitrary width, motivating the paper’s deep-and-narrow setting.These classical results apply to a wide class of nonlinear activations but do not clarify expressive advantages of depth.
- Hierarchical functions: Prior work studies depth for hierarchical or compositional functions and gives width bounds for shallow and certain deep networks.These results consider both ReLU and non-ReLU activations.
- Piecewise-linear functions: Earlier ReLU results bound depth for exact piecewise-linear computation but generally do not control hidden-layer width as a function only of input dimension.The present results are described as quantitative analogs of those bounds.
- Network size: Other cited work gives lower bounds on total network size for approximating sparse multivariable polynomials, without width bounds depending only on the number of variables.Related work also bounds total parameters for approximation classes such as Sobolev balls.
- Depth and width: Theorems 1–2 quantify expressive power from depth while controlling hidden-layer width.The paper characterizes deep-and-narrow analogs of shallow universal approximation results.
5. Proof of Theorem 2
The proof represents convex functions by iteratively updating graph representations with affine transformations and ReLU operations. General piecewise affine functions are handled through differences of positive convex maxima, using a width-d+3 construction.
- Convex case: For convex f, an affine graph transformation followed by ReLU replaces T with x ↦ max{T(x), L(x)}.This operation lets the network build a convex piecewise affine function by successively incorporating affine functions.
- Convex case: A convex piecewise affine function with N affine pieces is computed exactly by a ReLU net of width d+1 and depth N.The construction copies the input, updates the graph through successive layers, and stores the evolving function.
- General case: General piecewise affine functions are expressed as f = g − h, where g and h are maxima of positive affine functions.The maxima are computed successively using a width-2 ReLU maximum module.
- General case: The general construction uses width d to copy inputs, width 2 for successive maxima, and width 1 as memory for the first maximum.A final layer computes the difference, yielding depth 2(M+N) and width d+3.
6. Proof of Theorem 1
The proof approximates continuous functions by piecewise affine functions and then represents those approximations through convex components. Convex functions are first discretized directly, while width-preserving transformations supply additional depth estimates.
- Convex functions: A continuous convex function is uniformly approximated by a piecewise affine convex function, which Theorem 2 represents using width d+1.This establishes arbitrary approximation by width-d+1 ReLU nets.
- Convex functions: A convex Lipschitz function is approximated using k affine maps, with the resulting representation supplying quantitative depth estimates.The argument combines the affine approximation result with Theorem 2.
- Width-depth transformation: A single-hidden-layer ReLU net of width n can be transformed into an equivalent net with n+2 hidden layers of width d+2.The construction copies inputs, computes each hidden-layer affine function sequentially, and stores the output.
- Continuous functions: For a continuous function, a simplex partition with cell diameter ωf(ε) produces a piecewise linear approximation fε.The approximation is then decomposed into positive convex piecewise affine functions and handled by Theorem 2.