Hierarchical Compositions And Network Approximation Rates

Why the Structure of a Composition Matters

A smooth function of many variables can be difficult to approximate when its input dimension is large. But some high-dimensional targets are built from a hierarchy of simpler functions: small groups of variables are combined first, and their outputs are combined at later stages. In that setting, each local function may have far fewer inputs than the final target has variables. Approximation can exploit this structure by approximating the local functions and composing the resulting networks.

The key issue is error propagation. A local approximation error introduced near the leaves can be magnified by functions higher in the tree. A useful rate therefore needs to account both for the number and smoothness of the local functions and for how strongly errors are propagated through the composition.

Tree-Structured Compositions

Definition: A tree-structured composition is a scalar-valued function represented by a rooted tree. Each leaf supplies one input coordinate $x_j$, and each internal node $v$ applies a scalar function $g_v$ to the outputs of its children. The function at the root is the target $f$. Write $M$ for the number of internal nodes, $r_v$ for the number of children of node $v$, and $D$ for the largest number of internal nodes on a path from a leaf to the root.

For example, a node with two children applies a bivariate function to two intermediate values. The local input dimension at that node is two, even if its descendants collectively depend on hundreds of original coordinates. We take all leaf values and all node outputs to lie in $[0,1]$, so each local function has domain and range in the appropriate unit cube or interval.

Assume each $g_v:[0,1]^{r_v}\to[0,1]$ is Lipschitz with constant $L_v$ in the sup norm: for all $z,z'\in[0,1]^{r_v}$, $ |g_v(z)-g_v(z')|\le L_v\|z-z'\|_\infty $. Assume also that the local functions belong to Hölder balls of common smoothness $s>0$ and radius at most $A$. For noninteger $s=m+\alpha$, with integer $m\ge0$ and $0<\alpha<1$, this means that derivatives through order $m$ are bounded and the derivatives of order $m$ are $\alpha$-Hölder continuous. For integer $s$, take the usual class with bounded derivatives through order $s$.

The Local Approximation Input

The local approximation result we need is the ReLU approximation bound for Hölder functions. We state it explicitly to make its role in the composition argument clear. For each fixed input dimension $r$, smoothness $s$, and radius $A$, there is a constant $C_{r,s,A}$ such that every $g$ in the corresponding Hölder ball has a ReLU network $g_\eta$ satisfying

\|g-g_\eta\|_\infty\le \eta, \qquad \operatorname{size}(g_\eta) \le C_{r,s,A}\eta^{-r/s}\log(2/\eta), \qquad 0<\eta\le \frac12.

Here size counts nonzero network parameters. We use this established local rate rather than deriving it again. Its important feature for hierarchical targets is the exponent $r/s$: it depends on the dimension of the local function, not automatically on the total number of leaves in the tree. The restriction $\eta\le1/2$ will matter when we choose a local accuracy below.

Propagating Local Errors Through the Tree

For an internal node $v$, let its strict ancestors be the internal nodes on the path from $v$ to the root, excluding $v$ itself. Define the propagation weight $w_v=\prod_{a\text{ a strict ancestor of }v}L_a$, with an empty product equal to one. Thus the root has weight one. Set $S=\sum_v w_v$, summing over internal nodes. This quantity records the total possible amplification of local errors at the root.

Theorem: Suppose the tree has $M$ internal nodes, and each local function satisfies the Lipschitz and Hölder assumptions above. Let $r=\max_v r_v$, and let $C$ be a constant uniform over the local Hölder balls and all dimensions $r_v\le r$. For any $0<\varepsilon\le1$, there is a ReLU network approximating the root function uniformly to error at most $\varepsilon$, with size bounded by $$ C M\left(\frac{S}{\varepsilon}\right)^{r/s} \log\left(\frac{2S}{\varepsilon}\right). $$

To apply local networks to approximate child outputs, their outputs must remain in $[0,1]$, the domain of the next local function. If a local network output falls outside this interval, compose it with the clipping map $c(t)=\min\{1,\max\{0,t\}\}$. This map is exactly representable with a constant number of ReLU units, is 1-Lipschitz, and does not increase the approximation error to a target value in $[0,1]$.

