PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimum Width for Universal Approximation

Sejun Park, Chulhee Yun, Jaeho Lee, Jinwoo Shin

arXiv:2006.08859v1cs.LGstat.ML

TL;DR

The paper addresses the unresolved minimum width for universal approximation in terms of input and output dimensions. It proves exact ReLU results for Lp functions, distinguishes uniform approximation, and extends the approach to threshold-augmented and general activations.

  • Problem

    Prior work provided only separated upper and lower bounds for the minimum width of width-bounded universal approximators, especially when output dimension is high.

  • Method

    The paper develops tight upper-bound proof techniques, including a coding scheme, and analyzes ReLU, ReLU+Step, and general activation networks.

  • Results

    For any p ∈ [1, ∞), ReLU networks are dense in Lp(R^d_x, R^d_y) if and only if width w ≥ max{d_x + 1, d_y}; ReLU alone does not give the same result for uniform approximation.

  • Takeaways & Limitations

    Minimum width depends on both input and output dimensions and on the target function class and activation functions.

  • Takeaways & Limitations

    For uniform approximation, ReLU width max{d_x + 1, d_y} is insufficient in general, including the case d_x = 1 and d_y = 2.

Abstract

from arXiv · show

The universal approximation property of width-bounded networks has been studied as a dual of classical universal approximation results on depth-bounded networks. However, the critical width enabling the universal approximation has not been exactly characterized in terms of the input dimension $d_x$ and the output dimension $d_y$. In this work, we provide the first definitive result in this direction for networks using the ReLU activation functions: The minimum width required for the universal approximation of the $L^p$ functions is exactly $\max\{d_x+1,d_y\}$. We also prove that the same conclusion does not hold for the uniform approximation with ReLU, but does hold with an additional threshold activation function. Our proof technique can be also used to derive a tighter upper bound on the minimum width required for the universal approximation using networks with general activation functions.

1 Introduction

This section frames minimum-width universal approximation as a width-bounded counterpart to classical depth-bounded results and reviews the gap in prior bounds. It then states exact ReLU results for Lp approximation, the failure of the same width for uniform approximation, and extensions to mixed and general activations.

  • Prior work: Width-bounded universal approximation studies whether networks with bounded width and arbitrary depth can approximate broad function classes.This is presented as a dual scenario to classical results using bounded depth and arbitrary width.
  • Prior work: Prior ReLU results left the minimum width between d_x + 1 and d_x + 4 for L1(R^d_x, R), while later bounds remained separated for higher-dimensional outputs.Existing upper bounds could be at least d_x + d_y, whereas lower bounds could be at most d_x + 1.
  • Main results: The paper extends its tight upper-bound proof techniques beyond ReLU to general activation functions covered by prior work.The contribution is stated as an extension of the results to those general activation functions.
  • Main results: Theorem 1 gives the exact ReLU minimum width for Lp(R^d_x, R^d_y) as max{d_x + 1, d_y}.This closes the prior upper- and lower-bound gap and improves on the best known upper bound d_x + d_y + 1.
  • Main results: For uniform approximation, ReLU width max{d_x + 1, d_y} is insufficient in general, with width 3 required for C([0, 1], R^2).The same width characterization therefore does not transfer from Lp approximation to continuous functions on compact domains.
  • Main results: Adding threshold activation functions allows universal approximation of C(K, R^d_y) at width max{d_x + 1, d_y}.The paper calls the threshold activation Step and uses ReLU+Step networks for this result.

2 Problem setup and notation

The paper models fully connected networks as alternating affine transformations and coordinatewise activation functions, and defines width as the largest hidden-layer dimension. Universal approximation is expressed as density in either the uniform or Lp norm.

  • Network model: A network alternates affine transformations with vector-valued activation functions across its layers.Each affine map transforms the representation between successive layer dimensions, while each activation coordinate uses a function from the selected activation set.
  • Width: Network width is the maximum dimension among the hidden layers.The input and output dimensions are not included in this width definition.
  • Approximation criteria: Density in C(X, Y) means approximating every target function within any ε > 0 under the uniform norm.The approximation criterion is expressed as ||f*−f||∞ ≤ ε.
  • Approximation criteria: Density in Lp(X, Y) means approximating every target function within any ε > 0 under the Lp norm.The criterion is ||f*−f||p ≤ ε for the specified p.

3 Minimum width for universal approximation

