Source-linked AI summary
The Expressive Power of Neural Networks: A View from the Width
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, Liwei Wang
TL;DR
The paper asks how width affects neural-network expressiveness, complementing the dominant focus on depth. It proves width-bounded ReLU approximation and width-efficiency results, with experiments supporting the conclusion that depth is more effective for expressiveness.
Problem
Prior expressive-power research focused mainly on depth, leaving the role and efficiency of width less understood.
Method
The paper proves width-bounded universal approximation and polynomial width-efficiency bounds for ReLU networks, then evaluates narrow-network approximation experimentally.
Results
Width-(n + 4) ReLU networks are universal approximators, width-n networks fail for almost all functions, and wide networks require polynomially more nodes when approximated by narrow ones.
Takeaways & Limitations
The theoretical results and experiments provide more comprehensive evidence that depth is more effective than width for ReLU-network expressive power.
Takeaways & Limitations
Whether width efficiency has an exponential lower bound or a polynomial upper bound remains an open problem.
Abstract
from arXiv · showhide
The expressive power of neural networks is important for understanding deep learning. Most existing works consider this problem from the view of the depth of a network. In this paper, we study how width affects the expressiveness of neural networks. Classical results state that depth-bounded (e.g. depth-$2$) networks with suitable activation functions are universal approximators. We show a universal approximation theorem for width-bounded ReLU networks: width-$(n+4)$ ReLU networks, where $n$ is the input dimension, are universal approximators. Moreover, except for a measure zero set, all functions cannot be approximated by width-$n$ ReLU networks, which exhibits a phase transition. Several recent works demonstrate the benefits of depth by proving the depth-efficiency of neural networks. That is, there are classes of deep networks which cannot be realized by any shallow network whose size is no more than an exponential bound. Here we pose the dual question on the width-efficiency of ReLU networks: Are there wide networks that cannot be realized by narrow networks whose size is not substantially larger? We show that there exist classes of wide networks which cannot be realized by any narrow network whose depth is no more than a polynomial bound. On the other hand, we demonstrate by extensive experiments that narrow networks whose size exceed the polynomial bound by a constant factor can approximate wide and shallow network with high accuracy. Our results provide more comprehensive evidence that depth is more effective than width for the expressiveness of ReLU networks.
1 Introduction
The paper studies neural-network expressiveness from the perspective of width, complementing prior work focused mainly on depth. It develops width-efficiency results for ReLU networks and reports evidence that depth is more effective for expressiveness.
- Width provides a complementary perspective for understanding neural-network expressive power, which describes the ability to approximate functions.
- Width-(n + 4) ReLU networks approximate any Lebesgue-integrable function on n-dimensional space in L1 distance.
- Except for a zero-measure set, Lebesgue-integrable functions cannot be approximated by width-n ReLU networks, exhibiting a width phase transition.
- The paper concludes that its theoretical and experimental results provide evidence that depth is more effective than width for ReLU-network expressiveness.
- Width-O(k2), depth-2 ReLU networks cannot be approximated by width-O(k1.5), depth-k networks, establishing a polynomial lower bound for width efficiency.
- Experiments show that narrow networks slightly exceeding this lower bound achieve high approximation accuracy on wide, shallow networks.
2 Preliminaries
The preliminaries define fully-connected ReLU networks and the width and depth measures used throughout the paper. The analysis focuses on Lebesgue-integrable functions and L1 approximation error.
- A fully-connected ReLU network is a layered network connecting every pair of nodes in adjacent layers and using Rectifier Linear Unit activations.
- Network depth h counts layers including the output layer but excluding the input layer, while width is the maximum number of nodes in any layer.
- The input dimension is denoted by n.
- The paper studies Lebesgue-integrable functions f: Rn → R and measures approximation using L1 distance.
3 Width-bounded ReLU Networks as Universal Approximator
This section proves universal approximation for width-bounded ReLU networks and establishes a phase transition around width n. Its construction uses concatenated fixed-width blocks, while thin networks suffer dimension-related limitations.
- Width-(n + 4) ReLU networks approximate every Lebesgue-integrable function f: Rn → R to arbitrary L1 accuracy.
- The construction concatenates depth-(4n + 1), width-(n + 4) blocks that approximate functions supported on cubes, retain previous outputs, and sum approximations.
- Each block transfers n input coordinates, stores prior approximations in two neurons, and uses two additional neurons for the current cube.
- The results form a dual version of the classical depth-bounded universal approximation theorem, though they use Lebesgue-integrable functions and L1 distance rather than continuous functions and L∞ distance.
- The width threshold at n produces a phase transition in ReLU-network expressive power.
- Width at most n yields weak approximation ability because insufficient width can make different input points share corresponding first-layer values and therefore outputs.
4 Width Efficiency vs. Depth Efficiency
The paper studies whether width-efficient ReLU networks can match wide networks without substantially greater size, contrasting this with depth efficiency. Theory gives a polynomial width lower bound, while experiments support a polynomial upper-bound picture.
- Theoretical comparison: Wide ReLU networks exist that narrow networks cannot approximate unless their depth increases by more than a polynomial bound.This establishes a polynomial lower bound for width efficiency, weaker than the exponential lower bounds known for depth efficiency.
- Theoretical comparison: Depth efficiency has exponential lower bounds, whereas the paper’s width-efficiency theorem establishes only a polynomial lower bound.The authors note that this distinction leaves open whether width might also have an exponential lower bound.
- Open problem: The paper frames exponential width lower bounds and polynomial width upper bounds as competing possibilities for the unresolved width-efficiency problem.A polynomial upper bound would imply that depth plays a significantly stronger role in ReLU expressive power.
- Experiments: Experiments approximate randomly parameterized wide, shallow target networks with narrower networks whose width is 3k^3/2 and depth is k + 2.Targets have width 2k^2 and depth 3, with n = 1, 2 and k = 3, 4, 5; approximation uses supervised learning over sampled inputs.
- Experiments: The studied approximator networks achieve very small mean square error, and an example approximation is visually almost indistinguishable from its target.The error is evaluated as mean square error on uniformly placed inputs; Table 1 reports worst- and average-case results over 50 random parameter samples.
5 Conclusion
The conclusion presents width as a complementary lens on ReLU expressiveness, establishing a width phase transition and polynomial size lower bounds for narrowing networks. Experiments support a polynomial upper-bound interpretation, while the relative roles of width and depth remain jointly important.
- Main contributions: The paper establishes a universal approximation theorem for width-bounded ReLU networks, complementing classical results for depth-bounded networks.Its theorem concerns approximation of Lebesgue-integrable functions on the whole Euclidean space using L1 distance.
- Main contributions: A phase transition in expressive power occurs as the width of a ReLU network varies for a fixed input dimension.The conclusion identifies this transition as a central consequence of the width-bounded approximation result.
- Width efficiency: Wide networks cannot be approximated by narrow networks without polynomially more nodes, establishing a lower bound on approximation size.The paper also leaves open whether the width-efficiency lower bound is exponential or whether a polynomial upper bound holds.
- Width efficiency: Experiments support the polynomial upper-bound possibility and align with the paper’s analytical insights.The conclusion presents this evidence as part of a broader study of width and depth rather than as a completed proof of the upper bound.
- Implications: Width and depth should be tuned together because depth may determine abstraction level while width may influence information loss during forward propagation.The paper argues that comprehensive understanding of expressive power requires both views.
A.1 Proof of Theorem 1
The proof constructs width-(n + 4) ReLU networks by approximating integrable functions with weighted cube indicators. Sequential network blocks reshape cube regions, accumulate signed contributions, and achieve vanishing L1 error as the boundary parameter decreases.
- Approximation strategy: The proof first approximates a Lebesgue-integrable function by a finite weighted sum of indicator functions on n-dimensional cubes.It then implements each indicator approximation with a ReLU network and combines the resulting terms.
- Approximation strategy: Each construction block has width n + 4 and depth 3, preserving input coordinates while computing and storing the current approximation.The first n + 2 units act as memory elements, and the final two units perform the current computation.
- Cube simulation: The Single ReLU Unit progressively chops the support of an intermediate function across dimensions to form a hyper-trapezoid inside a cube.For each dimension, the construction uses boundary conditions controlled by δ to reduce the support region.
- Cube simulation: Sequential blocks store each simulated cube contribution in dedicated memory units, sum positive and negative terms, and reset computation units for the next cube.This allows the network to combine approximations of multiple positive and negative indicator functions into the target approximation.
- Error control: As δ approaches 0, the simulation error in L1 distance converges to 0.The construction therefore supplies arbitrarily accurate approximations of the cube indicators needed for the universal approximation proof.
A.2 Proof of Theorem 2
The proof shows that width-n ReLU networks under the stated condition can represent only the zero function, using a recursive decomposition into linear blocks and ray-based arguments. This yields Theorem 2.
- Proof setup: Under Condition 1, all layers except the output have width n, and Lemma 2 constructs nested linear blocks with controlled ReLU representations.Each X_k is a linear block; on X_k, the first k ReLU layers represent an affine function, while the network output vanishes on the boundary.
- Conclusion: If Lemma 2 holds at k = h − 1, the network output is linear on its support block and zero outside it.The proof then shows that Lipschitz continuity forces the output to vanish on the support block as well.
- Inductive construction: The proof proceeds by mathematical induction, taking X_0 = R^n and defining X_{k+1} where every kth-layer node output is positive.Convexity and the four inductive conditions are then propagated from X_k to X_{k+1}.
- Ray argument: For points outside X_{k+1}, a direction orthogonal to the other weight rows makes the ReLU representation constant along a ray.Convexity, continuity, and the ray argument extend the zero-output property from finite ray segments or infinite rays.
- Conclusion: Consequently, when all hidden-layer widths are at most n, the represented function is identically zero.The text identifies Theorem 2 as a direct consequence of Lemma 1.
A.3 Proof of Theorem 3
The proof of Theorem 3 shows that a network whose first layer has fewer than n nodes is constant along a fixed input direction. Continuous functions varying along every direction therefore remain separated from such networks in L1 distance.
- Fixed-direction invariance: When the first-layer width m is less than the input dimension n, a nonzero vector x_0 leaves all first-layer values unchanged.The resulting direction is determined by the null space of the first-layer linear map.
- Fixed-direction invariance: The network output is therefore constant along the fixed direction x_0.This follows because later computations depend on the input through the unchanged first-layer representation.
- Approximation lower bound: For a continuous target function that differs at two points along x_0, every continuous function constant along x_0 has a positive L1 approximation error.Neighborhoods around the two points preserve a positive function-value gap, yielding a positive lower bound on the integral error.
- Uniform separation: The lower bound remains positive uniformly over all unit directions because the error varies continuously on the compact unit sphere.This produces a universal positive constant separating the target from all network functions with the fixed-direction invariance property.
A.4 Proof of Theorem 4
The proof constructs a family of wide ReLU networks and shows that almost none can be represented by substantially narrower networks under specified depth and width bounds. It then extends the one-dimensional argument to higher-dimensional inputs.
- Proof strategy: The proof first handles input dimension n = 1, with the extension to n > 1 obtained by ignoring the additional inputs.The constructed wide network uses only the first input coordinate, setting weights from the other inputs to zero.
- Wide-network construction: A width-2k^2, depth-3 ReLU network is constructed to represent every function in the family E0.The construction uses first-layer shifted ReLU features and second-layer piecewise linear functions whose values are fixed at selected integral points.
- Wide-network construction: The network’s output is determined by activating the constructed piecewise linear functions and summing them to obtain fA.Linearity between integral points uniquely determines the node functions before their ReLU activation and aggregation.
- Narrow-network lower bound: Only a zero-measure subset of networks in Fk can be equaled by networks of width at most k and depth at most k^(3/2) + k + 2.The argument evaluates networks on 2k^4 points and uses a parameter-to-output mapping whose range has measure zero because the narrower networks have fewer degrees of freedom.
- Narrow-network lower bound: The negligible-range result implies that only a negligible set of functions in the wide-network family can be equaled by such narrower networks.The family E0 has positive measure, so its intersection with the narrower networks’ range is negligible; bounded parameters then extend the finite-point difference to the input-domain integral.
- Approximation gap: For every permitted narrow-network shape, Lemma 6 establishes a positive approximation error against a suitable wide network, completing the polynomial width-efficiency lower bound.The proof uses continuity, bounded parameters, convergent subsequences, and dominated convergence to show the infimum error is strictly positive.