Why Repeated Folding Matters
A one-dimensional ReLU network is piecewise affine, but its number of affine pieces can grow rapidly when layers are composed. A useful way to see this growth is to repeatedly fold an interval: each fold maps the interval onto itself, creating new turning points that later folds subdivide again. The result is a simple family of highly oscillatory functions whose exact complexity can be counted.
The key comparison is between depth and width. A fixed-width deep network can create exponentially many linear regions through repeated folding, while a single hidden layer needs width proportional to the number of regions for the same family. This is a precise representational statement, not a claim that depth always improves every approximation problem.
The ReLU Tent Map
The formula is a ReLU network with three hidden units and an affine output. On the interval \([0,1]\), the map rises linearly from 0 to 1 and then falls linearly back to 0. In particular, it maps the whole interval onto itself, so it can be applied repeatedly without leaving its stated domain.
Worked Example: Evaluating One Fold
Evaluate \(T(x)\) at \(x=0,\frac14,\frac12,\frac34,1\). The ReLU terms give
The term \(2\sigma(x-1)\) is zero at all five points, including \(x=1\). The values rise from 0 to 1 and then fall to 0, as required for a tent map.
How Many Linear Regions Do Repeated Folds Create?
For a continuous piecewise-affine function on \([0,1]\), a linear region means a maximal interval on which the function is affine. The number of regions counts the intervals between genuine changes in slope; a point where the formula happens to be written differently does not create a new region unless the slope changes.
Proof. The identity map \(T^0(x)=x\) has one region, maps \([0,1]\) onto \([0,1]\), and has slope of magnitude 1. Suppose \(T^L\) has the stated properties on \(2^L\) intervals. On any such interval, it maps monotonically and affinely from one endpoint of \([0,1]\) to the other. There is therefore exactly one interior point at which its value is \(\frac12\). Composing with \(T\) splits that interval at this point into two intervals: on each, \(T\circ T^L\) is affine and maps onto \([0,1]\). The magnitude of the slope doubles, because each branch of \(T\) has slope magnitude 2. Thus \(T^{L+1}\) has \(2\cdot 2^L=2^{L+1}\) regions, and slope magnitude \(2\cdot 2^L=2^{L+1}\) on each. The induction proves the result. Adjacent slopes have opposite signs, so each boundary between successive intervals is a genuine change in slope. \(\square\)
This region count is exact. It is not just an upper bound based on possible breakpoints: every fold creates a new midpoint on each existing affine interval, and all the resulting boundaries remain genuine corners.
Worked Example: Counting Regions After Three Folds
For \(L=3\), the theorem gives \(2^3=8\) regions. Their endpoints are \(j/8\), for \(j=0,\ldots,8\). The function values at these points alternate between 0 and 1:
Each of the eight intervals has width \(1/8\) and maps onto an interval of height 1. Its slope therefore has magnitude \(1/(1/8)=8\). The signs alternate as the graph rises and falls, giving four rising and four falling pieces. The endpoints and slope calculation agree with the theorem’s region count.
A Constant-Width Network for the Folded Function
The same recursion that defines \(T^L\) gives a network realization. Given a scalar input \(z\) to one fold, a layer of three ReLU units computes \(\sigma(z)\), \(\sigma(z-\frac12)\), and \(\sigma(z-1)\). An affine combination of those outputs gives \(T(z)\). Feed that scalar output into the next three-unit layer and repeat.
Consequently, \(T^L\) is represented exactly on \([0,1]\) by a ReLU network with \(L\) hidden layers of width 3 and an affine output. Its width is fixed as \(L\) grows, even though its number of linear regions is \(2^L\). This construction counts regions created by this particular function; it does not assert that every network of the same size has exactly that many.
Why a Shallow Network Needs More Width
The iterated tent maps form a family of oscillatory targets. Their values alternate between 0 and 1 on a fine, equally spaced grid. A single hidden layer must have enough units to make that many changes around the threshold \(\frac12\).
Proof. A one-hidden-layer network has the form \(h(x)=b+\sum_{j=1}^{W}a_j\sigma(w_jx+c_j)\). Each nonconstant hidden unit can change its affine formula at most once on the real line. The union of the resulting breakpoints divides \([0,1]\) into at most \(W+1\) intervals on which \(h\) is affine.
At the grid points \(x_j=j/N\), for \(j=0,\ldots,N\), the values \(T^L(x_j)\) alternate between 0 and 1. The strict approximation error bound implies that \(h(x_j)<\frac12\) when \(T^L(x_j)=0\), and \(h(x_j)>\frac12\) when \(T^L(x_j)=1\). Thus the values of \(h-\frac12\) have alternating signs at these \(N+1\) ordered points. By continuity, there is a threshold crossing in each of the \(N\) disjoint open intervals \((x_j,x_{j+1})\).
A piecewise-affine function with \(R\) affine regions can have at most \(R\) such sign changes in order: on each region its difference from the threshold is affine, so it cannot change sign more than once there; a region on which it equals the threshold contributes no additional sign changes. Hence \(R\ge N\). Since \(R\le W+1\), we obtain \(W+1\ge 2^L\), or \(W\ge 2^L-1\). \(\square\)
The approximation tolerance matters. The argument uses an error strictly below \(\frac12\), which forces the approximating network to preserve whether each grid value lies above or below the threshold. For a larger error, that alternating-sign conclusion need not hold.
Worked Example: A Lower Bound for Approximating \(T^4\)
Here \(N=2^4=16\), so the target has 16 affine regions and 17 alternating grid values at \(j/16\). Suppose a one-hidden-layer network approximates \(T^4\) uniformly with error less than \(\frac12\). It must lie below \(\frac12\) at each even-indexed grid point and above \(\frac12\) at each odd-indexed one, or vice versa.
That creates 16 threshold crossings between successive grid points. A width-\(W\) one-hidden-layer network has at most \(W+1\) affine regions, so \(W+1\ge16\), giving \(W\ge15\). By contrast, four width-3 hidden layers represent \(T^4\) exactly. The comparison is between an exact deep representation and a lower bound for shallow approximation under the stated error tolerance.
Worked Example: Reading the Tradeoff at Different Depths
For \(L=2\), the target \(T^2\) has \(2^2=4\) linear regions, with slope magnitude 4 on each. It is represented exactly using two width-3 hidden layers. Any one-hidden-layer network that approximates it with uniform error less than \(\frac12\) must have width at least \(2^2-1=3\).
For \(L=5\), the same calculations give \(2^5=32\) regions, slope magnitude 32, and a shallow width lower bound of \(2^5-1=31\). The deep construction still uses width 3, now across five hidden layers. The region count grows exponentially in depth, while the proved shallow width requirement grows with the number of alternating target values.
What the Construction Does—and Does Not—Show
Repeated folding gives an explicit mechanism for representing certain oscillatory functions efficiently with depth. The target family \(T^L\) is especially suited to the mechanism: each fold reproduces the same shape on smaller intervals. For this family, the network size in depth and width stays controlled while the number of affine pieces becomes exponential in the number of folds.
The result is not a universal approximation guarantee for arbitrary high-frequency functions. The shallow lower bound is also specific: it applies to one hidden layer, the target \(T^L\), and uniform error strictly below \(\frac12\). Different target shapes, error criteria, or architectures require their own analysis.
Common mistake: “The network has \(L\) layers, so it has only \(L\) linear regions.” This confuses layer count with the number of regions of the composed function. Each fold splits every existing region into two, so the count follows \(1,2,4,8,\ldots,2^L\), not \(1,2,\ldots,L\). Another mistake is to infer that exponential region count alone proves good approximation of any target; here the advantage follows from the specific alternating structure of the tent-map family.
Check Your Understanding
Use the definitions and arguments above to answer these questions.
- What are the two affine formulas for \(T\) on \([0,\frac12]\) and \([\frac12,1]\), and what are their slopes?
- How many linear regions does \(T^6\) have, and what is the magnitude of its slope on each region?
- Why does composing \(T\) with a function that maps an interval monotonically onto \([0,1]\) split that interval into two regions?
- For \(T^5\), what lower bound on the width of a one-hidden-layer network follows from uniform error strictly below \(\frac12\)?
- Why does the shallow-network lower bound not, by itself, establish an approximation advantage for every oscillatory target?