Depth-Width Tradeoffs In Function Approximation

Why Compare Depth and Width?

An approximation bound is only part of an architecture choice. Two networks can attain the same error with very different numbers of hidden layers, maximum layer sizes, and total hidden units. Depth can let a network reuse a small operation many times; a shallow network may instead need many units in parallel. The tradeoff depends on the target and the construction, so it is important to compare explicit budgets rather than treat depth as an automatic advantage.

This tutorial compares ReLU spline approximations with constructions based on the multiplication module established in the earlier material on ReLU networks for multiplication. The comparison is for particular targets and explicit upper bounds. It is not a general lower bound for shallow networks, nor does it say that every deeper architecture is more efficient.

We use the following form of the multiplication approximation result from the earlier material: there is a constant \(C\) such that, for every \(0<\delta\leq 1\), a ReLU network \(M_\delta\) approximates \(uv\) uniformly on \([-2,2]^2\) with error at most \(\delta\), has width bounded by a constant, and has depth and size at most \(C(1+\log(1/\delta))\). The added \(1\) is important: at \(\delta=1\), a zero-unit bound would not describe a valid multiplication approximation. We use the module as a building block, keeping track of the range of every input passed to it.

A Shallow Baseline: Piecewise-Linear Approximation

Let \(f\) be twice continuously differentiable on \([a,b]\), with \(|f''(x)|\leq M\). Divide the interval into \(N\) equal subintervals and linearly interpolate \(f\) at the \(N+1\) endpoints. On a subinterval \([u,v]\) of length \(h=(b-a)/N\), the interpolation error satisfies

For the first inequality, when \(x\) is interior to \([u,v]\), the interpolation remainder formula gives \(f(x)-L(x)=f''(\xi)(x-u)(x-v)/2\) for some \(\xi\in(u,v)\). The endpoints have zero error. The second inequality follows because \(|(x-u)(x-v)|\leq h^2/4\). Thus \(N\geq \sqrt{M(b-a)^2/(8\varepsilon)}\) suffices for uniform error at most \(\varepsilon\).

A continuous piecewise-linear function with knots \(t_1,\ldots,t_{N-1}\) can be represented as an affine function plus a weighted sum of \(\sigma(x-t_j)\), where \(\sigma(z)=\max\{z,0\}\). The coefficient of each ReLU term is the change in slope at that knot. Hence this interpolant is represented by a one-hidden-layer network with \(N-1\) hidden units.

Composing Multiplication Modules to Build Powers

A multiplication module can be reused to form powers. The key is to control how local errors accumulate and to check that approximate intermediate values stay in the module’s input range.

Proof. The claim holds for \(k=1\): \(q_1=x\), so its error is zero and \(q_1\in[-1,1]\). Suppose it holds at \(k\). Then \(q_k\in[-2,2]\), and \(x\in[-1,1]\subset[-2,2]\), so the multiplication module applies. Its error guarantee gives

Also, \(|q_{k+1}|\leq |x|^{k+1}+k\eta\leq1+m\eta\leq2\). Induction proves both claims. \(\square\)

A Smooth Target: From Taylor Approximation to a Network

For a smooth function, a deep construction can combine two savings: a polynomial may approximate the target rapidly, and a multiplication-based network can evaluate that polynomial using controlled intermediate errors. We work through \(f(x)=\sin x\) on \([-1,1]\). This target is infinitely differentiable, and every derivative has absolute value at most one.

Let \(P_m(x)=\sum_{k=0}^{m}a_kx^k\) be the Taylor polynomial of \(\sin x\) at zero, with \(m\) odd. Taylor’s theorem with remainder gives

Choose an odd \(m\) for which \((m+1)!\geq2/\varepsilon\); the Taylor error is then at most \(\varepsilon/2\). To evaluate the polynomial, construct approximate powers \(q_k\) as in the lemma and form \(\widetilde P_m(x)=\sum_{k=0}^{m}a_kq_k(x)\), taking \(q_0=1\). Because the nonzero coefficients have absolute values \(1/k!\), the power errors obey

Set \(\eta=\varepsilon/(4e)\), and require \(m\eta\leq1\), as needed for the lemma. Then the network’s polynomial-evaluation error is less than \(\varepsilon/4\). Combined with the Taylor error, its total error is less than \(3\varepsilon/4\), hence at most \(\varepsilon\). For sufficiently small \(\varepsilon\), the condition \(m\eta\leq1\) holds for the least odd \(m\) meeting the factorial condition.

For the budget, compute each power \(q_k\) along a chain of \(k-1\) multiplication modules. These chains can run in parallel; there are at most \(m\) active modules at a stage. With constant-width modules, the resulting network has width \(O(m)\), depth \(O(m(1+\log(1/\eta)))\), and size \(O(m^2(1+\log(1/\eta)))\). Here \(O(\cdot)\) hides constants independent of \(m\) and \(\varepsilon\); carrying the inputs and combining the polynomial terms is included in these bounds. The factorial condition allows \(m\) to grow much more slowly than \(\varepsilon^{-1/2}\), so these construction budgets can be far smaller than the one-hidden-layer spline budget for this target.

What the Tradeoff Does—and Does Not—Say

The examples show one mechanism by which depth can reduce the number of units: a small nonlinear module is reused to build a more complicated expression. For \(x^4\), repeated multiplication gives a logarithmic-in-accuracy size bound, compared with the \(\varepsilon^{-1/2}\) size of the stated spline construction. For sine, Taylor approximation followed by power construction gives a deep upper bound that grows slowly with increasing accuracy. The benefits depend on targets having useful algebraic or smooth structure.

These are approximation constructions, not universal architecture rankings. The spline calculation gives a sufficient shallow budget, not a lower bound for every one-hidden-layer network. Conversely, the deep bounds rely on the multiplication module, input-range control, and permitted depth. Constants, constraints on weights, connectivity, or training may change practical comparisons. A rigorous comparison must specify the target, error norm, domain, and which resource—depth, width, or total units—is being counted.

Common Pitfall

A common mistake is to say, “The deep network has logarithmic size, so it is always more efficient.” That conclusion does not follow. The logarithmic bound above applies to a specific construction on a specified domain, and the multiplier’s constant and architectural assumptions matter. Also, an error guarantee for each multiplication cannot simply be quoted without checking that approximate intermediate values remain in the multiplier’s domain. The power lemma supplies that check; the fourth-power example verifies it directly.