Source-linked AI summary
ResNet with one-neuron hidden layers is a Universal Approximator
Hongzhou Lin, Stefanie Jegelka
TL;DR
The paper asks whether extremely narrow deep networks can universally approximate functions, addressing the failure of fully connected networks at width d. It constructs deep ResNets with one-neuron ReLU residual blocks and proves universal approximation for Lebesgue-integrable functions in d dimensions. The result distinguishes ResNets from fully connected networks and attributes the difference to the identity mapping, while the construction has a suboptimal grid-cell dependence and faces a memory-related width constraint.
Problem
Fully connected ReLU networks cannot universally approximate functions when each hidden layer has at most d neurons, motivating the question of whether ResNet architecture changes this limit.
Method
The paper stacks residual blocks with one ReLU neuron per hidden layer, adds identity mappings between blocks, and uses a final linear output layer.
Results
ResNet with one neuron per hidden layer universally approximates every Lebesgue-integrable function in d dimensions as depth tends to infinity.
Takeaways & Limitations
The identity mapping gives ResNets greater representational power than fully connected networks for tall narrow architectures.
Takeaways & Limitations
The number of grid cells scales as O(1/r^d), which the paper identifies as suboptimal and leaves for future improvement.
Abstract
from arXiv · showhide
We demonstrate that a very deep ResNet with stacked modules with one neuron per hidden layer and ReLU activation functions can uniformly approximate any Lebesgue integrable function in $d$ dimensions, i.e. $\ell_1(\mathbb{R}^d)$. Because of the identity mapping inherent to ResNets, our network has alternating layers of dimension one and $d$. This stands in sharp contrast to fully connected networks, which are not universal approximators if their width is the input dimension $d$ [Lu et al, 2017; Hanin and Sellke, 2017]. Hence, our result implies an increase in representational power for narrow deep networks by the ResNet architecture.
1 Introduction
The paper asks whether arbitrarily deep narrow networks remain universal approximators and shows that ResNet’s identity mapping enables universal approximation with only one neuron per hidden layer.
- Universal approximation with bounded width remains an open question when depth tends to infinity.
- Fully connected ReLU networks require at least d + 1 neurons per hidden layer for universal approximation, while width at most d makes it impossible.
- ResNet preserves input dimension through identity mappings while allowing the hidden layers to be narrower than d.
- The paper proves that a ResNet with one neuron per hidden layer and ReLU activation universally approximates every Lebesgue-integrable function f: R^d → R as depth tends to infinity.
- The construction stacks residual blocks containing two linear mappings and one ReLU activation, then applies a final linear output layer.Each block maps R^d to R^d and adds the identity after its nonlinear transformation.
- The simplified architecture omits convolution, pooling, and batch normalization while remaining sufficient for universal approximation.
2 A motivating example
The motivating experiment compares narrow fully connected networks with one-neuron ResNets on unit-ball classification, illustrating the theoretical difference in their attainable decision boundaries.
- The experiment classifies the unit ball in the plane using randomly generated samples and trained networks at various depths.Positive and negative samples are separated by an artificial margin, and logistic loss is used for training.
- Fully connected networks with width d = 2 produce decision boundaries with roughly the same shape across depths, so approximation quality does not visibly improve.
- For fully connected ReLU networks with at most d neurons per hidden layer, the positive level set has Lebesgue measure either zero or infinity.
- Consequently, even infinite-depth narrow fully connected networks cannot approximate a bounded region.
- A one-neuron ResNet represents the indicator of a bounded region from two hidden layers onward, with its boundary appearing to converge toward the unit ball as depth increases.
3 Universal approximation theorem
The paper proves that ResNets with one ReLU neuron per hidden layer can universally approximate any Lebesgue-integrable function in any dimension. Its sequential trapezoid and grid-indicator construction overcomes the memory constraints imposed by the identity mapping.
- Theorem 3.1 establishes universal approximation of every f ∈ ℓ1(R^d) by finite-depth ResNets with one-neuron hidden layers and ReLU activation.
- The proof reduces the problem to approximating compactly supported piecewise constant functions, which are dense in ℓ1(R^d).
- In one dimension, trapezoid functions provide continuous approximations to indicator functions, becoming pointwise closer as δ approaches zero.
- Because summing separately constructed trapezoids requires memory of past components, the ResNet instead builds increasing trapezoid functions sequentially using one-neuron residual-block operations.The available operations shift functions, clip them with constants, and adjust slopes through min/max transformations.
- After constructing the subdivisions, the method rescales level sets one by one to match the target values, yielding the desired piecewise constant approximation.The construction preserves earlier subdivisions while building later ones, then removes the negative tail through cutoff operations.
- The higher-dimensional construction uses d-dimensional grid indicator functions, while arbitrary piecewise constant functions require O(number of grid cells) hidden units or layers.The grid-cell count is O(1/r^d), and the authors identify this exponent as suboptimal under their construction.
4 Discussion and concluding remarks
The paper proves universal approximation for ResNets with one hidden neuron per residual block, contrasting this with fully connected networks and discussing implications for training and generalization.
- The paper establishes universal approximation for ResNets with one neuron in each hidden layer.This contrasts with fully connected networks, where universal approximation fails at width d or less.
- ResNet vs Fully connected networks: ResNet’s identity mapping yields a compressed architecture with O(d) connections per layer instead of O(d2) for width (d + 1) fully connected networks.The paper characterizes the ResNet as a sparse or compressed counterpart to a fully connected network.
- Why does universal approximation matter?: Universal approximation provides a sanity check that, in principle, the architecture can capture any desired decision boundary.This is especially relevant because width d fully connected networks cannot approximate compact decision boundaries even with infinite depth.
- Training efficiency: The theorem guarantees representational possibility but not that SGD or another optimization algorithm will find the approximating function.The paper identifies optimization-landscape analysis as necessary for understanding training efficiency.
- Generalization: The explanation of why deep networks generalize well is outside the paper’s scope, although universal approximation is described as a building block for such a theory.The paper also notes that the over-parametrization implied by its result may play a role in generalization.
A Notations and preliminary
This section defines the piecewise-constant approximation class and identifies elementary operations realizable by one-neuron residual blocks.
- Piecewise constant functions in PC(Rd) have compact support and are constant on finitely many grid cells.They vanish outside a bounded grid region.
- Piecewise constant functions are dense in ℓ1(Rd), reducing universal approximation to approximating each such function arbitrarily well.The reduction follows directly from the definition of Lebesgue measure.
- Basic operations: A one-neuron residual block can shift its input by a constant.The operation is R+ = R + c.
- Basic operations: A one-neuron residual block can take the minimum or maximum of its input and a constant.These operations cut off selected level sets.
- Basic operations: A one-neuron residual block can take the minimum or maximum of its input and a linear transformation, enabling slope adjustment.The maximum case is expressed as R+ = R + [(α −1)R + β]+.
B Warm Up: One Dimension case
The one-dimensional construction builds trapezoid functions inductively, then adjusts separate level sets to approximate arbitrary piecewise constant functions with arbitrarily small error.
- The construction approximates a piecewise constant function h by using trapezoid functions on its subdivisions.The constant value on the k-th interval is denoted hk.
- Initialization: The initial residual construction creates an increasing trapezoid function using sequential cut-off operations applied to the identity function.The construction is illustrated geometrically in Figure 10.
- Inductive construction: Inductively, each new residual block flips the tail slope, folds the next interval, and cuts off the resulting peak to build the next trapezoid.The induction maintains the stated construction conditions C1-C5.
- Function adjustment: Separate level sets allow the network to adjust one function value at a time while leaving previously adjusted levels unchanged.The procedure starts at the top level set and proceeds downward.
- Extension motivation: The monotonicity of the increasing trapezoid function is only a construction aid; the proof uses the separate-level-set property.This motivates replacing monotonicity in higher dimensions with grid indicator functions.
C Extension to high dimension
The higher-dimensional proof constructs grid indicator functions by combining one-dimensional and (d −1)-dimensional subnetworks, then adjusts grid-cell values sequentially.
- Grid-cell adjustment: The resulting construction has separate level sets for d-dimensional grid cells, enabling sequential adjustment of each cell regardless of dimension.The main high-dimensional effort is constructing the grid indicator function.
- Approximation guarantee: For any sufficiently small δ, a one-neuron-per-hidden-layer ResNet equals the target piecewise constant value hk on the δ-interior of each grid cell Ik.This is the stated high-dimensional approximation proposition.
- The high-dimensional construction represents each grid cell as a product of one coordinate interval and a (d −1)-dimensional hypercube.This supports induction on the dimension.
- Network extension: A (d −1)-dimensional network is extended to d dimensions by setting the first-coordinate weight to zero, while the identity mapping preserves the other coordinates.This extension is illustrated in Figure 13.
- Network concatenation: The one-dimensional network on x1 and the (d −1)-dimensional network on x2:d are concatenated within a d-dimensional network.Their outputs occupy separate neurons before being coupled by summation.
D Experimental settings
The experiments examine a two-dimensional unit-ball classification problem and visualize predictions from trained networks using sampled points.
- Experimental setting: The unit-ball classification problem uses 2-dimensional samples, with positives inside the unit ball and negatives in the annulus from radius 2 to 3.The training set contains 10^2 positive samples and 2 ∗10^2 negative samples generated randomly.
- Experimental setting: Figure 15 depicts a five-layer fully connected network with width d = 2.
- Experimental setting: Networks are trained with logistic loss using SGD with momentum for 10 epochs.Training loss saturates after approximately 5–8 epochs.
- Experimental setting: Decision boundaries are visualized by sampling 2 ∗10^3 points in B(0, 5) and coloring positive and negative predictions red and blue, respectively.Red denotes {fN > 0}; blue denotes {fN ≤0}.
E Proof of Proposition 2.1
The proof establishes that narrow fully connected ReLU networks have positive level sets of either zero or infinite measure, then uses this contrast to motivate ResNet approximation operations.
- Implication: The resulting level-set dichotomy means narrow fully connected networks cannot approximate a bounded region, even as depth tends to infinity.
- Proof: For d = 1, the result follows because a one-hidden-unit fully connected network is always monotone.
- Proof: For d ≥2, the proof applies Lemma 1 of [21] and separately handles the possibility that the ℓ1 integral is infinite because of the negative part.An additional network N + thresholds the negative part before analyzing the positive level set.
- Proof: The auxiliary network N + is formed by duplicating the last linear transformation into two ReLU activation functions while retaining at most d neurons per hidden layer.