Structure of universal formulas
This work addresses the theoretical understanding of expressiveness in universal formulas, such as neural networks, for researchers in machine learning and approximation theory, though it appears incremental in refining classification results.
The paper analyzes the structural elements of universal formulas, which are parameterized analytic expressions with fixed complexity that can approximate any continuous function on a compact set. It introduces a hierarchy of expressiveness classes, proves classification results for functional families, and shows that fixed-size neural networks with certain transcendental activations cannot approximate functions on arbitrary finite sets, while some families like two-hidden-layer networks can approximate on finite sets but not on whole domains.
By universal formulas we understand parameterized analytic expressions that have a fixed complexity, but nevertheless can approximate any continuous function on a compact set. There exist various examples of such formulas, including some in the form of neural networks. In this paper we analyze the essential structural elements of these highly expressive models. We introduce a hierarchy of expressiveness classes connecting the global approximability property to the weaker property of infinite VC dimension, and prove a series of classification results for several increasingly complex functional families. In particular, we introduce a general family of polynomially-exponentially-algebraic functions that, as we prove, is subject to polynomial constraints. As a consequence, we show that fixed-size neural networks with not more than one layer of neurons having transcendental activations (e.g., sine or standard sigmoid) cannot in general approximate functions on arbitrary finite sets. On the other hand, we give examples of functional families, including two-hidden-layer neural networks, that approximate functions on arbitrary finite sets, but fail to do that on the whole domain of definition.