The paper exactly characterizes the minimum width for Lp universal approximation with ReLU as max{dx + 1, dy}, while uniform approximation can require greater width. Adding Step activation restores the same minimum width for continuous functions, and general activations receive a tighter upper bound.

  • Lp approximation with ReLU: For any p ∈[1, ∞), ReLU networks are dense in Lp(Rdx, Rdy) if and only if their width is at least max{dx + 1, dy}.Thus the minimum width is exactly wmin = max{dx + 1, dy}.
  • Lp approximation with ReLU: The tight ReLU width follows from an upper bound max{dx + 1, dy} and lower bounds dx + 1 and dy.The upper bound uses a coding construction, while the lower bounds come from an extension of prior arguments and a volumetric argument.
  • Uniform approximation with ReLU: For uniform approximation, width max{dx + 1, dy} is insufficient in general; specifically, ReLU networks on C([0, 1], R2) require width at least 3.The paper proves that width 2 is not sufficient when dx = 1 and dy = 2.
  • Uniform approximation with ReLU+Step: ReLU+Step networks are dense in C(K, Rdy) exactly when their width is at least max{dx + 1, dy}.The Step activation enables exact input quantization in the encoder without uniform norm errors.
  • Activation dependence: The minimum width depends on the activation choice, unlike the classical minimum-depth result where ReLU and ReLU+Step have identical minimum depths.The paper contrasts the width behavior established by Theorems 2 and 3 with depth-2 universal approximation for both activation choices.
  • General activations: For general activations satisfying the stated regularity conditions, width max{dx + 2, dy + 1} guarantees density in Lp(K, Rdy).This result is an upper bound rather than a full characterization, but it improves the previous width dx + dy + 1 bound.

4 Tight upper bound on minimum width for universal approximation

The upper-bound construction encodes inputs into scalar codewords, memorizes target codewords, and decodes them into outputs. Quantization errors can be made arbitrarily small, yielding width max{dx + 1, dy} for ReLU+Step and the corresponding ReLU and general-activation results.

  • Coding scheme: The coding scheme approximates a target function with three components: an encoder, a memorizer, and a decoder.The encoder maps input vectors to one-dimensional codewords, the memorizer maps them to target codewords, and the decoder produces output vectors.
  • Encoder: The encoder quantizes each input coordinate into K bits and concatenates the quantized coordinates into one scalar codeword.The quantization error is at most 2^-K, so the encoding information loss can be reduced by increasing K.
  • Memorizer: The memorizer maps each input codeword to a target codeword encoding the function value at the corresponding quantized input.Increasing K and M makes the information loss from input and output quantization arbitrarily small.
  • Approximation error: The overall coding map is equivalent to qM ◦ f∗ ◦ qK and achieves error at most ε when ωf∗(2^-K) + 2^-M ≤ ε.Thus sufficiently large K and M control both continuity and quantization errors.
  • ReLU+Step implementation: ReLU+Step implements the encoder, memorizer, and decoder with widths dx + 1, 2, and dy, respectively, giving overall width max{dx + 1, dy}.Step is used only for the discontinuous encoder; the memorizer and decoder are implemented with ReLU networks.
  • Extensions: The same construction supports the ReLU Lp upper bound and extends to general activations through their existing continuous-function approximation results.The ReLU construction uses the same coding architecture, while general activations yield a separate upper-bound result.

5 Tight lower bound on minimum width for universal approximation

The section proves that width-2 ReLU networks cannot uniformly approximate a constructed curve from [0,1] to R2. The proof uses topological properties of successive affine-coordinate-ReLU transformations to derive a contradiction.

  • Counterexample: A curve f*: [0,1]→R2 and ε>0 are constructed so every width-2 ReLU network has uniform error greater than ε.The proof proceeds by contradiction, assuming a width-2 network achieves error at most 1/100.
  • Network reformulation: A width-2 network is reformulated as an initial affine map followed by sequential coordinate changes, ReLU operations, and inverse coordinate changes.Each transformation φ_l^-1∘σ∘φ_l applies ReLU in a modified coordinate system before returning to the original coordinates.
  • Topological properties: ReLU’s coordinatewise thresholding implies that points outside a transformed feasible region move to its boundary, while points that remain fixed preserve bounded path-connected components.These properties are formalized in Lemmas 5 and 6 and drive the topological contradiction.
  • Counterexample construction: The counterexample curve consists of three segments, including a red segment, a black segment, and a blue segment with prescribed endpoints.The construction is illustrated in Figure 2(a), while Figures 2(b) and 2(c) depict the relevant intermediate-image configurations.
  • Contradiction: At a critical layer, the blue image together with a box forms a closed loop that surrounds part of the red image unless the two curve portions intersect.Intersection contradicts the assumed approximation structure; otherwise, later layers cannot move the surrounded points without violating the ReLU lemmas or the critical-layer definition.

6 Conclusion

