Depth Separation Through Approximation Error

Approximation error as a measure of depth separation

A deep network is useful for a compositional target when its layers can approximate successive parts of that target without paying the full cost of approximating the entire input-output map at once. But this observation by itself is not a depth-separation result. To establish separation, one must compare approximation errors at a common network size, or compare the sizes needed to reach a common error. In particular, an upper bound for deep networks does not show that shallow networks need more parameters: that conclusion requires a shallow approximation lower bound for the same target family.

We make that comparison precise using uniform approximation error. The discussion concerns ReLU networks, whose activation is $\sigma(t)=\max\{t,0\}$. A network's size will mean its number of nonzero parameters, including nonzero weights and biases. Its depth is the number of affine transformations in sequence. These choices matter: a size comparison is meaningful only after the size measure and the allowed architectures have been specified.

Definition: Let $\mathcal F$ be a class of real-valued functions on a domain $\Omega$, and let $\mathcal A_N$ be a specified architecture class of networks with at most $N$ nonzero parameters. Its worst-case uniform approximation error is $$ E_N(\mathcal F,\mathcal A) = \sup_{f\in\mathcal F}\; \inf_{g\in\mathcal A_N}\|f-g\|_{\infty,\Omega}, \qquad \|h\|_{\infty,\Omega}=\sup_{x\in\Omega}|h(x)|. $$ A deep-versus-shallow comparison uses two such classes, with their depth restrictions stated explicitly. The supremum makes this a guarantee for every function in $\mathcal F$, not merely a good approximation to one selected member.

For a compositional class, members have a form such as $f=g_L\circ\cdots\circ g_1$, where each $g_j$ maps one intermediate representation to the next. A deep network can approximate the component maps in sequence. The following error bound explains how local approximation errors accumulate. It does not presume that the resulting network is smaller than every shallow alternative; that further claim needs a lower bound.

Error propagation through a composition

Theorem: Let $g_j:\mathbb R^{d_{j-1}}\to\mathbb R^{d_j}$, for $1\le j\le L$, be maps defined on sets containing all intermediate points under consideration. Suppose $g_j$ is Lipschitz with constant $K_j$, meaning $\|g_j(u)-g_j(v)\|\le K_j\|u-v\|$. Suppose approximations $\widetilde g_j$ satisfy $\sup_u\|g_j(u)-\widetilde g_j(u)\|\le\delta_j$ on those sets, and the intermediate values of both compositions remain in the sets where these bounds hold. Then $$ \|g_L\circ\cdots\circ g_1-\widetilde g_L\circ\cdots\circ\widetilde g_1\|_{\infty} \le \sum_{j=1}^{L}\delta_j\prod_{k=j+1}^{L}K_k, $$ where an empty product equals $1$.

Proof. Fix an input $x$. Let $z_0=\widetilde z_0=x$, $z_j=g_j(z_{j-1})$, and $\widetilde z_j=\widetilde g_j(\widetilde z_{j-1})$. The triangle inequality and the Lipschitz condition give $$ \|z_j-\widetilde z_j\| \le \|g_j(z_{j-1})-g_j(\widetilde z_{j-1})\| +\|g_j(\widetilde z_{j-1})-\widetilde g_j(\widetilde z_{j-1})\| \le K_j\|z_{j-1}-\widetilde z_{j-1}\|+\delta_j. $$ Starting with $\|z_0-\widetilde z_0\|=0$, apply this inequality successively. For $j=1$, the bound is $\|z_1-\widetilde z_1\|\le\delta_1$. If the bound through stage $j-1$ is $\sum_{r=1}^{j-1}\delta_r\prod_{k=r+1}^{j-1}K_k$, multiplying by $K_j$ and adding $\delta_j$ gives $\sum_{r=1}^{j}\delta_r\prod_{k=r+1}^{j}K_k$. At $j=L$ this is the asserted bound. Since it holds for each $x$, taking the supremum proves the result. $\square$

Worked Example: Allocating Error Across Three Layers

Suppose $f=g_3\circ g_2\circ g_1$, with Lipschitz constants $K_2=2$ and $K_3=3$. Assume the first, second, and third component approximations have uniform errors $\delta_1=0.01$, $\delta_2=0.02$, and $\delta_3=0.01$. The first component's error is amplified by both later maps; the second's by the last map; the final error is not amplified.