Control the root error.
At a node $v$, the local approximation contributes at most its own error, plus the Lipschitz constant $L_v$ times the largest error among its children. Repeated substitution shows that the root error is at most $\sum_v w_v\eta_v$, where $\eta_v$ is the local error at node $v$.

Choose a valid common tolerance.
Set $\delta=\min\{\varepsilon/S,\,1/2\}$ and use $\eta_v=\delta$ at every internal node. Then $\sum_v w_v\eta_v=S\delta\le\varepsilon$, and the local approximation result applies because $0<\delta\le1/2$.

Add the local network sizes.
Each node costs at most $C\delta^{-r/s}\log(2/\delta)$, since $r_v\le r$ and $\delta\le1$. Concatenating the $M$ local networks therefore costs at most $CM\delta^{-r/s}\log(2/\delta)$, up to constant-size routing and clipping operations per node.

Express the bound using $S/\varepsilon$.
Write $A_0=S/\varepsilon$. Since $S\ge1$ and $\varepsilon\le1$, $A_0\ge1$. If $A_0\ge2$, then $\delta=1/A_0$. If $1\le A_0<2$, then $\delta=1/2$, so $\delta^{-r/s}\le 2^{r/s}A_0^{r/s}$ and $\log(2/\delta)=\log4\le2\log(2A_0)$. In either case the claimed bound follows after increasing $C$ by a constant depending only on $r/s$.

For completeness, the error expansion in Step 1 follows by induction up the tree. If $E_v$ is the error at node $v$, and $v_1,\ldots,v_k$ are its children that are internal nodes, Lipschitz continuity gives $E_v\le\eta_v+L_v\max_i E_{v_i}\le\eta_v+L_v\sum_i E_{v_i}$. Expanding this inequality from the root downward assigns coefficient one to the root error $\eta_{\text{root}}$, coefficient $L_{\text{root}}$ to each internal child error, and, in general, coefficient equal to the product of the Lipschitz constants at the strict ancestors of each node. These are exactly the weights $w_v$. Thus the root error is bounded by $\sum_v w_v\eta_v$, as used above. $\square$

Turning Depth into a Simpler Bound

The propagation sum $S$ gives the most informative version of the theorem when local Lipschitz constants are known. A simpler bound follows if every $L_v\le L$. Define $\Lambda=\max\{1,L\}$. Each node has at most $D$ strict ancestors, so $w_v\le\Lambda^D$, and therefore $S\le M\Lambda^D$. Substitution gives

\operatorname{size} \le C M\left(\frac{M\Lambda^D}{\varepsilon}\right)^{r/s} \log\left(\frac{2M\Lambda^D}{\varepsilon}\right).

This bound makes the roles of tree size, depth, local dimension, and accuracy explicit. It is an upper bound, and can be conservative: the actual $S$ may be much smaller than $M\Lambda^D$, especially when many nodes have short paths or their ancestors are strongly contractive.

Worked Example: Choosing Local Accuracy Without Exceeding Its Range

Consider a single internal node with $L=0$, a one-dimensional input, smoothness $s=1$, and target error $\varepsilon=1$. Its propagation sum is $S=1$, so $\varepsilon/S=1$. The local approximation result, however, is stated only for tolerances at most $1/2$. The valid common tolerance is $ \delta=\min\{1/1,1/2\}=1/2 $.

The root error is at most $\delta=1/2$, which is no greater than the requested error $1$. The local size bound is $C(1/2)^{-1}\log(2/(1/2))=2C\log4$. In the theorem's stated form, the bound is $C(1/1)\log2$; these differ only by a fixed factor, which is absorbed into the theorem's constant. The cap at $1/2$ is what makes the use of the local result valid.

Worked Example: A Chain With Error Amplification