The conclusion presents the paper as giving an exact characterization of minimum widths for ReLU and ReLU+Step networks. It emphasizes dependence on target function classes and activation functions as relevant to understanding deep, narrow architectures.

  • Contribution: The paper addresses the longstanding gap between upper and lower bounds on the minimum width required for universal approximation.The authors describe this width-bounded universal approximation problem as fundamental to expressive-power theory.
  • Contribution: The work provides an exact characterization of minimum width for ReLU networks and ReLU+Step networks.The conclusion identifies this as the paper’s central result.
  • Implications: The results show that minimum width depends on both the target function class and the activation functions.The conclusion contrasts this dependence with the minimum-depth setting discussed in classical approximation results.
  • Implications: The authors state that their results and analyses may contribute to understanding modern deep and narrow network architectures.

A.1 Proof of tight upper bound in Theorem 3

The proof establishes a width-max{d_x+1,d_y} upper bound for uniform approximation of continuous functions using ReLU+Step networks. It does so with an encoder–memorizer–decoder construction whose component widths determine the overall width.

  • Upper bound: Width max{d_x+1,d_y} ReLU+Step networks are dense in C([0,1]^d_x,R^d_y).For every continuous target and ε>0, the construction achieves uniform error at most ε.
  • Encoder: The encoder quantizes each input coordinate using the discontinuous Step activation and requires width d_x+1.Step permits exact construction of the piecewise-constant quantizer q_K, which cannot be uniformly approximated by ReLU alone.
  • Memorizer: The memorizer maps finitely many scalar codes to target values and can be exactly implemented by a width-2 ReLU network.Its construction uses piecewise-linear continuous functions on a finite set.
  • Decoder: The decoder maps scalar codes to target vectors and is constructed with width d_y while keeping outputs in [0,1]^d_y.The decoder construction is based on Lemma 10.
  • Assembly: The overall width is max{d_x+1,d_y}, and sufficiently large coding parameters K and M ensure uniform error at most ε.The width is the maximum of the encoder, memorizer, and decoder widths.

A.2 Proof of tight upper bound in Theorem 1

The proof derives the same width max{d_x+1,d_y} upper bound for L^p approximation with ReLU networks. It approximates a compactly supported continuous target through quantization, memorization, and decoding while controlling errors on small exceptional sets.

  • Upper bound: For every p∈[1,∞), f*∈L^p(R^d_x,R^d_y), and ε>0, a ReLU network of width max{d_x+1,d_y} achieves L^p error at most ε.The proof first reduces the target to a continuous function on compact support.
  • Encoder: ReLU approximates the encoder outside an exceptional set D_γ of arbitrarily small measure, because Step is unavailable.The construction provides a width-d_x+1 encoder and bounds μ(D_γ) by γ.
  • Error control: Inputs in D_γ may be mapped to arbitrary values, but their contribution to L^p error can be made small by choosing γ sufficiently small.
  • Error control: The boundary-set error is controlled because μ(E_K)<2^-d_xK, so sufficiently large K, M and sufficiently small γ yield the target L^p accuracy.

A.3 Proof of Theorem 4

The proof establishes a width max{d_x + 2, d_y + 1} upper bound for universal approximation with general continuous nonpolynomial activations, using an encoder–memorizer–decoder construction. The construction approximates the target in L^p by controlling discretization and componentwise approximation errors.

  • Upper-bound statement: For any p ∈[1, ∞), f*∈L^p(K, R^d_y), and ε > 0, a ρ network of width max{d_x + 2, d_y + 1} achieves L^p error at most ε.This is the statement proved as Theorem 4.
  • Approximation reduction: The proof first replaces the target by a continuous function f′ and reduces the task to constructing a network with ||f′ − f||_p ≤ ε.The target has compact support in [0,1]^d_x and codomain [0,1]^d_y in the proof, with extension to arbitrary compact support and codomain noted.
  • Network construction: A coding-based encoder of width d_x + 2, a memorizer of width 3, and a decoder of width d_y + 1 are composed to form the approximating network.The encoder and memorizer discretize and store coded values, while the decoder maps the code back toward the output vector.
  • Network construction: The decoder maps codes into [−ε, 1 + ε]^d_y, while the construction extracts output coordinates iteratively from the encoded representation.The decoder guarantee is stated for inputs in a compact interval containing [0,1].
  • Error control: Choosing sufficiently large K and M and sufficiently small component errors makes the total L^p approximation error smaller than ε/2, completing the upper-bound proof.The bound uses the modulus of continuity of f′ and the finite supremum of its L^p norm on [0,1]^d_x.

B.1 Proof of general lower bound

