🔢 mathematics

Compositional Approximation Can Strictly Outperform Superpositional Approximation

This paper demonstrates that for specific function classes with particular structural properties, compositional approximation methods (such as neural networks) can achieve arbitrarily better approximation rates than optimal superpositional methods, which rely on linear combinations of dictionary elements.

Original authors: Dennis Elbrächter, Philipp Petersen

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dennis Elbrächter, Philipp Petersen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Two Ways to Build a House

Imagine you are trying to build a perfect replica of a very complex, intricate house (which represents a function or a pattern in data). You have a toolbox full of simple building blocks (like bricks, beams, or tiles).

The paper compares two different strategies for building this house:

The "Superpositional" Strategy (The Linear Pile): You take your simple blocks and just pile them on top of each other, mixing them together in one big heap. You can adjust how many of each block you use, but you are essentially just adding them up. This is like how traditional mathematical methods (like Fourier series) work.
The "Compositional" Strategy (The Layered Assembly): You build the house in layers. You take a block, shape it, then take that shaped piece and use it as the foundation for the next layer, which you shape again, and so on. This is how Neural Networks work. They don't just add blocks; they compose them, feeding the output of one layer into the next.

The Problem: When the "Pile" Fails

For many simple shapes (like smooth curves), both strategies work about the same. You can build a good approximation with either method.

However, the authors discovered a specific type of "house" (a specific class of mathematical functions) where the Pile Strategy hits a hard wall, while the Layered Strategy zooms right past it.

The Analogy of the "Almost-Orthogonal" Crowd:
Imagine you are trying to describe a crowd of people standing in a room.

The Pile Strategy: You try to describe everyone by picking a few "standard" people from a dictionary and adding them together. If the people in the crowd are all standing in completely different directions (mathematically "orthogonal"), you need a huge number of standard people to describe them all. It's like trying to describe a crowd where everyone is facing a unique direction; you need a unique description for almost everyone.
The Twist: The authors created a scenario where the people are almost facing different directions, but not quite. They are "almost orthogonal."
- In a Pile, this is a nightmare. Because they are so different from each other, you can't reuse your standard blocks efficiently. You need a massive dictionary of blocks to cover everyone, and the number of blocks you need grows explosively as the room gets bigger.
- In a Layered approach, you can build a "machine" that generates these people. You don't need a unique block for every person; you just need a few simple rules (layers) that, when stacked, can generate the specific "almost different" directions.

The Main Discovery: The "Gap"

The paper proves mathematically that for these specific "almost orthogonal" functions:

Superpositional methods (The Pile): The error (how bad the approximation is) stays high unless you use a massive, unmanageable number of parameters. The efficiency is strictly limited.
Compositional methods (The Layers/Neural Networks): You can achieve the same level of accuracy with far fewer parameters.

The authors constructed explicit examples where the gap between the two methods is arbitrarily large. You can make the "Pile" method infinitely worse than the "Layered" method just by tweaking the structure of the function.

Why Does This Happen? (The Geometry of the Problem)

The paper uses a concept called covering numbers (a fancy way of measuring how "big" or "complex" a set of shapes is).

The Pile: To cover all the possible shapes in this specific function class, the Pile method needs to cover a massive area. It's like trying to cover a giant, sprawling forest with a few small tents. You need thousands of tents.
The Layers: The Compositional method realizes that these shapes aren't random; they have a hidden structure (self-similarity). It's like realizing the forest is actually made of repeating patterns of trees. Instead of covering the whole forest with tents, you just need a blueprint to build the trees. The "Layered" method can navigate this structure efficiently, requiring a tiny fraction of the resources.

The "Riesz" Constraint

