Structure of universal formulas
Dmitry Yarotsky
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.