# Compositional Approximation Can Strictly Outperform Superpositional Approximation

arXiv: https://arxiv.org/abs/2606.08727 · HTML: https://mlsanity.com/paper/2606.08727/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 8 references that are in the map.
- First posted on arXiv 7 Jun 2026.

## Builds on (most cited first, 3 of 3)

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Deep Neural Network Approximation Theory](https://mlsanity.com/paper/1901.02220/) (2019)
- [How degenerate is the parametrization of neural networks with the ReLU activation function?](https://mlsanity.com/paper/1905.09803/) (2019)

## Abstract (arXiv)

Many classically studied function classes are known to be approximated optimally by superpositional methods, i.e. with approximants constructed as the linear combination of elements in some dictionary. Here optimality means that the uniform approximation error viewed as a function of the number of parameters used has polynomial decay of the highest order achievable by any parametrized method whose parameters can be encoded as a bit string of length proportional, up to logarithmic factors, to the number of parameters. While compositional methods like neural networks are structurally different, their approximation rates can be made comparable by imposing constraints that ensure such a proportional bit string encoding. In this work we study function classes exhibiting structural properties that limit superpositional approximation rates to be strictly lower than compositional approximation rates. In particular, we construct explicit examples for which there is an arbitrarily large gap.