The theorem gives $$ \|f-\widetilde g_3\circ\widetilde g_2\circ\widetilde g_1\|_\infty \le 0.01(2)(3)+0.02(3)+0.01 =0.06+0.06+0.01 =0.13. $$ Thus, local errors summing to $0.04$ can produce a final error bound of $0.13$. If all three Lipschitz constants were $1$, the same local errors would instead give the bound $0.01+0.02+0.01=0.04$. The layerwise error budget must therefore account for downstream amplification, not merely the number of components.

A rate criterion for depth separation

Write $\mathcal A_N^{\mathrm{deep}}$ and $\mathcal A_N^{\mathrm{shallow}}$ for the permitted deep and shallow network classes with at most $N$ nonzero parameters. The central comparison is between an upper bound for the deep class and a lower bound for the shallow class, both for the same function family and error metric.

Theorem: Let $\mathcal F$ be a function class. Suppose that for constants $C_D,c_S>0$, exponents $\beta>\alpha>0$, and every integer $N\ge1$, $$ E_N(\mathcal F,\mathcal A^{\mathrm{deep}})\le C_D N^{-\beta}, \qquad E_N(\mathcal F,\mathcal A^{\mathrm{shallow}})\ge c_S N^{-\alpha}. $$ Then for every integer $N>(C_D/c_S)^{1/(\beta-\alpha)}$, $$ E_N(\mathcal F,\mathcal A^{\mathrm{deep}}) < E_N(\mathcal F,\mathcal A^{\mathrm{shallow}}). $$ Moreover, for sufficiently small $\varepsilon>0$, the deep class can guarantee error at most $\varepsilon$ with size at most $\lceil(C_D/\varepsilon)^{1/\beta}\rceil$, whereas any shallow size $N$ that guarantees error at most $\varepsilon$ must satisfy $N\ge(c_S/\varepsilon)^{1/\alpha}$.

Proof. Since $\beta>\alpha$, the inequality $N>(C_D/c_S)^{1/(\beta-\alpha)}$ implies $C_DN^{-\beta}<c_SN^{-\alpha}$. Apply the assumed deep upper bound and shallow lower bound to obtain $$ E_N(\mathcal F,\mathcal A^{\mathrm{deep}}) \le C_DN^{-\beta} <c_SN^{-\alpha} \le E_N(\mathcal F,\mathcal A^{\mathrm{shallow}}). $$ For the size statements, $C_DN^{-\beta}\le\varepsilon$ whenever $N\ge(C_D/\varepsilon)^{1/\beta}$, which yields the stated ceiling. Conversely, a shallow guarantee $E_N(\mathcal F,\mathcal A^{\mathrm{shallow}})\le\varepsilon$, together with the lower bound, requires $c_SN^{-\alpha}\le\varepsilon$, or $N\ge(c_S/\varepsilon)^{1/\alpha}$. The ratio of these size scales is proportional to $\varepsilon^{-(1/\alpha-1/\beta)}$, which diverges as $\varepsilon$ decreases to zero because $1/\alpha>1/\beta$. $\square$

This theorem is a rate-comparison criterion, not a claim that the hypotheses hold for every compositional class. In an application, the deep upper bound may be obtained by approximating component maps and controlling their accumulated errors. A separate argument must establish the shallow lower bound for the particular class, domain, norm, and size measure being used. Without that lower bound, one has shown that deep networks can approximate efficiently, but not that shallow networks cannot do so as efficiently.

Worked Example: Translating Two Rates Into Parameter Requirements

Suppose a specified compositional family has the bounds $E_N(\mathcal F,\mathcal A^{\mathrm{deep}})\le 4N^{-1}$ and $E_N(\mathcal F,\mathcal A^{\mathrm{shallow}})\ge \tfrac12N^{-1/2}$. These are assumptions about this family, not universal rates for all compositions. Here $C_D=4$, $c_S=\tfrac12$, $\beta=1$, and $\alpha=\tfrac12$. At a common size, the theorem gives strict separation when $$ N>(4/(1/2))^{1/(1-1/2)}=8^2=64. $$ For example, at $N=100$, the deep error is at most $4/100=0.04$, while the shallow error is at least $\tfrac12/\sqrt{100}=0.05$. Hence the deep worst-case error is strictly smaller at that size.