Suppose a tree has two internal nodes: a lower node $u$ followed by a root $v$. Let $L_v=3$, so an error at $u$ can be amplified by a factor of three at the root. The weights are $w_v=1$ and $w_u=3$, giving $S=4$. For target error $\varepsilon=0.08$, the common local tolerance is $ \delta=\min\{0.08/4,1/2\}=0.02 $.

If each local function is one-dimensional and has smoothness $s=1$, the local size bound at each node is $C(1/0.02)\log(2/0.02)=50C\log100$. The two-node network therefore has size at most $100C\log100$. Its propagated root error is at most $ w_v\delta+w_u\delta=1(0.02)+3(0.02)=0.08 $, exactly the target bound. Giving the lower node the same tolerance as the root without accounting for $L_v=3$ would not provide this guarantee.

Worked Example: A Balanced Binary Composition

Take a complete binary tree with three internal levels. It has $M=1+2+4=7$ internal nodes and eight leaves. Suppose every local function is bivariate, has smoothness $s=1$, and has Lipschitz constant at most $2$. The root-level nodes have weights $1$, the two nodes one level below have weights $2$, and the four lowest internal nodes have weights $4$. Hence $S=1+2(2)+4(4)=21$.

For $\varepsilon=0.05$, the common local tolerance is $\delta=0.05/21=1/420$, which is below $1/2$. Each bivariate local approximation costs at most $C(420)^2\log(840)$. Adding the seven local networks gives the bound $7C(420)^2\log(840)$, approximately $8.31\times10^6 C$ using the natural logarithm. The total target has eight inputs, but the exponent in this bound uses local dimension two, not dimension eight.

Why Hierarchy Can Improve the Rate

The exponent in the local rate is governed by the largest local dimension $r$. For fixed smoothness, replacing a direct approximation in $d$ variables with local approximations in small groups can substantially reduce the accuracy exponent. The improvement is most useful when the target genuinely has a compositional representation with regular local functions; the tree structure alone does not guarantee that an arbitrary high-dimensional function can be represented this way.

For a complete binary tree with $d$ leaves, $r=2$, and bounded Lipschitz constants, the simple bound has a dependence on accuracy of order $\varepsilon^{-2/s}$, apart from the displayed factors involving $M$, depth, and logarithms. A direct Hölder approximation in $d$ variables instead has an accuracy exponent $d/s$. This comparison concerns approximation classes and their assumptions: it does not assert that every function on $[0,1]^d$ has a smooth binary-tree representation.

Common Mistake

A tempting but incorrect step is to set every local tolerance to $\varepsilon/S$ and then apply the local approximation theorem for all $0<\varepsilon\le1$. That theorem requires tolerance at most $1/2$; for example, if $S=1$ and $\varepsilon=1$, then $\varepsilon/S=1$, outside its stated range. The correction is to use $\delta=\min\{\varepsilon/S,1/2\}$. It still guarantees $S\delta\le\varepsilon$, and the size bound in terms of $S/\varepsilon$ follows with an adjusted constant, as shown in the proof.

Another common error is to count only the local approximation error at each node and ignore amplification above it. An error introduced below a node with Lipschitz constant $L_v$ can be multiplied by $L_v$; the product along the full path to the root is why the weights $w_v$, rather than a bare count of nodes, enter the accuracy allocation.

Key takeaway: Approximate each smooth local function at a tolerance chosen to control the sum of its propagated errors. The resulting network-size rate depends on local input dimension and smoothness, while the tree affects the bound through its number of nodes and its error-propagation weights.

Check Your Understanding

Use the definitions and error bound above to answer the following questions.

In a binary tree with many leaves, why can the local dimension in the approximation exponent remain two?
For a node $v$, which Lipschitz constants appear in its propagation weight, and why is its own Lipschitz constant excluded?
If $S=12$ and $\varepsilon=0.04$, what common local tolerance does the theorem use?
Suppose all local Lipschitz constants are at most $1$. Give a bound on $S$ in terms of the number $M$ of internal nodes.
Why does the hierarchical rate not imply the same improved rate for every function of the full input vector?