Compositional Function Classes And Deep Approximation

Why the Structure of a Function Matters

A function of many variables need not use all of those variables in one complicated operation. It may instead combine small groups of inputs, then combine the resulting intermediate quantities. If each local operation is smooth and has few inputs, approximating those operations separately can avoid paying the approximation cost associated with the full ambient dimension at every stage.

The central issue is how local approximation errors accumulate. An error introduced early in a composition can be amplified by later maps, while a small error in the final map is not amplified at all. We will make this dependence explicit and then translate local approximation rates into a bound for the full network.

Compositional Classes and Network Budgets

Definition: Let $g_j:\mathcal X_{j-1}\to\mathcal X_j$, for $j=1,\ldots,L$, be maps between subsets of finite-dimensional spaces. Their composition is $$ F=g_L\circ g_{L-1}\circ\cdots\circ g_1. $$ The quantity $d_{j-1}$, the dimension of the input to $g_j$, is its local input dimension. It can be much smaller than the ambient input dimension of $F$.

For vectors, use the maximum norm $\|x\|_\infty=\max_i|x_i|$. Suppose each $g_j$ is Lipschitz on its domain: for some $A_j\geq 0$, $$ \|g_j(u)-g_j(v)\|_\infty\leq A_j\|u-v\|_\infty. $$ We also assume that the intermediate exact outputs lie in the domains where the next maps and their approximation guarantees apply. The maps may take values in compact boxes other than the unit cube.

A local network approximation guarantee specifies that a ReLU network with budget $W_j$ approximates $g_j$ uniformly to error at most $\varepsilon_j$. Here a budget may count nonzero parameters; the same accounting convention must be used for every local guarantee. A sequential composition of these networks has depth at most the sum of their depths. Its parameter count is at most the sum of their parameter counts, apart from any fixed overhead needed to keep intermediate outputs in the prescribed domains.

Worked Example: Pairwise Products in Eight Variables

Let $x\in[0,1]^8$, and define $$ F(x)=\frac{1}{4}\sum_{k=1}^{4}x_{2k-1}x_{2k}. $$ The first map $g_1:[0,1]^8\to[0,1]^4$ computes the four pairwise products, and the second map $g_2:[0,1]^4\to[0,1]$ averages them. Thus $F=g_2\circ g_1$.

Suppose each coordinate product has a local network approximation with uniform error at most $0.01$, and $g_2$ is represented exactly as an affine map. If the four product errors are $e_1,\ldots,e_4$, where $|e_k|\leq0.01$, then $$ |\widehat F(x)-F(x)|=\left|\frac{1}{4}\sum_{k=1}^{4}e_k\right| \leq\frac{1}{4}\sum_{k=1}^{4}|e_k| \leq 0.01. $$ Each nonlinear local operation has only two inputs, although $F$ is a function of eight variables. A rate based on approximating a general smooth function directly in eight dimensions would not reflect this structure.

Error Propagation Through the Composition

To compose approximations safely, we need their outputs to remain in the domains on which the next stage is controlled. If those domains are boxes, coordinatewise clipping provides a simple device. For the unit interval, the function $$ c(t)=\operatorname{ReLU}(t)-\operatorname{ReLU}(t-1) $$ equals $0$ for $t<0$, $t$ for $0\leq t\leq1$, and $1$ for $t>1$. It is 1-Lipschitz and can be represented exactly by a small ReLU network. Clipping to a box is done coordinatewise. If the target value lies in the box, clipping cannot increase its distance from that value.

Theorem (composition error bound): Suppose $g_j:\mathcal X_{j-1}\to\mathcal X_j$ is $A_j$-Lipschitz for $j=1,\ldots,L$. Suppose the clipped local network $\widetilde g_j$ satisfies $$ \sup_{u\in\mathcal X_{j-1}}\|\widetilde g_j(u)-g_j(u)\|_\infty\leq\varepsilon_j $$ and takes values in $\mathcal X_j$. Then the composed approximation $\widetilde F=\widetilde g_L\circ\cdots\circ\widetilde g_1$ obeys $$ \sup_{x\in\mathcal X_0}\|\widetilde F(x)-F(x)\|_\infty \leq \sum_{k=1}^{L}\varepsilon_k\prod_{r=k+1}^{L}A_r, $$ where an empty product is $1$.

Proof. Fix an input $x$. Define the exact intermediate values $x_0=x$, $x_j=g_j(x_{j-1})$, and the approximate values $z_0=x$, $z_j=\widetilde g_j(z_{j-1})$. Put $e_j=\|z_j-x_j\|_\infty$, so $e_0=0$. By adding and subtracting $g_j(z_{j-1})$, then applying the local approximation bound and the Lipschitz property, $$ e_j\leq\|\widetilde g_j(z_{j-1})-g_j(z_{j-1})\|_\infty+ \|g_j(z_{j-1})-g_j(x_{j-1})\|_\infty \leq\varepsilon_j+A_je_{j-1}. $$ Repeated substitution gives $$ e_L\leq\varepsilon_L+A_L\varepsilon_{L-1} +A_LA_{L-1}\varepsilon_{L-2}+\cdots+ \left(\prod_{r=2}^{L}A_r\right)\varepsilon_1. $$ This is the claimed bound for the fixed $x$; taking the supremum over $x$ proves the result. $\square$

Worked Example: A Three-Stage Error Calculation

Consider the scalar maps $g_1(x)=2x$, $g_2(u)=u/2$, and $g_3(v)=3v$. Their Lipschitz constants are $A_1=2$, $A_2=1/2$, and $A_3=3$. At $x=0.4$, the exact intermediate values are $x_1=0.8$, $x_2=0.4$, and $F(x)=1.2$.