The paper is careful to say that this advantage holds even if we restrict the "Pile" method to be very well-behaved (mathematically, satisfying a "Riesz condition," which ensures the blocks aren't weirdly redundant or broken). Even with the best possible dictionary of blocks, the Pile method cannot catch up to the Layered method for these specific functions.

Summary

The Claim: Neural networks (compositional methods) are not just "good enough" for everything; they are strictly superior for a specific, mathematically defined class of problems.
The Reason: These problems have a hidden, layered structure that allows you to build complex things from simple steps.
The Limitation: Traditional methods that just add things together (superposition) cannot exploit this structure efficiently. They get stuck trying to describe every tiny variation individually, leading to a massive waste of resources.

In short: If the problem is built like a Russian nesting doll (layers inside layers), a method that builds in layers wins. If you try to solve it by just dumping all the dolls in a pile, you will fail to be efficient, no matter how many dolls you have.

Technical Summary: Compositional Approximation Can Strictly Outperform Superpositional Approximation

Problem Statement
The paper addresses a fundamental question in approximation theory: under what conditions do compositional methods (such as neural networks) provide strictly superior approximation rates compared to superpositional methods (linear combinations of dictionary elements, e.g., M-term approximation). While empirical evidence suggests neural networks are powerful, theoretical justifications often rely on emulating existing methods, achieving comparable but not superior rates. Furthermore, many classical function classes admit dictionaries that yield optimal M-term approximation rates. The authors seek to identify structural properties of function classes where compositional approximation can strictly outperform any superpositional approximation, even under constraints that ensure efficient bit-string encoding of parameters (preventing trivial "brute-force" dictionary constructions).

Methodology and Framework
The authors establish a rigorous mathematical framework within a Hilbert space $H$ to compare approximation schemes:

Approximation Rates: They define the approximation rate $\gamma(C, S)$ as the polynomial decay order of the uniform error as a function of the parameter budget $M$ .
Superpositional Schemes: These are defined as $M$ -term linear combinations of dictionary elements $D = (\phi_i)_{i \in \mathbb{N}}$ , subject to a "polynomial depth search" constraint. This constraint limits the indices and coefficient sizes of the dictionary elements used to a polynomial of $M$ , ensuring the approximant can be encoded as a bit string of length $O(M \log^q M)$ . The Riesz approximation rate ( $\gamma_{\text{Riesz}}$ ) is the supremum of rates achievable by any dictionary satisfying a lower Riesz bound (ensuring stability).
Compositional Schemes: These are modeled via neural networks with constraints on depth (polylogarithmic in $M$ ), connectivity (linear in $M$ ), and weight magnitude (polynomial in $M$ ). This ensures a similar bit-string encoding efficiency.
Geometric Perspective: The core theoretical insight relies on the asymptotic geometry of the function class. The authors argue that if a function class can be $\epsilon$ -approximated by a union of a limited number of low-dimensional linear subspaces (a structure exploitable by composition) but requires a high-dimensional linear subspace for linear approximation, a gap in rates may exist. This is linked to the concept of "covering numbers," where the nonlinear set of approximants is vanishingly small relative to the necessary linear space as $\epsilon \to 0$ .

Key Contributions and Results

The SPOON Construction: The authors introduce a prototypical set structure called a SPOON (Superpolynomially growing almost Orthogonal sequeNce). A SPOON consists of a sequence of sets $V_m$ where:
- The cardinality grows superpolynomially ( $|V_m| \ge 2^{m^\alpha}$ ).
- Elements have norms decaying as $m^{-\mu}$ .
- Elements are pairwise $\eta$ -almost orthogonal, with the inner product bound decaying as $m^{-\nu}$ .
Upper Bound on Superpositional Rates (Theorem 3.4): The central theoretical result proves that if a function class $C$ contains a $(\mu, \nu)$ -SPOON, the best achievable Riesz approximation rate is bounded by:
$\gamma_{\text{Riesz}}(C) \le \frac{1}{2} + \frac{\mu}{\nu}$
The proof utilizes a contradiction argument involving the geometry of almost orthogonal sets and the properties of Riesz dictionaries. It demonstrates that any dictionary satisfying the Riesz condition cannot efficiently cover the exponentially large, almost orthogonal sets within the SPOON using only a polynomial number of terms.
Explicit Construction (Section 4): The authors construct explicit function classes $V(k, \alpha, \beta, \mu)$ using compositions of a "hat" function $f$ . These classes are formed by iterated compositions of functions defined by binary vectors.
- They prove these classes contain large sets of almost orthogonal functions satisfying the SPOON conditions.
- They demonstrate that ReLU neural networks can approximate these classes with a rate of $\gamma_{\rho}^N \ge \frac{\mu}{\alpha}$ .
- Combining this with the upper bound, they show that for specific parameter choices (e.g., $\mu = \sqrt{k}$ ), the gap between compositional and Riesz rates becomes arbitrarily large as the depth of composition $k$ increases. Specifically, $\lim_{k \to \infty} \gamma_{\rho}^N = \infty$ while $\lim_{k \to \infty} \gamma_{\text{Riesz}} \le \frac{1}{2}$ .
Pathological Orthogonality Example (Appendix A): The paper also presents a simpler, though more pathological, example involving an orthonormal system where the coefficients decay logarithmically. In this case, superpositional approximation yields a rate of $-\infty$ (no polynomial decay), while neural networks achieve a positive rate, highlighting the difficulty superpositional methods face with highly orthogonal structures.

Significance and Claims
The paper claims to provide the first explicit examples of function classes where compositional approximation strictly outperforms superpositional approximation, even when the superpositional method is allowed to choose the optimal dictionary under stability (Riesz) and encoding constraints.

The significance lies in identifying a specific structural property—the presence of large, almost orthogonal sets within finite-dimensional subspaces—that is inherently difficult for linear combinations to capture efficiently but is naturally handled by the hierarchical composition of simple building blocks. The authors argue that this structural mismatch explains why neural networks can achieve better rates for certain classes without relying on instability or unbounded parameter encoding. The work suggests that the advantage of neural networks is not merely universal approximation but a specific geometric adaptability to function classes with this "almost orthogonal" structure.

The authors remain modest regarding the scope, noting that their results apply to function classes containing these specific SPOON structures and that the current bounds on superpositional rates are restricted to Riesz dictionaries, though they believe this is a technical rather than fundamental limitation. They do not claim these results apply to all function classes or that neural networks are universally superior, but rather that they are superior for classes exhibiting this specific asymptotic geometric structure.