The general lower bound shows that width d_y − 1 networks cannot be dense in either L^p(K, R^d_y) or C(K, R^d_y), regardless of the activation functions. The proof constructs a target whose range follows the vertices of a d_y-dimensional simplex, while narrower networks factor through a lower-dimensional affine image.

  • Lower-bound statement: Width d_y − 1 networks are not dense in both L^p(K, R^d_y) and C(K, R^d_y) for any set of activation functions.The result applies independently of the activation choice.
  • Counterexample: The counterexample target f* traverses the d_y + 1 vertices of a d_y-dimensional simplex sequentially as the first input coordinate increases.It remains at each vertex for intervals of length 1/2^(d_y+1) and moves between vertices at constant speed.
  • Factorization: Any network of width less than d_y with at least two layers factors as a final affine map t_L: R^k → R^d_y applied to the preceding computation, with k = d_y − 1 sufficient for the argument.Cases with k < d_y − 1 are covered by considering k = d_y − 1.
  • Geometric obstruction: A (d_y − 1)-dimensional hyperplane cannot uniformly approximate all simplex vertices, yielding a positive lower bound on the approximation error.The proof uses the simplex’s positive distance from every such hyperplane and a volumetric projection argument.

B.2 Proof of tight lower bound in Theorem 3

The proof of the tight lower bound for ReLU+Step networks shows that width d_x cannot uniformly approximate the constructed continuous target. Its key structural lemma is that every nonempty level set of a width-d_x network containing a Step activation is unbounded.

  • Conclusion: Thus the tight lower bound for uniform approximation with ReLU+Step networks is max{d_x + 1, d_y}.The d_y lower bound comes from the general width lower bound, while this argument supplies the d_x + 1 requirement.
  • Level-set property: For ReLU+Step networks containing at least one Step activation, every nonempty level set is unbounded.This is the central structural property established in Lemma 19.
  • Level-set property: The proof analyzes the first layer containing Step and uses induction through preceding ReLU layers to preserve the unbounded-or-empty level-set structure.The base case follows because a Step unit maps an input ray to the same output.
  • Inductive mechanism: For preceding width-d_x ReLU layers, the relevant activation region is open and convex, the network is affine there, and bounded level sets must lie inside that region.These properties are supplied by Lemma 20 and support the induction.
  • Contradiction: The target’s level set separates a central point from infinity, whereas any sufficiently accurate width-d_x ReLU+Step approximation has an unbounded level set through that point.Their intersection forces incompatible target values, contradicting the assumed uniform approximation error.

B.3 Proof of tight lower bound in Theorem 1

The proof of the tight L^p lower bound shows that width-d_x ReLU networks cannot approximate a suitable target in L^p. Unbounded level sets force any nontrivial network output to persist over sets of infinite measure, preventing L^p membership or approximation.

  • Lower-bound statement: There exist f*∈L^p(R^d_x, R) and ε > 0 such that every width-d_x ReLU network remains more than ε away from f* in L^p.The argument can be generalized to arbitrary codomains.
  • Level-set mechanism: For a width-d_x ReLU network, either the network is identically zero or its level-set structure produces an unbounded set on which nonzero outputs persist.The proof assumes d_x hidden neurons per layer and invertible affine transformations without loss of generality.
  • L^p obstruction: An unbounded level set thickened by a fixed neighborhood has infinite measure, so a nonzero output over it makes the p-th power integral diverge.The proof explicitly uses Lebesgue measure and concludes f∉L^p(R^d_x, R) in this case.
  • L^p obstruction: If the network vanishes outside the relevant activation region, the same level-set argument forces it to be zero throughout that region or again rules out L^p membership.This establishes the stronger dichotomy used to derive the approximation lower bound.
  • Conclusion: The resulting contradiction completes the tight upper-width proof for Theorem 1.The supplied proof passage identifies this as the conclusion of the theorem’s tight-width argument.

B.6 Proof of Lemma 7

The proof uses simple curves, loops, and polygons to construct a closed boundary U and show that gℓ∗(q) lies inside its bounded complement component. A parity argument then establishes the required containment.

  • Definitions: The proof defines curves, simple curves, loops, simple loops, polygons, and simple polygons through continuous, injective, or piece-wise linear parameterizations.
  • Constructing U: A simple polygon U is constructed from line segments of gℓ∗([p2,1]) and a line segment L, forming a simple loop around gℓ∗(q).
  • Parity argument: The proof shows πU(gℓ∗(q))=1, so gℓ∗(q) lies in the bounded path-connected component of R2 \ U.
  • Topological separation: By the Jordan curve theorem, R2 \ U has exactly two path-connected components, one bounded and one unbounded.
  • Parity argument: The parity function πU counts proper ray intersections with U modulo 2 and identifies the unbounded component by πU(x)=0.
Loading 2006.08859v1…