Research Shows Compositional Methods Can Outperform Superpositional Approximation for Certain Functions

A preprint submitted to arXiv by Dennis Elbrächter presents a theoretical analysis showing that compositional approximation — the structural approach underlying neural networks — can strictly outperform superpositional approximation, which encompasses classical methods like linear combinations of dictionary elements. Superpositional methods have historically been considered optimal for many well-studied function classes, in the sense that their uniform approximation error decays at the highest polynomial rate achievable by any parametrized method with efficiently encodable parameters. The new work identifies specific structural properties of function classes that limit superpositional rates while allowing compositional methods to achieve faster decay. Crucially, the authors construct explicit examples where the gap in approximation rates between the two paradigms can be made arbitrarily large, not merely a constant-factor improvement. To ensure a fair comparison, the study imposes constraints on compositional methods — such as neural networks — that guarantee their parameters can be encoded in bit strings of length proportional (up to logarithmic factors) to the number of parameters, placing both approaches on equal computational footing. The results contribute to the theoretical foundation for understanding the expressive power of deep learning and when compositional architectures offer provable advantages.