Suppose the approximating stages are $\widetilde g_1(u)=2u+0.01$, $\widetilde g_2(u)=u/2+0.02$, and $\widetilde g_3(u)=3u+0.005$, so their local errors are $\varepsilon_1=0.01$, $\varepsilon_2=0.02$, and $\varepsilon_3=0.005$. The approximate calculation gives $z_1=0.81$, $z_2=0.425$, and $z_3=1.28$. The actual final error is $1.28-1.2=0.08$.

The theorem gives the same bound: $$ \varepsilon_3+A_3\varepsilon_2+A_3A_2\varepsilon_1 =0.005+3(0.02)+3(0.5)(0.01)=0.08. $$ The first-stage error is multiplied by the Lipschitz constants of both later stages; the last-stage error is not amplified.

From Local Smoothness to a Compositional Rate

The theorem separates two questions: how well each component can be approximated, and how its error propagates. For a component with $d_{j-1}$ inputs and smoothness $s_j$, a typical local ReLU approximation guarantee has the form $$ \varepsilon_j\leq C_j W_j^{-\alpha_j}, \qquad \alpha_j=\frac{s_j}{d_{j-1}}, $$ up to constants or logarithmic factors specified by the particular local approximation result. This is the familiar smooth-function approximation scaling with the dimension of the function being approximated. Here we use it as a local guarantee, rather than assuming it applies automatically to every architecture or smoothness class.

Substitution into the composition theorem yields $$ \|\widetilde F-F\|_\infty \leq \sum_{j=1}^{L} C_jW_j^{-\alpha_j}\prod_{r=j+1}^{L}A_r. $$ The bound depends on each stage’s local input dimension through $\alpha_j$, not on the total number of inputs treated as if every stage were one unrestricted map.

Corollary (equal local exponents): Suppose $\alpha_j=\alpha>0$ for all $j$, and $C_j$ and $A_j$ are fixed. If $W$ is a total budget allocated across $L$ components, choosing budgets of order $W/L$ gives $$ \|\widetilde F-F\|_\infty \leq \left(\sum_{j=1}^{L}C_j\prod_{r=j+1}^{L}A_r\right) \left(\frac{W}{2L}\right)^{-\alpha} $$ for $W\geq 2L$, ignoring fixed clipping overhead.

Derivation. Choose integer budgets $W_j$ whose sum is at most $W$ and for which $W_j\geq W/(2L)$, possible when $W\geq2L$ after distributing the budget as evenly as possible. Then $W_j^{-\alpha}\leq(W/(2L))^{-\alpha}$ for every $j$. Apply this inequality term by term in the preceding error bound and factor out the common power. This proves the stated bound. $\square$

When local exponents differ, the slowest local rate can govern an equal-allocation guarantee: for $W_j$ of order $W/L$, each term has exponent $\alpha_j$, and the smallest exponent decays most slowly as $W$ grows. A more tailored allocation can improve constants, but it cannot erase the need to approximate a difficult component.

Worked Example: A Two-Variable Operation Inside a Twenty-Variable Input

Let $x\in[0,1]^{20}$, and define $$ F(x)=\sin\left(\frac{\pi}{2}\frac{x_1+x_2}{2}\right). $$ The first component computes $g_1(x)=(x_1+x_2)/2$; the second computes $g_2(u)=\sin(\pi u/2)$. The other 18 coordinates do not affect the target.

On $[0,1]$, $g_2$ has Lipschitz constant $A_2=\pi/2$, since $|g_2'(u)|=(\pi/2)|\cos(\pi u/2)|\leq\pi/2$. Suppose local approximations have errors $\varepsilon_1=0.01$ and $\varepsilon_2=0.005$. The composition bound is $$ \|\widetilde F-F\|_\infty \leq 0.005+\frac{\pi}{2}(0.01) \approx 0.02071. $$ The first operation has only two inputs and the second has one. A rate based solely on a generic twenty-dimensional target would miss the fact that the function uses just two coordinates through two low-dimensional stages.

When the Dimension Advantage Applies

Compositional structure helps when the component maps really do have small input dimensions and their local smoothness and Lipschitz constants are controlled. It does not guarantee a dimension-free approximation rate. A component may itself depend on many inputs, may have poor smoothness, or may have a large Lipschitz constant that amplifies earlier errors. The error formula makes each of these limitations visible.

A common mistake is to see that a target is written as a composition and conclude that its approximation error is simply the sum of the local errors. That omits the effect of downstream sensitivity. For example, if a later stage has Lipschitz constant $10$, an error of $0.01$ introduced before that stage can contribute as much as $0.1$ to the final error. The correction is to weight each local error by the product of the Lipschitz constants of all later stages, as in the theorem.

A second caution is about comparing rates: a local rate $W_j^{-s_j/d_{j-1}}$ is not a universal formula independent of the approximation theorem’s assumptions. The smoothness class, activation, architecture, norm, and any logarithmic factors matter. The compositional argument begins once valid local guarantees are available; it does not replace their hypotheses.

Key takeaway: Approximate each component using its own input dimension, then propagate its error through the remaining maps. Compositional structure can reduce the dimensional burden of approximation, while Lipschitz amplification and difficult local components determine how much of that advantage survives.

Check Your Understanding

Use the error-propagation formula and the local dimensions to answer these questions.

For a two-stage composition with $A_2=4$, $\varepsilon_1=0.01$, and $\varepsilon_2=0.02$, what final error bound does the theorem give?
Why does clipping a local approximation to a box containing the true output not increase its distance from that output?
If two components have local input dimensions 2 and 10 and the same smoothness $s$, which local rate exponent $s/d$ is larger, and why does that matter?
In what situation can a small first-stage approximation error still produce a large final error?
Does writing a target as a composition alone establish a dimension advantage? State two additional properties that affect the bound.