For target error $\varepsilon=0.01$, the deep sufficient size is $\lceil4/0.01\rceil=400$. The shallow necessary size satisfies $$ N\ge\left(\frac{1/2}{0.01}\right)^2=50^2=2500. $$ The comparison does not say that every deep network of size $400$ achieves error $0.01$, or that every shallow network of size $2499$ fails on every individual function. It says the deep upper bound guarantees the class-wide target at the stated size, while the shallow lower bound rules out that class-wide guarantee below its necessary size.

Using the comparison for compositional classes

For a hierarchical target, the error-propagation theorem supplies one part of the argument: if each component has an efficient network approximation, their composition has a controlled total error. To turn this into a depth advantage, one must also count the parameters used by the component networks and verify that composing them produces a network in the allowed deep class. The error bound and the parameter count are distinct: small local errors do not by themselves imply a small total network.

A useful reasoning sequence is:

Specify the target family.
State the domains and dimensions of the component maps, their regularity or Lipschitz bounds, and the norm in which errors are measured.

Build the deep approximation.
Approximate the components, propagate their errors through the composition, and add the parameter counts using the chosen size convention.

Prove a shallow lower bound.
Show that every allowed shallow network below a stated size has approximation error at least the claimed amount for the same family and norm.

Compare at equal size or equal accuracy.
Apply the rate criterion, keeping constants and exponents visible so the range of the conclusion is explicit.

Worked Example: Checking the Error Budget Before Counting Parameters

Suppose a compositional target has two component maps, each with Lipschitz constant at most $2$. The first approximation has error at most $\delta_1$, and the second has error at most $\delta_2$. The propagation theorem gives the final error bound $2\delta_1+\delta_2$. To guarantee final error at most $0.05$, choosing $\delta_1=0.01$ and $\delta_2=0.03$ works because $$ 2(0.01)+0.03=0.05. $$ Choosing $\delta_1=\delta_2=0.03$ does not: the bound becomes $2(0.03)+0.03=0.09$. Once a valid local error budget is set, one can use component approximation results to determine the parameter count for each accuracy and sum those counts. That calculation gives a deep upper bound; it still does not supply the shallow lower bound required for a separation claim.

Common pitfall: mistaking an upper bound for separation

A common but incorrect argument is: “The compositional structure lets a deep network achieve error at most $C N^{-\beta}$, so deep networks are more efficient than shallow networks.” This only bounds the deep network's error from above. A shallow network might have a still smaller error at the same size, or might achieve the same target with a comparable number of parameters. The correction is to establish a lower bound on shallow approximation error for the same function family and under the same error metric and size convention, then compare the two bounds.

The conclusion is also limited by the class being studied. A worst-case lower bound over $\mathcal F$ does not imply that every $f\in\mathcal F$ is hard for shallow networks. Nor does separation in uniform error automatically imply separation in another norm or in prediction risk. Those require their own approximation bounds. Depth separation through approximation error is therefore a precise comparison between specified architectures and a specified target family, rather than a blanket statement that additional depth always improves approximation.

Key takeaway: A compositional construction can give a deep approximation upper bound by controlling errors layer by layer. A genuine depth-separation result additionally needs a shallow lower bound. When the deep error decays faster in network size, the rate comparison proves both smaller deep error at equal size and a growing size advantage as the target accuracy becomes more stringent.

Check Your Understanding

Use the definitions and rate comparison above to answer the following.

Why does a deep approximation upper bound alone not prove that deep networks outperform shallow networks?
In the composition error bound, why is the error from an early component multiplied by Lipschitz constants of later components?
If the deep and shallow rates are $N^{-1}$ and $N^{-1/2}$, respectively, which exponent is larger, and what does that imply for their size requirements as error tends to zero?
What must be held fixed for a shallow lower bound and a deep upper bound to support a valid comparison?
For two maps with Lipschitz constants $K_2=4$, first-stage error $0.02$, and second-stage error $0.01$, calculate the composition error bound.