The Expressive Power of Neural Networks: A View from the Width
Width-(n+4) ReLU networks are universal in L1, while width efficiency has a polynomial lower bound.
Key Findings
Methodology
The paper studies fully connected ReLU networks, with ReLU(x)=max(x,0), parameterized by input dimension n, maximal layer width dm, and depth h. It combines constructive approximation, measure-theoretic arguments, and geometric analysis of information loss. The authors then compare wide shallow targets with narrow deep approximators, proving a quantitative lower bound and testing its practical tightness through random synthetic networks and supervised optimization.
Key Results
- Theorem 1 proves that for every Lebesgue-integrable f:R^n→R and ε>0, a ReLU network of width at most n+4 satisfies ∫|f−FA|dx<ε. The construction concatenates depth-(4n+1) blocks that process local cubes, preserve previous approximations, and accumulate them.
- Theorem 2 shows that for nontrivial integrable targets, a network with width dm≤n has L1 error either +∞ or exactly ∫|f|, so it generally cannot make useful progress. Theorem 3 gives a positive error lower bound on [-1,1]^n for width at most n−1.
- Theorem 4 constructs width-2k², depth-3 networks that cannot be approximated arbitrarily by bounded-parameter networks of width at most k^(3/2) and depth at most k+2. Experiments nevertheless find low error; for n=1,k=5, worst and mean MSE are 0.005643 and 0.001296.
Significance
The work extends universal approximation theory from the conventional fixed-depth, width-growing perspective to fixed-width, depth-growing ReLU networks. It identifies a sharp qualitative transition near the input dimension: width n+4 is sufficient for L1 universality, whereas width at most n suffers a severe information bottleneck. Its width-efficiency result is only polynomial, unlike exponential depth-separation theorems, but the experiments suggest that a constant-factor increase beyond the lower-bound depth may often suffice. This strengthens the case that depth is typically more efficient than width.
Technical Contribution
The central construction is a width-(n+4) memory-and-accumulation architecture. n neurons relay coordinates, two preserve the approximation produced by earlier blocks, and two implement the current local approximation. A four-layer subnetwork handles the two-sided truncation in each coordinate, yielding a block of depth 4n+1. The impossibility proof exploits geometric collapse in the first layer: when width is no larger than n, many input points along suitable rays share the same first-layer representation, so subsequent ReLU layers cannot reconstruct the discarded variation.
Novelty
Relative to Cybenko, Funahashi, and Hornik, which establish depth-bounded universal approximation, this paper gives a systematic width-bounded theorem specifically for ReLU networks and exposes the n versus n+4 transition. Relative to Eldan–Shamir and Telgarsky, it formulates the dual width-efficiency question: how much additional depth is required when width is reduced?
Limitations
- Theorem 4 establishes only a polynomial lower bound, not the exponential separation known for some depth results; it therefore does not prove that width is fundamentally weaker than depth.
- Experiments cover only n=1,2 and k=3,4,5 on random synthetic functions, so they do not establish behavior on high-dimensional vision, language, or convolutional workloads.
- A polynomial upper bound remains open; successful AdaDelta training is empirical evidence, not a universal constructive theorem.
Future Work
The authors leave open whether width efficiency has an exponential lower bound or a universal polynomial upper bound. Important extensions include convolutional and residual architectures, sharper constants around the n+4 threshold, explicit dependence on approximation error, parameter magnitude, and domain, and the trainability of narrow deep simulations. High-dimensional real-task studies are also needed to connect expressivity theory with architecture selection.
AI Executive Summary
Neural-network expressivity is usually discussed through depth, yet every layer also has a finite information capacity: its width. Lu and colleagues study this neglected axis for fully connected ReLU networks, asking when a narrow network can approximate arbitrary functions and how much depth can compensate for reduced width. Their analysis complements classical universal approximation theorems and depth-separation results by treating width as the primary resource.
The headline theorem is constructive. For input dimension n, a width-(n+4) ReLU network can approximate every Lebesgue-integrable function on R^n arbitrarily well in L1 distance. Its depth may be large: the construction concatenates depth-(4n+1) blocks. Each block passes all n coordinates, approximates the target on one cube, stores earlier output, and adds the new contribution. In contrast, width at most n creates a geometric bottleneck. Distinct inputs can collapse to identical first-layer representations, so later layers cannot recover the lost direction; broad classes of functions therefore remain badly approximated.
The paper then asks whether width can be traded for depth efficiently. Theorem 4 constructs width-2k², depth-3 targets that cannot be approximated arbitrarily by parameter-bounded networks of width at most k^(3/2) and depth at most k+2, giving a polynomial lower bound. Experiments use random synthetic targets for n=1,2 and k=3,4,5, with 20,000 or 40,000 uniformly spaced inputs, AdaDelta training, and 50 trials. For n=1,k=5, worst and average MSE are only 0.005643 and 0.001296. Thus depth appears practically powerful, although the general polynomial upper-bound question remains unresolved.
Deep Analysis
Background
Classical results by Cybenko, Funahashi, and Hornik show that shallow networks with suitable activations are universal approximators, although their required width may grow exponentially with input dimension. Later work by Eldan–Shamir, Cohen–Sharir–Shashua, and Telgarsky established strong depth advantages. The paper argues that these results do not fully explain the role of width, motivating a dual analysis for fully connected ReLU networks.
Core Problem
The study asks two precise questions: what is the minimum width needed for universal approximation, and how much depth or total size is required when a wide network is replaced by a narrow one? The challenge comes from ReLU’s piecewise-linear structure, approximation over R^n, and the need for function-level rather than parameter-count arguments.
Innovation
The paper contributes three results. First, it proves L1 universal approximation for width n+4. Second, it proves severe non-approximation for width at most n and a positive bounded-domain error floor below n. Third, it establishes a polynomial width-efficiency lower bound and complements it with experiments suggesting that the lower-bound scale may also be close to a practical upper bound.
Methodology
- �� Define ReLU(x)=max(x,0), network width as maximal layer size, and depth including the output layer.
- �� Partition a target function into local contributions supported on cubes.
- �� Build depth-(4n+1), width-(n+4) blocks; n units relay coordinates, two store prior output, and two implement the current local approximation.
- �� Use repeated ReLU truncations to simulate cube indicators and local functions, then sum blocks while controlling tail error through integrability.
- �� For width efficiency, construct a width-2k², depth-3 target and restrict the approximator to width k^(3/2), depth k+2, and parameters in [−b,b].
- �� Train the narrow approximator by supervised regression and measure mean squared error on uniformly sampled inputs.
Experiments
Targets are fully connected ReLU networks with input dimension n=1 or 2, scalar output, width 2k², and depth 3; k is 3, 4, or 5. Weights are sampled from a standard normal distribution and biases uniformly from [−1,1). Approximators have width 3k^(3/2) and depth k+2. Evaluation uses 20,000 points for n=1 and 40,000 for n=2 in [−1,1)^n, split equally into training and testing. AdaDelta uses learning rate 1.0 for 100 or 200 epochs; 50 parameter draws produce worst-case and mean MSE.
Results
The width-(n+4) theorem establishes arbitrary L1 approximation on R^n, while width at most n is generally ineffective. Theorem 4 supplies a polynomial separation. Empirically, for n=1 and k=3,4,5, worst MSE is 0.002248, 0.003263, and 0.005643, with mean MSE 0.000345, 0.000892, and 0.001296. For n=2, worst MSE is 0.008729, 0.018852, and 0.030114, while mean MSE is 0.001990, 0.006251, and 0.007984.
Applications
The results inform architecture design under memory or hardware limits: if a layer cannot be wide, additional layers may sequentially preserve and recombine information. They also motivate teacher–student compression, where a narrow deep ReLU model approximates a wide shallow model. However, the theory should not be interpreted as a direct prescription for optimal image or language architectures.
Limitations & Outlook
The analysis is restricted to fully connected ReLU networks and primarily L1 or integrated squared error; it does not cover convolution, residual connections, normalization, or classification generalization. The polynomial lower bound is far from an exponential separation. Experiments are low-dimensional, synthetic, and small-scale, and optimization success does not prove a universal polynomial upper bound. Future work needs sharper constructions, trainability theory, and high-dimensional real benchmarks.
Plain Language Accessible to non-experts
Imagine a factory assembly line. Width is the number of workers available at each station; depth is the number of stations. A very wide line can process many pieces of information simultaneously, but it may require an enormous workforce. This paper shows that a line with n+4 workers per station can, if long enough, approximate almost any task. Some workers carry the n input measurements forward, others remember what earlier stations have produced, and the remaining workers process the current small region before adding it to the running result.
If the line has no more than n workers, information can be lost at the first station. Two different objects may receive the same label, and later workers cannot tell them apart. More stations do not automatically restore a missing label. This is why the paper finds a sharp threshold near the input dimension.
The authors also test whether a wide, short line can be replaced by a narrow, long one. Mathematics shows that some replacements require at least a polynomial increase in size. Yet small experiments suggest that a narrow line only a constant factor deeper can often reproduce the wide line with tiny error. The result is encouraging, but it was tested only on simple, low-dimensional artificial tasks—not on photographs, speech, or conversations.
ELI14 Explained like you're 14
Think of a neural network as a team building a super-smart game character. Width is how many teammates can work during one game level; depth is how many levels they must pass. A huge team can inspect lots of clues at once, while a small team may need more levels to finish the same job. Which team wins? That is exactly what this paper investigates!
The surprising rule is that if the input has n pieces of information, a team with n+4 working spots can eventually imitate almost any reasonable pattern. But a team with at most n spots may accidentally treat different inputs as identical during the first level. After that, even dozens of extra levels cannot recover the forgotten clue. It is like deleting part of a save file and hoping the next levels magically know what was erased.
The researchers then made a wide, short network and challenged a narrow, deeper network to copy it. The theory says some copies need polynomially more layers. In experiments, however, the copies were impressively accurate. For one-dimensional inputs with k=5, the average mean squared error was just 0.001296. That is like a remake of a game looking almost exactly like the original!
But don’t jump to “deeper is always better.” The tests used tiny artificial examples with one or two input dimensions, not real games, photos, or social-media data. The big mystery remains: can every wide network be copied by a polynomially deeper narrow one? Researchers still need to solve that level!
Glossary
ReLU
ReLU is the function max(x,0): negative values become zero and positive values pass through. Technically, it creates piecewise-linear transformations.
Every network analyzed in the paper uses fully connected ReLU activations.
Universal approximation
A model has this property if it can approximate any function in a specified class to arbitrarily small error. The paper uses L1 approximation for integrable functions on R^n.
Theorem 1 proves universality at width n+4.
Width
Width is the maximum number of computational units in any layer. It represents parallel representational capacity and short-term information storage.
The main threshold is width relative to input dimension n.
Depth
Depth is the number of network layers, including the output layer but excluding the input layer. It enables repeated sequential transformations.
Depth is compared with width as a substitute resource.
L1 distance
The L1 error between f and g is ∫|f(x)−g(x)|dx. It measures total absolute discrepancy over the domain.
Theorems 1–3 use L1 distance for approximation and impossibility.
Width efficiency
Width efficiency measures the extra depth or size needed after reducing width while preserving approximation quality. The overhead may be polynomial or exponential.
Theorem 4 proves a polynomial lower bound.
Open Questions Unanswered questions from this research
- 1 It remains unknown whether width efficiency has an exponential lower bound or a universal polynomial upper bound. Resolving this requires new complexity arguments and constructive approximation methods.
- 2 The optimal threshold near n+4 is unknown, especially under compact-domain L∞ error, alternative activations, or architectural constraints.
- 3 The low-dimensional synthetic evidence has not been connected rigorously to high-dimensional images, language, convolutional networks, or trainability.
Applications
Immediate Applications
Architecture design under memory limits
When hardware limits the number of units per layer, designers can keep width above the input-dimension bottleneck and add depth to perform sequential computation. This is most directly relevant to small regression models, embedded inference, and constrained prototypes.
Teacher–student model replacement
A wide shallow ReLU network can serve as a teacher, while a narrower deeper network is trained by supervised regression to reproduce its outputs. The paper’s results suggest that a modest constant-factor depth increase may achieve low MSE, although validation on the real task remains necessary.
Long-term Vision
Automated width–depth co-design
Future neural architecture search could estimate where parallel channels are needed to preserve information and where sequential depth is sufficient. Such systems may jointly optimize accuracy, latency, memory, and energy instead of treating width and depth independently.
Abstract
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.