Structure of universal formulas
Authors: Dmitry Yarotsky
Venue: NeurIPS 2023 poster (2023)
Keywords: VC-dimension
neural networks
activation functions
approximation
polynomials
algebraic functions
TL;DR: We study which parameterized elementary functions of bounded complexity can approximate arbitrary continuous functions

Abstract: 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.

Structure of universal formulas
Dmitry Yarotsky
Skoltech
d. yarotskk@@skotechh.ruu
Abstract
By universal formulas we understand parameterized analytic expressions that have fixed complexity, but nevertheless approximate any continuous function 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 the weaker property infinite VC dimension, and prove a series of classification results for several increasingly complex functional families. In particular, introduce general family of volynomially-xxponeniaalll
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 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.
Introduction
By universal formulas we broadly (informally) understand parameterized explicit analytic expressions that have fixed complexity (as expressions) but nevertheless can approximate any continuous function on a compact set. An example of such formula, given by Boshernitzan [1], is
bd
y(x) = Jn d2 cos(M) cos(e")
where d >> O, a, b and are parameters. proves that, by varying the parameters, functions (I) can uniformly approximate any continuous function on any compact interval in R.
Expression II involves integration. Laczkovich and Ruzsa 13 prove existence of universal formulas representable as elementary functions without integration (moreover, their formulas uniformly approximate continuous functions on the whole under a mild growth assumption).
One can further restrict the types of operations and show that universal formulas can be realized by fixed-size classical neural networks with suitable activation functions [29]. By classical neural network we mean computational model consisting of units ("hidden neurons"), each computing a map 21...., 2n + o (Ei Wg2k + ft), where 21..... 2n (signals) are outputs of some previous neurons, and wM and h are weights (parameters) of the neuron. In addition to hidden neurons, one distinguishes "input neurons" that just represent the scalar components of the network input, and "output neuron(s)" that represent the scalar component(s) of the output. The output neurons work as hidden neurons but without activations, i.e. as .1,...,24, Zn + En Wi,2k + h. As defined, neural networks are fairly restrictive in terms of used operations: for example, they contain multiplications of signals 2 by constants (weights) w, but not multiplications between signals, 22 However, this and some other extra operations can be implemented with any accuracy using suitable combinations of neurons. The universal network in 29 uses a fixed architecture graph, activations sin and aresin,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

sin
arcsin
fax
+ 21
Figure 1: Left: A (slightly simplified) fixed-size universal neural network approximating any I E C(O0, IJ) from (29]. Most hidden neurons are standard neurons 21,..... An with one of the activation functions (identity, sin or arcsin). Also, there are several multiplication neurons. The parameters of the model are all the weights wk, h in the standard neurons. Right: A multiplication neuron can be replaced by group of standard neurons while preserving universality.
<Z Wx=x++h)
and approximate any C((O, (see Figure
D. Another fixed-size universal network had been constructed earlier in [15] but the activation was not an elementary function in that work.
The Kolmogorov(-Aroodd) Superposition Theorem 10 shows that any function f C([o, 1]d) can be expressed in terms fixed number (only depending on d) of summations and univariate continuous functions. This implies that multivariate universal formulas
be easily constructed from univariate ones, by plugging the latter in the Kolmogorov ansatz. Accordingly, the question of multivariate universal formulas is not significantly more interesting complicated than its counterpart for univariate formulas, and in this paper restrict our attention to the latter. We also mention in passing another interesting property of universal formulas: they naturally give rise to universal polynomial O, with a polynomial P and dense set of solutions in C[aa, bl), see 2 19 [3]. (In fact, one can find such a polynomial for any parameterized family of elementary functions; the density of solutions then follows from the universality of the formula.) See [22 for a connection to analog computers.
differential equations P( (zz ....... f(m))
A foundational theorem neural networks is the universal approximation theorem (UAT). It states that, for a broad class of activation functions, neural network with a single layer of hidden neurons can approximate any continuous function a compact set if we increase the number of neurons [8]. This result is very different from, and should not be confused with the above fixed-size universal networks of [15] [29] In UAT, universality is achieved by increasing the number of parameters, and accordingly UAT imposes much weaker requirements on the activation functions (c.g., it holds for any continuous non-polynomial activation, [14 18]).
the other hand, the fixed-size universal network in Figure I is fairly simple. One of the two activation functions used there, sin, is actually used as activation in practical multi-layer networks (e.g., the popular SIREN network of (23)). This raises the following natural question motivating the present paper: can practically used neural-network-type models be universal as fixed-size formulas (i.e., without increasing the number of neurons)?
There is an important caveat here: the universality of universal formulas is, of course, an idealization that requires their parameters have unbounded precision or magnitude. parameters are finitely defined so as to be representable on real computer, one can give simple entropy bound constraining feasible approximation accuracy. Specifically, suppose that formula contains p parameters, each somehow represented using B bits (e.g., B = 32 or 64 for standard floats). Suppose we are approximating function ff at N points #1,... ., NN with absolute accuracy c. Suppose finally that [f] is bounded by M and (xx),, h = 1,..., N, can be chosen independently subject to this constraint. Then
N loog, PB.
(2)
This shows that in practical application with parameters implemented as standard floats, universal formulas such as (T) can typically produce only crude approximations. In the sequel, we will ignore these finite- prete-precciion aspects.

---

Our contribution. Our goal in this paper is to understand which structural properties are critical for universal formulas. This question does not seem be simple. As general strategy of tackling it, we analyze a sequence of progressively more complex parametric functional families with respect to several relevant classes of model expressiveness. Our specific contributions are as follows.
1. We introduce hierarchy Go D 91 D 92 of classes of model expressiveness (Section 2) Here Go represents the families of infinite VC-dimension, G1 the families achieving approx- imation arbitrary finite sets, and G2 the families achieving uniform approximation on the whole segment [0, 1j. Universal formulas correspond to the class G2. The class Go is important because elementary functions belonging to it must involve, in some form, the function sin acting on an unbounded domain (Section 3 We argue that the class 91 is also important because, as we show, some functional families cannot belong to it due to algebraic (polynomial) constraints.
2. As first result on algebraic constraints, we consider the family of fixed-size linear combi- nations of sine waves with unbounded weights (equivalently, fixed-size single-hidden-layer neural networks with activation sin) and prove that it belongs to the class Go G1. Moreover, we give a complete description of the limit points of this family (Section 4
3. As a generalization of the previous result, we introduce a general family of polynomially- aagonenniaalyy-lgebbee expressions of bounded complexity, and prove that it is also subject to polynomial constraints and lies outside G1 (Section 5
4. We give an application of the previous result to branching expressions and neural networks with conventional activations (Section (). Specifically, we prove that if the network has bounded complexity and possibly multiple layers, but only one layer with transcendental activation functions (such as sin x, Gaussian or standard sigmoid). then the network is subject to polynomial constraints and lies outside G1. Moreover, polynomial constraints hold even if the activation functions are only piecewise analytic, is common in practice.
5. The situation drastically different for formulas involving compositions of polyooolll analytic functions and sin: such formulas generally belong to G1 (Section 7 It seems hard to separate the classes G1 \ G2 and Gz. We give a couple of examples of families for which we can prove that they belong to Gi G2. One of these families can be deseribed as that of txeel-copleexity two-hidden-layer networks with sin activation that have single neuron in the second hidden layer. We conjecture that general sine networks of fixed complexity also belong to G1 \ G2.
Most proofs are deferred the appendix (the respective sections are indicated in the theorems).
2 The hierarchy of expressiveness classes
Throughout the paper, we consider various families H of functions g [0, -> R. We define for them expressiveness classes Go, G1, G2:
H E Go
Kapnik-Chervonent dimension VCdim(H) oc;
H 91
For any finite subset (x x E [0, 1], any ,,,..., YN E R and any >> 0 there is E H such that ( - 3kll < e for all k 1,...,,N N.
def
H G2 def For any f C(10, 11) and SuP (g(x)) [xx) <.
0, there is g H such that l|g flloo
Here, VCdim(Hy) = oc means that for any N E N we can find a size-N subset X C |0, shattered by H thresholded at 0, i.c. such that for any S C X there is g E H for which g(x) > Of x E S and g(z) < 0f x E X S.
Clearly,
Go 2 91 16125 22.
(3)
The classes 91 and G2 reflect approximability on arbitrary finite sets and on the whole interval [0, 1), respectively. Universal formulas discussed in the Introduction correspond to the class G2. One can
3

---

say that G1 corresponds to universality in a weaker sense, which is particularly relevant if we try to lear the parameters using a finite training set {(zg, yt)}.
We will consider several families H that we will distinguish by superscripts denoting or enumerating their types (c.g. Ht or H (()),.) and by subscripts reflecting complexity within the type (e.g., ( will denote linear combinations of N sine waves). Most of these families admit natural interpretations in terms of conventional neural networks- - we will mention them along the way.
While the remainder of this work focuses on the mathematical analysis of the relation between various functional families and the classes GR. let us briefly clarify the role of these classes from the general perspective of approximation and learning.
1. Most conventional learning models (e.g., neural networks) can be said to be defined using (piecewise) elementary functions. If the model is assumed to have a bounded complexity (e.g., a bounded number of neurons) and its weights and signals are bounded, this model falls outside even the broadest class Go (see Section 3 helow). This does not apply, however, to models containing the function sin acting on an unbounded domain.
2. For a fixed-coppexxity model, being outside the classes Gi and thus not having the full ap- proximation power is not a practically negative property: this just means that the complexity of the model needs to increase to achieve better fit.
3. The situation when a fixed-coppexitty model belongs to the class G2 (i.e., is a universal formula) is mathematically interesting but somewhat exotic from the perspective of con- ventional computation, since the respective model parameters need to contain a potentially unbounded amount of information.
4. The class 91 \ G2 seems especially dangerous from the generalization point of view: given a hypothesis space И from this class, we can fit a model arbitrarily well to a generic continuous ground truth on any finite training set, but can hardly ever uniformly approximate this ground truth on the whole domain. This cannot be said about the class G2. In Section we give examples of functional families (neural networks) provably belonging to this dangerous class G1 \ G2.
3 Pfaffian functions
There is an important broad class of parameterized functions [ar, w) for which one can guarantee that the family H obtained by fixing various w has a finite VC-dimension. This class is most naturally described in terms of Pfaffian functions introduced by (9. Pfaffian functions can be defined using function sequences in which, at each step, the next function satisfies polynomial first-order differential equations involving itself and previous functions (see p 5 30 for details). In particular, Pfaffian functions include all elementary functions when the latter are defined on suitable domains.
Importantly, in contrast to functions like In, exp and polynomials, which are Pfaffian on their whole natural domain of definition, the function sin is not Pfaffian on the whole set R. though it is Pfaffian on any bounded interval (a, b) (moreover, the representation of sin as a Pfaffian function depends on (a, b) and becomes more complex as b a increases). For this reason, elementary functions Pfaffian only when they involve sin (or a closely related function, like cos) restricted to bounded intervals.
The fundamental theorem of gives an explicit finite upper bound on the number of zeros of Pfaffian functions, which implies, in particular, that the respective parametric families have finite VC-dimension. We state this result specialized to elementary functions and in the form suitable for
purposes; see 99. 30 29 for details.
Theorem 1. Suppose that a formula y f(x,, w) is constructed from the variables x and wi... Wa using real numbers, standard arithmetic operations (+, -, x/)), elementary functions In, exp, sin, aresin, and compositions. Suppose that there is a nonempty subset W C R such that for any = (w...... wa) E W the function f(., w): [0. + R) is well well-defined. i.e., In and aresin are applied on the intervals (0, oo) and (-1,1), respectively, and there is no division by O. Moreover, suppose that there is bounded interval (a, to which the arguments of sin always belong for all E W. Then the family H [f(, w)w has finite VC-dimension.
4

---

This theorem shows that an elementary function has chances to be universal only if it includes sin (or some related function) acting on an unbounded domain. Therefore, we will focus on these latter functions in the sequel.
It is crucial for Theorem T that all the computations in the formula real-valued and not complex- valued (the proof eventually boils down to Rolle's theorem, which does not hold for C-valued functions). In particular, we cannot bypass the domain restriction of sin by simply writing sin æ (e e = /2. In contrast, many results in the next sections will be essentially algebraic and will hold for complex complex-valued valued operations.
We remark that Sontag [25] considers a class of formulas closely related to Pfaffian functions and proves that shattering k-poiit sets in general position requires at least (k 1)/2 parameters in such formulas.
4 Linear combinations of sines
simple example family with an infinite VC-dimension is H = (esin(wa)) JaeR. This usually proved (see e.g. (28). Section 3.6) by giving a particular example of an arbitrarily large finite set shattered by (1),, For our purposes, however, it is instructive to describe a general collection of finite sets on which H1)) has universal approximability. We say that numbers 21, ,,, ...... are rationally independent if they linearly independent over the field Q of rational numbers.
Theorem 2. Let X {=1.... EN } be finite subset (0, 1] such that the values 21, ....... ZN rationally independent. Then the family (()) can approximate any R-valued function on X.
Proof. Consider the torus TN = (R. [T) its points can be identified with the points of the cube [0, 2 N Let |-] : R - [0. 1) be the standard floor function. By a classical Kronecker's 's theorem 7 the set ((2 - (zz ()..))..... 2.. 20x [ [))]))]eeee) JOER is a dense subset of TV if and only the numbers NN are rationally independent. Using the 2n-periodicity of sin, this implies immediately that if #1,... NN are rationally independent, then ((iin(w))) ..... s.isssn( () is dense in 1 and hence {(csin(wx] ...... x)) is dense in R.N.
....,
This result shows that the family (2) E Go- It is also clear that (1 & GI (e.g., since g(0) 0 for any E ())). In fact, the sufficient condition of rational independence in the theorem is close to also being necessary. In particular, a simple kind of sets not shattered by HI) are all nontrivial arithmetic progressions F&
ok, # 0, of length 5. Indeed, it follows from the identity sin (u + (I: 1)v) + sin(u + (k: + 1)u) = (i + kv) cos(r) that the values of functions from (2) cannot, for example, have the sign configuration + + + + on such progressions.
Consider now the more general family consisting of all linear combinations of fixed number of sine waves with arbitrary frequencies and phases:
N
H N
Σ
On sin(wn + hn)
(4)
dhl ERR.=l,,.,,""
One can view this family as representing single-hidden hidden-layee neural networks with the sin activation function (w,, and hn are the weights and biases in the hidden layer, and en are the weights in the output layer).
One can again easily show that H (2) N E Go \ G1, by observing that the values of all functions g E H (2)
are constrained by common nontrivial polynomial equations:
Theorem 3.
1. For any NN Za E R and On, Bn E R. O..... ......... 2N,
det A = 0, where A = (g(x0 + + 3m)) 2N
km
(5)
2. det A is nonzero polynomial in the variables g(æ), where x E X = (xo + on + fm O,.... 2N), }, if and only if all ag different and all Bm are different.
5

---

Proof. 1. The matrix A is degenerate because each of its 2N + rows is linear combination of 2.N vectors (e"w,,) e with n = ......NN .N and $ =i.
2. If some Or or Am are repeated, then the matrix A contains repeated columns or rows and so the polynomial det A identically vanishes. Conversely, suppose that all og are different and all 8m, different. Without loss, we can assume ag < < C22N and 000- <... < B2N. We can then expand det A g(zo + 02N + B2N) det A' + ..., where det A' is the top left 2.N 2N minor and the terms... do not contain the variable g(ro + 02N + 8, Repeating the expansion for A', etc., we that the polynomial det A contains the monomial I g(2 ag 3x) with coefficient 1, i.. is nonzero.
This result shows that there are (infinitely many) nontrivial polynomial constraints the values of the functions g E H Importantly, these constraints are preserved under pointwise limits, so, in particular, H (2) E Go \ G1- Taking N 1 and a₃ By ok, k 0, 1, obtain a nontrivial constraint for the values of g on any nontrivial length-5 arithmetic progression Zy = u + wk, in agreement with earlier observation.
In fact, thanks to the semi-linear structure of the family H we can go further and give explicit description of its limit points. It turns out that the limiting functions can only differ from the original combinations of sine waves by resonant factors x""
Theorem A Let be fixed. Then a function fa is limit point of H in the sense of uniform convergence on the segment [0, 1] if and only if
2Mo-1
K Ma-1
fx)x)
Σ
Com
Σ
Ckex th sin(waa + hkm);
(6)
m=
where Mo 2 0, M₁ 2 f K = l..... K, and Σ M = N.
Resonant factors appear by taking suitable combinations of sine waves at close frequencies, e.g. sin(wxx) lim - + Aw)xr sin(..)). We show explicitly how construct resonances of arbitrary degrees subject to the constraint Σk=n Mr N. Note that the frequency 0 corresponding to the first sum in expansion (6) is special as it is associated with potential double-degree resonance.
The more difficult part of the proof is the "only if" part, i.c. that any limiting function has the form (6). Our basic idea is show that limiting function subject to linear differential equation describing waves with a given set of frequencies: the general resomant form (6) would then appear from the usual solution of such an equation with nontrivial multiplicities of the frequencies. This strategy, however, is not so easy to implement rigorously, since in our setting the frequencies are unbounded. We give two alternative proofs overcoming this difficulty. The first, clustering- based
proof, groups the frequencies found in a converging sequence fn E H "frequency clusters", and then shows that unbounded clusters can be removed without changing the (2)
(2) into spatially separated
limit. The second, discretizutionnbasee proof, starts with describing the discretized functions of H( by suitable linear diffte-effeeeecee equations which also hold for the limiting function f.. Then, consider these discretizations at different length scales and show that they can only be consistent with each other and with the continuity of the uniform limit f. if representation (6) holds.
5
expressions
Theorem shows that the values of functions H (2
N are subject to nontrivial polynomial constraints preserved under pointwise limits. We extend this argument to a much larger family of functions, involving complex algebraic operations. This generaliztion will allow us, in particular, prove related result for multi-layer neural networks.
U c CN is open domain, we say that a holomorphic function Q U C is algebraic function if there exist N-variable polynomials do...., Ug. not all zero, such that
(Z (zi...., 2N) = O. Vz (21...., 2N) E U. Σ (

---

The value is called the degree of the algebraic function Q. Algebraic functions include, in particular, all polynomials and (on their holomorphy domains) rational functions and powers 2" with rational Arithmetic operations and compositions applied to algebraic function produce again algebraic functions.
We define the family H (3) N. d. as consisting of all functions g : [0, + IR of the form
(x) = Q(x, (()), ee..,......... Px(()))
(8)
where Pl..... PN are complex-valuee polynomials of degree S d, and Q is an algebraic function of degree S q such that all polynomials du appearing in its definition have degree S r. Here, the functions Q are assumed to be defined some domains U CN++1 that contain all the values (2c, e eP(()) ee,,eeelaa ew(x)), ) x E [0, I]. Our main result is the following extension of Theorem 3
Theorem 5
Fix N, 9, d. Let m = (1- 1) (+1 + (max(11,) + 1)(N + 1). Then there exists a nonzero polynomial R of m + 1 variables such that for any E H N.g.r.d and any a, b E [0, 1]
R(g(a): g(a + h). g(a + 26)......(()))
9(6)) = =0, h b-2
(9)
As corollary, since the polynomial R is the same for all g E H N.g.r.d constraint (9) is preserved by (3) pointwise limits, so H N.g.r.d $ G1.
Our proof of Theorem 5 is inspired by the theory of iigebraii-transcendde functions 16
that addresses representability of functions by algebraic differential equations. Our context is rather different: we are interested in the pointwise convergence of functions (or convergence in the uniform norm). so conditions involving derivatives are not applicable in our setting. We observe, however, that some elements of this theory can be extended from the usual to discretized derivatives. This is why, in particular, the conditions in Eq. ( are formulated for a regular grid of points a, a + h,...,b.
Since the polynomials Pn in the definition of (1)3) N. are allowed to be
the families
(( N.g.r,d subsume the sine wave families ( considered in the previous section:
H (2) C C 21.1.111
(10)
Branching expressions and neural networks
We describe now application of Theorem 5 to neural networks. We start by noting that many standard activation functions can be classified as piecewise polynomial or (piecewise) algebraic- exponentia
Piecewise polynomial:
Binary step function (I) [[x 2 0). ReLU (<)) max(0, (),,, leaky
ReLU (x) = max(ar,,a n), squared ReLU (xx = max² (0.z) [2].
(Piecewise) algebraic-exponential sin.r, tanh x, standard sigmoid (I) - ELU
a(x) [a(e" 1), x < 0 swish (xx) x/(1+
20 Gaussian (xx) x
x.
x
"Piecewise" here means that R is in general divided into several subsets (in fact, up to two subsets in the above examples) on which the activation defined by different analytic formulas. We will refer to this as "branching". On each branch, activations of the first type are polynomials, and those of the second type can be represented in the form (8) with a polynomial or rational Q.
Define the family N of functions [0, 1] - RR as realization, with various weight assignment, of the following class of feedforward neural networks. Suppose that the underlying directed acyelic graph of the network contains at most N neurons. Suppose that each hidden neuron is equipped with one of the piecewise polynomial or algebraic-exponeetiie activation functions mentioned above (possibly different at different neurons). Suppose finally that any directed path from the input to the output neuron contains most one (piecewise) algebraic-exponential neuron (for example, this is the case if the network has a single algebraic-expomenttal layer, while the other layers are piecewise polynomial). Then we have
'f course, there also exist standard activations not of these two types, e.g. sofiplus (2) IIn1 e²) 6
7

---

Theorem 6 (C. Given N, there exists and nontrivial polynomial R of m + variables such that for any g E HN and any a, b [0,1]
Rig(a), g(a + h), g(a +
= =0,
h
h-2
(11)
The main obstacle in deriving this theorem from Theorem 5 is the branching in the activations that destroys the global analytic structure of functions g E H We overcome this obstacle using the well-known Van der Waerden's 's theorem arithmetic progressions.
Theorem 7 ((7): see, e.g., 26 for short proof). For any integers s.P there exists an integer
Ns p) 2 such that every coloring C (I,,.., N.... (1....P) of {I,.., Neaw) } into p colors contains at least one monochromatic arithmetic progression of length s (i.e. progression in {1,.. Neaw) } of cardinality s on which C is constant).
Compositions of sines and non-polynomial functions
The exoooeeiillnlonnlllllleeee polynomial constraints of Theorem 5 as we show by the following example. Let a be a real analytic function on the interval [-1,1]. Let [(x) esin(war(lrr) h) with parameters e, b, h E IR and b E [-1, 1]. Denote the respective family by H
structure (8) is actually close to being necessary for the
Theorem (D). Hº E 91 if and only if a is not a polynomial.
This shows that the polynomial constraints of Theorem 5 are destroyed if we relax even slightly the requirement of polynomial arguments of the exponentials in Eq. (8) They are also destroyed if we replace the algebraic function Q by the sine function.
While H E 91 for non-polynomial a, we can show that He is never in G2, by directly finding all limit points of 11 under uniform limits. Let call the limit points of H¹ not belonging Hº nontrivial.
Theorem 9 E For a non-constant a, the only nontrivial limit points of the family H are an + a,æx" ao (bxr) + c, and esin(a, a,x"), where arg min(m 0 an: dr, o, b, E R. In particular, He & G2.
d (0) + 0) and
The families Hº with non non- oon-polylomial a thus provide examples of elements of the class G1 \ G2 of finitely- but not globally-universe formulas. Consider now a more complex family ( consisting of the functions
(5)
f(x) csin(g(=)) + h, P ?
(12)
where (2)) consists of linear combinations of N sine waves as defined earlier in Eq. One can
interpret the family (5) as a two-hidden-layer neural network with the activation function, N neurons in the first hidden layer, and single neuron in the second hidden layer. Using the same
approach of examining the limit points and invoking additional topological arguments, we prove that
the family (5) belongs to the same class as Hº:
Theorem 10 For any N 2 1, ( E G 92
appears that the class Gi \ G2 quite generic - we conjecture that an analog of Theorem 10 holds for any multi-layer neural network with the sin activation and a bounded number of neurons. However, proving such general result by explicitly describing the limit points as Theorems 9 10 is difficult. We are not aware of simple conditions allowing to separate Gi \ G2 from G2.
In this context, let us discuss the structure of universal formulas mentioned in the Introduction.
bd Boshernitzan's formula ( includes the factor I+ ccos(br) which is of the form g and hence in G1,
and the transcendental composition cos(e²). This agrees with our results showing that compositions of sines and non -olyyooaaa functions are essential for universal formulas. However, Boshernitzan' 's formula also includes integration, which effectively serves to produce an approximation to a piecewise constant function. The neural network in Figure T and the formulas of [3] combine sines with arcsines, which serves to approximate periodic piecewise linear or piecewise constant functions. seems that approximate piecewise constant functions are essential element of existing universal

---

formulas, and so one can conjecture that arcsine related inverse trigonometric function is necessary component of an elementary universal formula without integration.
In the fairly different context of recursive decidability, there is a remarkably similar sharp difference
between polynomial-sine and more complex compositions [1]. Let S1 denote the ring generated by the integers and the expressions 2, sin and sin (z sin x" (1 1, ....... J. Let also S2 denote the ring generated by the integers and the expressions sin x" and cos xr (n 11, ........ Then the predicate that there exists real z such that f(x) > 0 is undecidable for E Si, but decidable for S2.
8 Discussion
The expressivenes: hierarchy. To analyze the necessary features of the structure of universal formulas, we have examined the chain of expressiveness classes Go 5 9 ? G2 corresponding, respectively, to the families having the infinite VC-dimension, general approximability on all finite sets, and general global uniform approximability. Membership in the class Go can be conveniently studied using the theory of Pfaffian functions, while, as we have shown, membership in the class 91 can be conveniently studied using algebraic methods. In particular, our results suggest that globally universal formulas need to involve suitable compositions of non-polynomial and sine operations.
Transcendental structure of universal formulas. Our main result in Section 5 shows that combin- ing a single layer of exponential and sine operations with polynomials and algebraic functions has a fairly weak expressiveness, in the sense that such formulas of bounded complexity polynomial relations and do not even have general approximability on finite sets. In this family, the requirement on the operations preceding the exponential/siee layer much stronger (polynomial) than the requirement on the subsequent operations (algebraic). As Theorem g shows, any non non-polyy pon--olyoomial operation preceding the sine operation and combined with linear operations restores the general finite approximability.
constrained by
General methods. All results presented in this paper that rule out global universality are essentially obtained by one of the three general methods: Khovansky's analytic theory of Pfaffian functions (Theorem [T). finding algebraic constraints (Theorems 3 5 66, and direct computations of limit functions (Theorems 4 TOP. It appears that all these methods are insufficient to conveniently separate the finite approximability class G1 \ G2 from the global approximability class G2. Only the last of the three methods seems useful for that, but it seems hard to find the full set of limit points for more complex families similarly to how we did that for the linear combinations of sines (Theorems and the families Ha H5() (Theorems
10). It would be interesting to have general method
suitable for separating 91 G2 from G2-
Limit points. Theorems 4 and show that the nontrivial limit points of the families H² and He are some sort of resonances, reflecting some degeneracies of the model. The set of nontrivial limit points is small and explicit these two cases. However, in a universal formula this set the whole C[[0, 1J). It would be interesting to see how general is this dichotomy, e.g. whether the set of nontrivial limit points of some formula can be small but not explicitly describable subset of C(O0, 1)).
Neural networks. In Section 6 we described a general family of neural networks lying outside the class Gj and so non-universal. These networks can have single layer of transcendental neurons (with activations such as sin, tanh, ="x) as well some layers with
activations. We have shown that though the resulting functions are only piecewise analytic, they still admit polynomial constraints. remains, however, an open question whether networks with multiple transcendental layers involving the sine activation can be universal. Theorem 8 shows that such networks belong to Gi. while Theorem I0 shows that the two-hidden-layes -lyer sine network of bounded complexity and with a single neuron in the second hidden layer belongs to Gi \ G2. We conjecture that, without aresin or other special functions that help create periodie piecewise- linear dependencies, general sin networks of fixed complexity belong to G1 \ G2.

---

Acknowledgments
The author thanks the anonymous reviewers for several useful suggestions. Research was supported by Russian Science Foundation, grant 21-11-00373.
References
[1] Michael Boshernitzan. Universal formulae and universal differential equations. Annals of mathematics, 124(2):273-291, 1986.
[2] Creighton Buck. The solutions to a smooth PDE be dense in C ()). Technical report, WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER, 1980.
[3] Djórk-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint 1rXiv:151..07288 2015.
[4] George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
[5] Andrei Gabrielov and Nicolai Vorobjov. Complexity of computations with pfaffian and noethe- rian functions. Normal forms, bifurcations and finiteness problems in differential equations, 137:211-250, 2004.
[6] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 315-323, 2011.
[7] Steven M Gonek and Hugh L Montgomery. Kronecker's approximation theorem. Indagationes Mathematicae, 27(2):506-523, 2016.
[8] Erik Christian Hansen, Yonathan Stone, and Jesse Wolfson. Alexander Ostrowski's "On Dirichlet Series and Algebraic Differential Equations". arXiv preprint arXiv:2211.02088, 2022.
[9] A. G. Khovanskii. Fewnomials. Vol. 88 of Translations Mathematical Monographs. American Mathematical Society, 1991.
[10] Andrei Kolmogorov. On the representation of continuous functions of many variables by superposition of continuous functions one variable and addition. In Doklady Akademii Nauk, volume 114, pages 953-956. Russian Academy of Sciences, 1957.
[11] Leopold Kronecker. Näherungsweise ganzzahlige Auftössng linearer Gleichungen. Monats. Königl. Preuss. Akad. Wiss. Berlin, pages 1179-1193, 1271-1299, 1884.
[12] Miklós Laczkovich. The removal from some undecidable problems involving elementary functions. Proceedings of the American Mathematical Society, 131(7):2235-2240) 2003.
[13] Miklós Laczkovich and Imre Z Ruzsa. Elementary and integral-clementary functions. Illinois Journal of Mathematics, 44(1):161-182, 2000.
[14] Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken, Multilayer feedforward networks with nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867, 1993.
[15] Vitaly Maiorov and Allan Pinkus. Lower bounds for approximation by mlp neural networks. Neurocomputing, 25(1-3):11-11 1999.
[16] Eliakim Hastings Moore. Concerning transcendentally transcendental functions. Mathematische Annalen, 48(1-2)::9-744 1896.
[17] Alexander Ostrowski. Über dirichletsche Reihen und algebraische Differentialgleichnnge. Mathematische Zeitschrift, 8(3):241 2298, 1920.
[18] Allan Pinkus. Approximation theory of the mip model neural networks. Acta numerica,
8: 8:143-195, 1999.
10

---

[19] Amaury Pouly and Olivier Bournez. A universal ordinary differential equation. Logical Methods in Computer Science, 16, 2020.
[20] Prajit Ramachandran, Barret Zoph, and Quoc V Le. Searching for activation functions, arXiv preprint arXiv: 1710.051,,, 2017.
[21] Lee A Rubel. universal differential equation. Bulletin (new series) of the american mathemat- ical society, 4(3):345-33) -39,, 1981.
[22] Lee A Rubel. The extended analog computer. Advances in Applied Mathematics, 14(1):39-50, 1993.
[23] Vincent Sitzmann, Julien Martel, Alexander Bergman, David Lindell, and Gordon Wetzstein, Im- plicit neural representations with periodic activation functions. Advances in Neural Information Processing Systems, 33:7462-7473, 2020.
[24] David R So, Wojciech Mańke, Hanxiao Liu, Zihang Dai, Noam Shazeer, and Quoc Le. Primer: Searching for efficient transformers for language modeling. arXiv preprint arXtv:2109.08668. 2021.
[25] Eduardo D Sontag. Shattering all sets of 'k' poontss in "general position" requires 1k-1)/2 parameters. Neural Computation, 9(2)3377-348, 1997.
[26] Terence Tao, A quantitative ergodic theory proof of Szemerédi's theorem. arXiv preprint math/0405251, 2004.
[27] Bartel Leendert Van der Waerden. Beweis einer baudetschen Vermutung. Nieuw Arch. Wiskunde, 15:212-216, 1927.
[28] Vladimir Vapnik. The nature of statistical learning theory. Springer science business media, 1999.
[29] Dmitry Yarotsky. Elementary superexpressive activations. In International Conference Machine Learning, pages 1132-11940, PMLR, 2021.
[30] Thierry Zell. Betti numbers of semi-pfaftian sets. Journal of Pure and Applied Algebra, (33(333)33,3-38, 1999.

---

Contents
Introduction
2
The hierarchy of expressiveness classes
3
Pfaffian functions
Linear combinations of sines
Poyyeomiall---ppoonnniillllhhiii expressions
Branching expressions and neural networks
Compositions of sines and non-polynomial functions
8
Discussion
References
10
Proof of Theorem 4
12
B Proof of Theorem 5
21
Proof of Theorem 6
24
D Proof of Theorem 8
25
Proof of Theorem 9
25
Proof of Theorem 10
26
A Proof of Theorem
Sufficiency (each function 66 is limit point of ( First observe that each resonant component xm sin(wx + h)) is a uniform limit of m + sine waves linearly combined to match the discretized dth derivative dum sin(wx + Tm/2):
d' nm sin(wx + h) d sin (wx + h 1-th//2 Tm/2)
(13)
m
=
lim (Aw) Aw-3
m (-1)
sin((w + nAw]e + mm/2).
(14)
n==
Note also that any finite linear combination Em=) Gm sin (war + hm)) can be written as single sine wave csin(wx + h) with suitable amplitude e and phase h. It follows that we can obtain any linear combination - Cma sin(wx + hm) as uniform Aw 0 limit of linear combinations
M 1
Cm, sin((w + mAw) + kmmAww
(15)
12

---

with suitable values of Cm, and hm, This shows in turn that the second component of expression
K Ma-1
Σ
Σ
Cka sin + hkm),
(16)
A=1
can be obtained by limits of linear combinations frequencies.
Σx= k=1 Mg sine waves with suitable phases and
It remains show that the first component of expression (6) limit of linear combinations Mo sine waves. Observe that for any constant Ty
m=n Com can be obtained
2M
(x 20 2M MMMe-11- lim (Aw)2Mo-1 sin sin 2Mo (Awr Awro). (
(17)
Aw-0
2inn200-1100 (Awx Awro) is linear combination of Mo sine waves with 1, 1,.... My (and some phases). By previously given argument, this implies that any linear combination of monomials (æ =z) 2.Mo can also be obtained
Since 2. - 1 is odd, sin 2M sin frequencies (2x - 1)
limit of some linear combinations of Mg sine waves with frequencies (2s 1)Aw, s = 1..... Mg. But the monomials (x =o)) 20 linearly span the space of polynomials of degree - 2. 1. It follows that any such polynomial can be obtained as a limit of linear combinations of My sine waves, as claimed.
Necessity (each limit point of (222) has the from
We give two alternative proofs.
Suppose that function f. the uniform limit of functions fr (2) We identify the different frequency clusters associated with the sequence fr. Let S w1,r S S WN,, be the N sorted frequencies appearing the sine wave expansion fy; we assume here without loss of generality that all the frequencies are nonnegative, For each n = 1,...,N N - one of the following three options holds:
Proof 1 ("clustering-basedd
1. either wn+1, Wp.r " 00;
2. or sup,, (Wn+1. - Wn.r) < oo;
3. or none of the above holds.
For each n, by taking subsequence of fr, times, we can then assume without loss of generality that for each n either option 1 or option 2 holds. It follows that we can partition the set (1,..., N) into contiguous subsets 7 (1, (1) T2
exclude option 3. By taking subsequences N
{ir + I...., i2....., I. = (io-1 + I,...,N] N} such that for some constant !
" co,
if n, n' E Ie: Ω Vr, if n. e 4.
Whrr worrl
(18)
The sets I thus represent the largest clusters of frequencies that remain at a bounded distance from each other in the limit oc.
Clearly, there at most one cluster whose frequencies remain bounded in the limit - co, namely It with to 1. It will be convenient assume that I, has bounded frequencies but possibly is empty.
For any M = 1, 2.... and Ω > 0 let denote by (2 form
ai the set of functions f [0, - C of the
f(x) Σ Ren
(19)
where c, E C are arbitrary amplitudes and wn E 12
Lemma 1. For any M. and n 1,2,...
(2)
(x)) 2 M(++1) (1 + 22) M max(n, xE(0,1]
max
max [f(x)).
(20)
x
13

---

We remark that the constant in Eq. (20) is likely suboptimal, but it must certainly grow with M, since, as the proof of the sufficiency part of Theorem 4 shows, arbitrarily narrow frequency bands are sufficient to generate any degree-M polynomial.
Proof. The function f satisfies the differential equation Dj = O, where
M
M
D
II
de iwn)
AM
bp
(21)
dz
da
with some constants 6n Consider the vector-valued function f(x) = ((()) ((U It satisfies the differential equation
f = Af
(22)
dx
with the matrix A (amm m where
1
+ 1 and n < M - 1,
Onm
dm
M - 1,
(23)
0,
otherwise.
The solution of this equation is
(xx) A(a A(a-50) p(xo))
(24)
If || || is any norm on the CM, then
[[(()) f(xx))l I (ellAlllezoll 1)(lf(20)lls
(25)
where ||||| is the respective matrix norm. Let || oloo be the maximum (1=2) norm, then
M
|| = max
Σ
1amll = max Σ 1mml:1) 1)
- II (1 + Wmm )) S (1+
(26)
m
m=1
Now let zu arg x] fl) loo and let no
arg
M-1 f(() (2o) that
[[((z))] = (mo) (zo)). no = 0, then
max 2E
['(x))
max [[()).
(27)
=E(0.1]
Suppose that no > Observe that if 2 - xol S 1n2 (1 + 92 -M then
[x(n))(x)= p (xo) < [[f(z) - f(xoo)l |1
(28)
(e (ellA1l> lo- 1) (2
(29)
(1+0)) - 1) (2o))
(30)
1 (n (zo)1-
(31)
(zo) and denote / = 1n2 2 [=mo)(zo)
Consider the complex unit direction zo-
(1 + -M-
For all x such
that | -rol I we have
R (mo) (mo) (x)) 2 (z))))
(32)
It follows that can find in [0, 1] subinterval of length 1/ on which either
R(zo (x)) 2 2/4 (mo) (xo))
(33)
or
Riz no- (x)) S - ( (xro)-
(34)
Making another iteration, we can find in [0, 1] a subinterval of length 1/42 on which either
RiZo (mo (x)) 2 1/2 2-1 (f
(35)
or
(x)) s to= 24 f (2o) RoZo (
(36)
14

---

Continuing in this way, for any n = no, - -1, -....., 0 we find in [0, 1] subinterval of length 1/4"e- on which either
R(zo (no
(3:)) 2 20no m]ing #FIFI ((no) (2o0) (xx)) (2n=-
(37)
or
R(zo (no-n) < 2ing- -+
((m)) (zu))l
(38)
Taking 0, this implies
( S 22o
max [xxx
(39)
and so, by definition of zo and no. for any n = .,...,M
M -1
max [0.1 (x() ((m))
(40)
max [f(x)
(41)
Dc U
+ 52) M M)
max
[(x)]
(42)
S 22 + 22) (MM-1) max
[(())
(43)
zE|o,1]
This proves the claim for S M 1. If 2 M, then we use again Eq. 21 and the bound
Em (bml $ (2)
Lemma 2. The L and L? norms are equivalent on the set (22) M. for any Hag
|1/ll2 < |0 & 2/2(1 + 12) 1|
(44)
Proof.
Only the second inequality is nontrivial. By Lemma
|x c|l/|| e= [2(1 (M++)
(45)
z0 arg max [x)), then for la xol - 1/c we have [f(x) 2 (1 |x xo (f)))
and
/" 1/c (1-tc))(((50))22 11
|| 2
(46)
0
implying the desired result.
Consider now the expansion of fr over different frequency clusters:
fr ftr
(47)
where Jer denotes the I--component of fr. We first show that we can discard the components associated with unbounded frequencies.
Lemma 3. If fr converge f. uniformly on [0, 1], then far also converge to f. uniformly on [o, 1].
Proof. Step 1. Let us first prove the statement in the case Sa = Observe that each ft,- can be represented
fer
Σ g
(48)
where It.r.1 = It.r,-1 and Gt.r.q E H2N with some Ω independent of and r. We use this representation for except I = to (since stn. H already):
fr = fto.r
iqui. Dt.r.a
(49)
tftto g=#1
15

---

Then.
I 12 = (fr. fr)
1
cross-terms.
(50)
tylto q=#1
Observe that product of g HMO belongs to H ( M2,20 follows that each cross-term can be written as
(c gr),
(51)
H where Awr " oo and gr E (2N) 20 the function 9, being a product of two functions out of the collection F = (hoort ((
We have
(e ا96' = J/² E e-
gr
(52)
-Aww/ 1 S." (r(2))de -dws
(53)
Aww/ -2 22119-11o0 + 1/ e-sser of (zx)dx)
(54)
Au,1 (2 c)l1gr1lo
(55)
where we used the inequality l +l I c||gr|>> with constants c(N, 52) as established in Lemma Observe that if 9r product of functions from the collection F, say g, h, then have
| S ||/||>/|/||l>>
S C' C' |
(56)
with another suitable constant C C(N, ()) by Lemma 2 It follows that the cross-terms in Eq. 50 are dominated by the explicitly written terms:
(cross-terms] -o (111to
(9 - 00.
(57)
tf g==1
Therefore, if 1l o(1) as a 00, then we also have
1l = O(1 O(lfflll) = O(1lfllmm) o(1)
(58)
and similarly all
119t.rgl1>0 o(1)
(59)
Step 2. Now prove the result for general f.. If [|5r ffal2 then the sequence fr is Cauchy:
lim lim Ilfr Sry || 0. 700 +20
(60)
We write
fn fre (femm - flors) +
St.ri
9t.rz.4
(61)
totto g=#1
ty 9=#1
Assuming that 12 (2(11) and grows sufficiently fast, the frequencies Wt.r Wt.rz and 0 (correspond- ing to the first term) will form disjoint clusters. We can then use the argument from Step and conclude that all l|gt = o(1), implying the desired result.
The last lemma shows that any uniform limit of functions fr H((2) also a uniform limit of band-limited functions fr E H2M. for some Ω co. Any function E H is solution of the differential equation
(2
D,f, = 0,
(62)
where
N
D,
II
iwr ( + iwwr)).
(63)
du
==1
16

---

If the frequencies war are bounded, by compactness we can find their limit points cap- We argue now that the limiting function f. is a solution of the corresponding limiting equation Df with
D de
(wn) ( + iwa).
(64)
==
Indeed, such solutions have the form
f (zz e A(a-wo) f(ro),
(65)
(cf. Eq. 24 while the functions f. can be written as
f. = - ( (xo),
(66)
with respective matrices Ap. As r + oC, the matrices A, converge (by taking subsequence, if necessary) to A, and, by Lemmal 1 (x0) - [ It follows that the function f. indeed is representable in the form (65). i.e. is solution of equation Dʃ = 0. This immediately implies the claim of the theorem (with isolated zero limiting frequencies win 0).
Proof 2 (*diseretzzaiio--aase") Our second proof essentially relies on discretizations of the function and will consist of two steps. In the first step we introduce the discretizations, show that they satisfy discrete difference equations, and describe general solutions of these equations. In the second step we analyze how discretizations different length scales agree with each other and show that the continuity of f. enforces representation (6) in the zero spacing limit.
Step 1: Discretization. Suppose that function S. is the uniform limit of functions fr () r 1,2,... Fix some Ar > O and consider the sequences u² = (ug) (ux ),=0 [ obtained by restricting these functions to the points sAr:
[1/Aa] and (())
u fs(Arr), w!?) fs(rr,), 1, /1/aa].
(67)
Since fr H2() each sequence (r) can be written linear combination
(()) HWarewn + bbree hwnree s s =,0,,.... .........////)
(68)
with some complex amplitudes bar C and frequencies war E R (the horizontal bar denotes complex conjugation).
We want to perform now the limit r > oo and derive a similar representation for u*, To this end observe that, up to the boundary values, a sequence of the form u, bes satisfies the finite difference equation
(T ewwd ju O,
(69)
where T' is the left shift:
(Tu), Ug+1-
(70)
Since each sequence (r) has the form of linear combination (68) and the operators T giwAx commute, it follows that (r) satisfies the finite difference equation
(
[T
Sunr AT Rien Ar Ju( 0.
(71)
1=1
This equation holds up to the 2NV boundary components (r) that are moved by the shifts T' contained
in (r) outside the domain [0, 1] of the functions fr.
We would like to perform the limit - oo this difference equation, we cannot directly perform it in the exponents Ar, since the frequencies war may be unbounded and not have any limit points. However, the values awarr& belong to the unit circle in C, which compact set. Therefore,
can choose subsequence Tt such that e twar Ar - 2 as f + co, with some 2 C, 2 1.
17

---

Performing this limit in the difference equation, we then see that the limiting sequence u² satisfies difference equation
N II IT ju" = 0.
Du
def
u
(72)
general solution of this equation is again a linear combination of sine waves, but with possible resonances due to repeated values 2,, Suppose that the numbers 2,, contain K distinct nonreal values
21...., 2 with multiplicities Mr 2 1. Additionally, let M+ 2 0 the multiplicitiis the real
values = = +1 among the numbers =.. We can then write the general real solution of equation 772
as
2M
2M
K M 11
U. = Σ
mmm 8 (-1)² +
Σ m=0
8h (hkm 2 + bkmm2k)) ))
(73)
==
R=1
m=0
with M_ + MM Ek=1 M& N. Equivalently, we can write
2M-
2M
K Mc-1
u'
m
Σ
b bmm V+mm
(bkm Vkm + Djene Veem
(74)
where we have introduced the vectors V=,mm Vem Vkm
Cl1/An]+1 with components
(U+.)) = (=+1), (Njm)) = - 8 (ukm) " 2/
(75)
The coefficients bko and b in expansions 73 (74) are determined uniquely as long as Ax is sufficiently small:
Lemma 4. Suppose that Ax S 1/(2N 1) so that dim [1/Ax] + 2N. Then the 2N vectors v.mm Vim and Vim are linearly independent and the coefficients m bkm are uniquely determined.
Proof. For 1 S S Mr consider the finite difference operators Da.g obtained by removing the factor (T =x) from the operator D that appears in Eq. (72
D
Dx.g = (T- )
(76)
When applied to u", this operator kills all the components of the expansions (73) associated with 2ạ and having degree m 2 M2 - q. In particular.
774 except those
(DR.1")) a.bb.Me-1
(77)
with the explicit coefficient
ag (Mr 1)!(ze 2σ) Me
II
((2x zx) 2 + 0.
(78)
(E KMM)
We can then find the coefficient bR.M,-1 from Eq. 77 if there is at least for which it holds (recall that not applicable to a few boundary values of s). The highest power of the shift T appearing in DA,1 T 72N such exists long dim u² > 2N.
Having found bR. 1,, we can subtract the corresponding component - apply to the remainder the operator Da.2, which will kill all terms except by -V.M, -2 This allows to determine the next coefficient by, - Continuing this process and extending it to other zk and 24, we uniquely recover all the coefficients bt.ms bkm- The linear independence of the vectors Vi.m Vm and Vim follows from this uniqueness.
from u² and
Step The limit Ar + 0. We consider now discretizations with variable spacing Az. Our goal
(73) lead to the desired representation (6) in the limit Ar - 0. In the notation, we will occasionally add Ar to the subscripts to reflect the dependence of various quantities on the discretization spacing.
is to show that expansions
18

---

It is convenient to rewrite expansion (73) by rescaling the coefficients via 6km Ckm ( (Ar) ym and
introducing frequencies wi and w- such that 26 e"My and -1 elw so to make the expansion less Ar-dependent:
" f.(sAr)
(79)
2M
2M
Σ
C- (=m(sAx)) e aAw Σ
C+.m C+,m(sAz))
(80)
K Ma-1
($Ar)
(Ckme
Ckme iwkddr)
(81)
m==
The frequencies wh; w are determined from the values AR,An only up to integer multiples of 2nr Ar:
def
+ 2xl
Wk EWA.AW
(82)
Ar
Jeez'
def f
2
w- EW -,A
(83)
Ar
JIEZ
Observe that expansion 799 appears in it only through the combination sAz, if this expansion holds for some Ar, then it also holds for any integer multiple Az' (Ar, with the same coefficients c=.m; Ckm and frequencies wk
81) is invariant under downscaling, in the following sense. Since s
To discuss this effect more detail, we argue now that we can establish a correspondence between different values 2n across different scales. In general, downscaling is accompanied by aliasing: if difference equation (72) holds with the values 2,,A on the length scale Ax, then on the integer multiple length scale Ar holds with the values
(2
(84)
In particular, the values Ar that are distinct on the length scale A may collide when mapped to the length scale lAx. However, in our setting we can bound the number of collisions thanks to the finiteness of the set frequencies.
Specifically, consider length scales of the form 2 AAr, with t = 0, 1, The total number of collisions over all t is bounded, since there are at most K N distinct values 2g. It follows that at sufficiently large there are no collisions, so that the number K = K₁ of distinct values 24,2 Ax is the same for all 1, and we can enumerate these values so that for 12 > 4
kk 4 Ar.
2-2-11 "
(85)
Moreover, observe that for sufficiently large there will be w wi_-component (corresponding to z 1) in the (81). Indeed, since the square roots of -1 are not real, the presence of the -=_-compoeent for some would mean that Ke41 K,- But such an increase is possible only for finite number t's.
Similarly, the w4 componett of the expansion
79
8 must have the form
2M
f~o(sAr) =
Σ
C+.m (sAx))
(86)
m==
with the same c+.m for all sufficiently large f, since any change of this component with is accompa- nied by an increase in Kg. The function f., uniquely extends to continuous function the whole interval [0, 1],
2M--1
f~o(x)
Σ
C+,mx"
(87)
which agrees with the first component in the expansion 16
This discussion shows that without loss of generality (by subtracting So.0 from f. if necessary), contains only the last component, standing in line (1).
may assume that expansion 79
(8
19

---

Assuming that transition from the length scale Ar to Az' = 7A occurs without collisions in 2k. the downscaling invariance condition can be written as
Az Alm,An';
(88)
WR. A. WR,AZ',
(89)
where the sets W are defined by Eq. (82) By Lemma the coefficients Clm,A are uniquely determined as soon as Ar and Ax' are small enough.
Considering again the length scales of the form 2 2'A,,, we get a nested sequence
C W C Wk,,- 'do C WA,Ar-
(90)
All the inclusions here are strict. The intersection
Wk.li n Wk,2 -Ar
(91)
is either empty consists of a single frequency }- J- In the latter with fa,0) identify the respective component the function fa:
again (as previously
f=,(z)==
Σ
x (Ckme + Ckmn fwnzr)
(92)
Our goal is to prove the that the intersections kkli are indeed nonempty for all k. We will obtain this as a consequence of the continuity of the function fa, which in turn follows from the fact that f. assumed to be a uniform limit of continuous functions fr.
To this end, observe that when upscaling from 2z to 2- Av. the value = is one of the two square roots of =x.2-tAr- The case WI.lim f corresponds to the case when for all sufficiently large / we take the square root with positive real part, so that
2x.2 'Ar 2 1.
(93)
In contrast, in the case Wk.lim 0, for any tu there is t to such that 24,2-11Az has negative real part, so that
2k.2 Ar +
(94)
Now consider the vector u obtained by sampling the function f. at the points sAr as in Eq. (67).
Consider the sequence (++.t) of vectors the same dimension, obtained by sampling the function f. with additional shifts 2-AAr:
( (a((s+27))
s s= 0, 1,.1................ dim u 1.
(95)
Since f, is continuous,
(+.1)
(96)
Recall that the vector u admits expansion 74) over the vectors Vi,m, Vkm Vem As mentioned earlier, we can assume without loss of generality that there are no Vt.m terms:
M
(bem Vkm + Dkm Vkm)..
(97)
Observe now that an analogous expansion can also be written for the shifted vectors:
Mc-1
(bkm v km
+ +kem V 'mm
(98)
A= m==
Moreover, the vectors Vim are either exact or approximate multiples of the vectors Vimi
m 0, km 22.2 'Ax Vmm + +1) (t (t), m > 0.
2h.2 AAx Vkm-
(99)
By Lemma the vectors Vem and Vkm are linearly independent for sufficiently small Ax, so convergence (66 requires all those coefficients Z for which bum + 0 at least for one m to converge to (as in Eq. (33).. This proves that all Wk.lim are non-empty for such A. If for some k we have bem = for all m, then this k-component effectively missing and can be ignored. This completes the proof of the theorem.
20

---

B Proof of Theorem 5
Our proof will consist three steps. In the first step we show that the polynomial constraint claimed in the theorem holds for functions of the form e((z), the second step we show that if polynomial constraints hold for the arguments of an algebraic function, then its values also admit a polynomial constraint. In the final third step we combine these results to complete the proof the theorem.
We remark that our arguments are close to the arguments the theory of functions [16] 17], but we work in discretized setting of uniformly sampled data without considering any derivatives.
Step Polynomial constraints for exponentials polynomials. Consider the function
g(z) = e((2
(100)
where P is (possibly complex-valuedd polynomial of degree s d. Consider operators Dj, of forward discrete derivatives of order s with step h:
(x)))) = (D) g( + h) Dj 9(x)) = _... h
Σ (-1)
(5) 1
g(x (z)
kh).
(101)
We have D= for any h C and any polynomial P of degree d:
Σ (-1)dt+ dd ( kh)+ 0.
d+1
(102)
k=
Separating the positive and negative coefficients, write this, equivalently, as
(d+1)/22
[d/2]
(d+1)
d ++11
Σ
P(x + 2kh) =
Σ
P(x + (2m 1)h).
(103)
2k
2m +
K=
m0
Exponentiating, follows for g(x) given by Eq. 100p that
[(d+1)/2
[d/2]
II
(g(x 1o(x+2k0 2kh))
II
(g(a (2m + 1)h)) O.
(104)
m==
We can view this as a polynomial constraint of the form
R(g(z), g(x + h).... g(x + (d+ =
(105)
with some fixed polynomial of d variables.
Step 2: Extension of polynomial constraints to algebraic functions. Lemma 5.
1. Suppose that Q VI...., UN) is an algebraic functtionn and go tions satisfying polynomial relations
are func-
shi) =0 Vx, h. R2 (g (2), (n( h), .n. (x
(106)
Let g(x) Q(90()) ..... .x((x))))) and m 2 s(N + 1). Then there exists nontrivial polynomial R of m + variables such that
R(g(z), g(z + h)..... gx + mh)) = 0, Vx, h.
(107)
2. Moreover, suppose that the function Q is not fixed, and is only constrained by its degree
deg Q < q and the degrees deg de S of the polynomials appearing in its definition. Let
2 (q + () (N+++1) s(N 1). Then there exists nontrivial polynomial R of m + 1
variables such that relation 107
holds for all such Q.
21

---

Proof. 1. Recall the defining relation 7 of the algebraic function Q
oz(20..... ................................ (z). (..;....; = 0.
(108)
We can use this relation to express Q4 in terms of lower powers ,u...., QU-1
(2o...... -0 (z0. 00) 2N)
Φn (zo....., 2x) (2........
(109)
k=0
By iterating this relation, for any powert 2 q we can express Q' in terms the powers Q", "...,,
O' ... 2N) 0, (z0
S (=0 ... , EN):
(
(110)
where dh.& are suitable polynomials of degree not greater than / max deg or. Substituting
In = (n(,,
we get
Q'((()) = 0, (g()))
Σ Se (g()))))))(((()))
(11I)
R=
where for brevity we have denoted g(z) =
(N())).
Formula (IIl remains valid if we replace by x + 1h with any Consider various monomials in the variables (g(( + Ih)) for m. m:
F.
II
(g(x Ih))
(112)
1=0
(g(z (o + 1h))
Σ
..... m
(113)
1=0
No
R..
where t = (to...., tm), = (ko,... (m + ()(xax) ti) max; deg ob,, and
km), Lt.k are some polynomials of degree not greater than
m Q (g( Ih)) 1=0
(114)
Our goal is to prove that for sufficiently large m. the monomials F, are linearly dependent (with some coefficients independent of æ and h), which is exactly equivalent the existence of a polynomial R satisfying relation 107). This is done by showing linear dependence of the expressions (113) with different
Specifically, observe that, regardless of t, expressions 113) contain only finitely many (namely, 1n+1 different components Qk. Since there are infinitely many monomials Fe, it follows already from this observation that there exist nontrivial vanishing linear combinations of the monomials F; if the coefficients these linear combinations are allowed to belong to the field of all rational functionn of g(x)....,gg g(x t + mh). However, we need to show that nontrivial vanishing linear combinations can be found even with constant coefficients.
To this end, we will further reduce the combinatorial complexity of expressions 113 by removing
rational functions of the variables yn (x + I'h) with l' > I. Recall that each On. is subject to polynomial relation (106). transform polynomial functions of g(x) into rational functions of
high powers of the variables 9n, (z + Ih) the expense of introducing
We can these relations g(x). g(x + l)...., g + sh) that contain only bounded powers of g(r). Specifically, isolate the variables gn (z) in the polynomials R2 by writing equations (106) in the form
d.
Cnn (x + h)) (z) sh)))) =0
(115)
22

---

with suitable polynomials Vn.yj of the remaining variables In (I + h...... In + sh). The value d, is the degree of 9n (x) this representation. Then, similarly to how we did this for Q, we can express
-hn (x) -Un (gn (I h),.... ..... gn + sh)))
Σ
Vns (I ht...... sh)))s? (r).
(116)
By iterating this relation, for any t 2 dn we get
(x) = V (gn(x h...... ................................ (x a + shh))
( h)..... 19(( + sh)))ss (r).
(117)
with some polynomials thnji. of degree not greater than max, deg Ung- This relation remains valid we replace x: by + th with any 1:
gi 1h) Vnaa, (gn(x + (1+ 1)h), 1) (3))))))
(118)
dn-1
Vn +
(n + (1 s)h)))) th).
(119)
We can now transform expression 113 by first replacing there all powers d, of (x) with powers t < dn, and rational functions of 9n (x + h)...., 9n (x + sh), then replacing powers t 2 da of gn + h) with powers S d, and rational functions of 9n + 2h). .... I. (s + 1)h), and so on. We continue this process while the involved variables g(x [h) obey the condition I m. As result, we obtain rational function of the variables g(æ)...... g(x mh) that contains only powers of the variables In (æ).... , (2: + (m - 8) 8)h) not exceeding d.
To establish the desired linear dependence, we want the rational functions appearing in these transfor- mations the monomials F to have the same denominator for all t. is convenient to ensure this in the following way. Choose some large I and assume that all the powers & in the monomials Fe vary between 0 and T, so that in total we have (T + 1) m++1 monomials. In expression (113), instead of the denominator I[ (g(x [h)) use the common denominator
Zn
II 1=0
0 (g( Ih)).
(120)
This changes the polynomials Ft.
== ZT Σ
(( g(x +
(121)
k
the new polynomials ft.k now have degrees not exceeding (m + 1)T max; deg Φs. Now we perform the iterative substitutions of the powers gt, (x + km) in the polynomials P,,x as described above, while keeping the same denominator for all t; this requires multiplying the common denominator by appropriate powers of dn,d, (gn (x + (1 + 1)h),..., In (1 +))))) As a result of this process we obtain expressions
F = 7
Q
II O
dhd 1h) V Ve.k. + (m + 1)h). .g( + mmh).
1=0
(122)
Here J= (Jan) is a matrix with elements 0 < Jul S d, - 1, so summation over finite. The polynomials Ve.k.. only depend the remaining variables g(x + (m + ... g(( + mh).
Importantly, by taking into account previously observed bounds on the degrees of polynomials appearing in Eqs. (119) and (2T), we observe that deg V Vt,k.J < CT with some constant C depending on 8, m, N and the degrees of the polynomials dà and Pny appearing in the assumed expansions (108) and [15)
23

---

Now the desired linear dependence of the monomials Ft results, with a suitable choice of m and T. by comparing the number (I + 1)m=+I of different monomials Ft with the number of different monomials that may appear in the expansions of the polynomials V Vt.k,J. Since these polynomials depend on the s(N + 1) variables g(x + (m - 8 + ...)...... g(r + mh) and have degrees not exceeding CT, the number of different monomials in them does not exceed C (N+(( with some constant Ci depending on the same parameters C. Taking into account that the summations 122 involve, respectively, qm*+1 and II dn dm-=+1 terms, we that the (T + 1) monomials Fe belong to a I == d 1ma=*+> + 1 (ttt))/((++)))imeeeeeee dimmensiona linear functional space. Accordingly, if s(N +1] < m++1 1, then some of the monomials Fe will be linearly dependent T is large enough. This completes the proof of part 1 of the lemma.
over k and J in expansion
2. The argument above produces nontrivial linear combinations of monomials Ft with coefficients generally dependent on Q. We show now that, assuming appropriate degree bounds for Q and choosing larger m, one can find nontrivial linear combinations with Q-independent coefficients. To this end, note that the main obstacle to choosing Q-independent coefficients is that the polynomials Ve, k.J in expansion (122) are Q-dependent. To overcome this obstacle, we express these polynomials both in the variables g( x + (m 8 + 1)h), .... g((: a + mh) and the coefficients b of the polynomials
Ve.k, + (m- 1).)..... g(x mh)) lekk (b. (m- s + g(x mh)
(123)
Here, the vector b includes all the coefficients of all q + 1 polynomials 6x appearing in the defining identity (08).. By retracing the steps to construct the polynomials Vt,k,, we see that their dependence on the coefficients b indeed polynomial. Moreover, deg Wtkk. again bounded by CT, where C is some constant possibly dependent on N, s, q, max deg ΦR. max, deg Unnj. but not on T. Since we assume deg 6R S r, we have dim b S (g +1)((* (N) The total number of variables in Vt.k.. is thus not greater than
N ( + s(N +).
p= (q
(124)
N
We repeat now the dimensionality- based linear dependence argument. The total dimensionality of polynomials Vt, considered at all k, is O(TP). On the other hand, the number of monomials F, is (T + 1)m+1. If we set m 2 p. then for sufficiently large T we can find a nontrivial vanishing linear combination of Fe with coefficients independent of Q.
Step 3: Proof of Theorem
We apply now Lemma 5 to our setting in which ga(x)) and N. We know from Step that for k = I,..., N conditions (106) hold with s deg Ps + 1. For go. condition (106) holds with s = 2
(x) = (P)(2) h: = 1 I....,N.
go(x) 2go(x (x + h) + g0 + 2h) 0.
(125)
Since assumed that deg Ps S d, we can set max(d, (d, 1) + 1 as a common value with which condition (106) holds for all n = O,..., N. The conclusion of Theorem 5hen follows from statement 2 of Lemma
C Proof of Theorem 6
Since the network has not more than 2 hidden neurons and each of our activation functions has at most two branches, the output g(x) of the network at any belongs one of at most 2 branches represented by analytic expressions. Consider each of these branches as defined for all x E [0, [0 and N' ar..a
denote the family of all branches resulting from all g E ((()) by ( Observe that N if N' 9, r, d are large enough. Indeed, the input of any algebraic-exponential neuron is polynomial of degree not greater than d = 2 (if the squared ReLU is present; otherwise, if only the step function and ReL.U/leaky ReLU are present, then one can take d = 1). All the considered algebraic-exponenttal activations are rational functions of x, e or = and the subsequent neurons are polynomial, so any branch of the full network can be written in the form (8) with a rational Q and 2N as the number of its exponential arguments. Rational Q's have algebraic degree q = 1. The maximum degree of the
24

---

polynomials 6% appearing in the definigg relation 7 does not exceed r = 2 (again, if the squared ReLU is present; otherwise one can take r 1). Summarizing,
H 4) N
H (3)
(126)
2N.12
Theorem 5 implies now that there exists some in and a nonzero polynomial R of + variables such that for any ÿ H and any size-(m- + 1) arithmetic progression ã, ā + h,..., mh E [0, 1]
R((()) p(ā + Ta + 27), 2h),...,ā(( + mb)) = 0.
(127)
We need to obtain a similar relation (TT). but for g E H& Each value g(a + kh) in Eq. [II belongs one of the 2 branches g H which associate with p 2 colors. By applying van der we that if we set a a m/ appearing in Eq. (11 contains at least
Waerden's 's theorem with p 2 and m
Nuaw (m + 1,2
then the length-(m- + 1) progression a, a +-a++1 h,...,, one l + 1) sub-progression ä. + h..... ā mh which the values of belong to the same branch. We can then satisfy condition by defining the polynomial R by
R(zo. ...,, 2m)
Rizeo Zom):
(128)
6 (80)).18))))
where runs over all length-(m progressions from the set (0,............. , m].
D Proof of Theorem g
The "only if" part follows from Theorem The "if" part is generalization of Lemma 1 from 29]. Suppose that a is not polynomial; we want to prove that H E G, By absorbing h in a, we assume that ar (0)
csin(wo Consider an arbitrary finite subset X = {x1...., EN C [0, 1]. By Theorem 2 it is sufficient to show that there exsts b E [-1, 1] such that the values (bz ). ... o xbrN) are rationally independent. Suppose that this is not the case. For fixed coefficients = (A the function (b) >N o real analytic for E []. Since there are only countably many À E Q.N, there is some X such that σ vanishes at uncountably many b [1. Then, by analyticity, σ = 0 on [-1, 1]. Expanding this σx into the Taylor series at 6 = we get the identity Σ An 0 for each m such that a d (0) f Suppose that Ia have the natural order S x < <... < EN. If there dum (0) * O, then, by letting m co, we first show that Av = 0. then A 0, etc. If r > 0, then we exhaust all Xn in this way; otherwise we exhaust all except A1. However, A 0 follows then from (0) * O. Thus, either À = 0 or is polynomial, which contradicts our assumption.
0. Dropping then h, we specialize f(x)
are infinitely many m for which d'
E Proof of Theorem 9
Suppose that the function sequence fa(x)) on oin(w, hv) converges to nontrivial limit point fu. By a compactness argument, this requires at least one of the parameters Cus Wn to be unbounded. We expect unboundedness of one parameter be compensated by another parameter converging to 0. Accordingly, we consider three possibilities: Wn + 0, wn + w of 0 and wi, + co. One of these possibilities can always by ensured by choosing subsequence of fn. if necessary (in the sequel we will without further mention repeatedly use such reductions based on compactness and/or transition to subsequences).
Case 1: w, - 0. Since (bnar) is uniformly bounded by our assumption and sin is periodic, we can assume that wn + hn "=>30 with some constant [0, 2T), for all x [0, 1]. If a + J, then the limit fo can only be trivial, a constant. Suppose that a = 0 (the case = π leads analogous results). In this case J' (x) en (b,,,) h (1 o(1)) so (x
lim en (b,,)) + hn). There are two possibilities: b, + b f 0 and b, - 0. In the first case we obtain nontrivial limits
f+(x) ao(bx) +c, a, a.
(129)
25

---

In the second case we can Taylor expand
a(b,,x) (0) + d'a der (0)(b,,)* o(b)), da (0) +
(130)
dur
A nontrivial f. requires c, to have a finite nonzero limit. In this case, by adjusting hn obtain nontrivial limits
(x) do + a, ag dy IR.
(131)
Case 2: Wn - w o O. Consider again the two possibilities: bn + + 0 and bn - 0. In the first case we do not get any nontrivial limits. In the second case we again have Taylor expansion (130).
Arguing as in Case 1, the only nontrivial limits that we can produce are of the form (11))
Case Wn + so. In this case we must have b, + O, since otherwise sin(w,, + h.)) will have an unbounded number of alternating values =1, so we must have + 0 and accordingly the only possible limit f. 0. It follows that we again have expansion (330). and
(x) = on sin (wn(( + 1 d'e de (b) + o(b) hm)
(132)
To avoid triviality due to an unbounded number of alternating values +1 of sin, we must have b = O()) We get new nontrivial limits of fn when bn has nonzero limit:
fx) = esin(av + a,,"), a, 0, E R.
(133)
F Proof of Theorem 10
We need to prove that H (0) E 91 and H $ Gz.
Proof of (5) E 91. For N 2 2, this property can be concluded from Theorem 8 since we can just set (zx) = sin(x) and h = h sin x a/2) in this theorem. In the case N observe that in the proof of Theorem we only use Then, this proof becomes applicable to the family f(x (sin(wor(bx)) with ozz) sin(x + h)
redefine
that (0) o O; otherwise we can set
and any phase # ok, E; this is subfamily of H (5)
N=1'
Proof of (1 & G2. We will show that we cannot obtain a general continuous function as limit of functions from (5) because any such limit has particular restrictive form.
We write (x) Cn sin(gn (2n(z)) + hn and consider several cases depending on the behavior of c..
Case Cn - 0. this case the limiting function is constant: f-(x) =
Case 2: On + + 0. In this case hn must be bounded and hence can be assumed to converge to some h (by possibly choosing a subsequence). Denote on, (v) = Cn sin(y) (y) + hni then Φn (y) converges uniformly on R to (v) = csin(y) + h. Clearly, the functions f (z) (g also uniformly converge to fa.
Consider now two alternatives: either the family {gu} is uniformly equicontinuous, or not. In
the first case, fix some point zo E [0, 1], let Fn
[a(zo] and consider the shifted functions (x) = gn (x) - 2TTn. We have o. (g.(2)) = o. (g. (x)), the family (G.) is also equicontinuous. and In (2r) E [0, 2nr for all n, that the family {gr) ) is additionally uniformly bounded [0, 1].
Then, by the Arzelà-Ascoli theorem, the family (Tr) contains a uniformly convergent subsequence.
It follows that describes all such limits.
o. (g.), where 9. is uniform limit of some functions from H N+ Theorem 4
In the case of the second alternative, there exist e > O and subsequence In, such that for some
Js, 2i E [0, 1] we have |. 1 x - 0 while 19,, (xxa) - In, (a')) ) 2 e for all s. Letr, = [___(_.) (s.) and
Ta (x) In, (1) 2nr,, Then (xx)) ) E [0, 2x and by choosing a subsequence we can assume that
Is (2.. converges to some y. E [0, 2m) Using [g (x..) (=("')) 2 and the continuity of Gs. we can
then assume that T. (z()) converges to some y. # ye. Also, can assume that I, and z converge to
26

---

some [0, 1]. Then, by the uniform convergence of Fn. (u) 1in, (x) fxx)) + 0 as
co. On the other hand, fn, (x) = (9n, = o. (3)((x)) so that, by the continuity of J.,
lim sup - fx.)) [c(r)
sup
( fxx)) +0, 0,
(134)
vE(v..u]]
because dh in nonconstant any interval |ye v4]. This contradiction shows that the second alternative impossible.
Case 3: Cn - In this case the range of In must shrink, since otherwise the range of fn would be unbounded. Taking a subsequence, we can assume that for some yo E [0, 2n] we have On (x) 1/0 2mm, (1) uniformly on [0, 1]. We can then Taylor expand
(x) hn On sin( cn cos(vo) Yo 2xm,,)
(135)
o sin (gn) yo 2 c. O(gn yo )))
(136)
If (Bs( * O, then the respective term dominates the higher order terms and must be bounded as increases. We can then discard the higher order terms, and we see that f. is a uniform limit of the functions Cngn
with some ag.. These limits are among the limits of the family H (2) covered by Theorem
N again
(3s( = 0, then the respective term vanishes and the next, second order term will dominate the higher order terms. In this case f. is limit of functions of the form vin h,, + 0n(9r. b,)
Substituting 9n. E H and expanding products of sines, we see that v/, E HH(2) the limits of vh are restricted by Theorem
1+2(N+ 132 so, again,
27


Reviews:
[{"review_id": "5DqlHjhgWB", "reviewer": "Reviewer_BXX4", "summary": "The authors study \"universal formulas\" -- specifically, families of parametric\nmappings $(f_{\\omega})\\_{\\omega \\in \\Omega} \\subset C([0, 1])$ where $\\Omega$ is\na domain in a finite-dimensional euclidean space, such that $(f_{\\omega})$ is\nactually dense in $C([0, 1])$ with the sup-norm -- motivated in part by\napplications to neural networks. In this connection, universal formulas should\nbe contrasted with typical \"universal approximation\" results for neural\nnetworks that state that various fixed-depth neural networks can approximate\nany continuous function on $[0,1]$ by *increasing the number of neurons*\nsufficiently; universal formulas achieve this approximation with a fixed number\nof neurons by instead exploiting (at least indirectly) unbounded-magnitude\nparameters and infinite-precision arithmetic. The authors present a hierarchy\nof nested expressiveness classes -- in decreasing order, families with infinite\nVC dimension, families that achieve arbitrary approximation on arbitrary finite\nsets, and families that achieve arbitrary approximation of arbitrary continuous\nfunctions (i.e., universal formulas) -- and study obstructions to a family\nbeing in a class higher in the hierarchy, but not a class lower in the\nhierarchy. Starting from the classical example of the infinite VC-dim class\n$\\\\{c \\sin \\omega x\\\\}_{c,\\omega \\in \\mathbb{R}}$, the authors prove using\nalgebraic methods that a fairly general class of\n\"polynomially-exponentially-algebraic\" expressions, which includes neural\nnetworks with topology given by a (fixed size) directed acyclic graph with only\none \"algebraic-exponential\" activation on any path to the output (e.g., $\\sin$\nactivation, $\\tanh$ activation) and arbitrary piecewise-polynomial activations\notherwise (e.g., ReLU), cannot achieve the arbitrary finite approximation\nproperty.\nResults for networks achieving finite approximation but not being universal\nformulas are slightly less general, due to technical challenges: the authors\nshow, for example, that classes $f(x) = c \\sin (\\omega \\sigma(bx) + h)$ achieve\narbitrary finite approximation if and only if $\\sigma$ is non-polynomial, and\ndemonstrate that for a certain sub-class of $\\sigma$ maps studied earlier\ninvolving $\\sin$ activations, the resulting class does not have the universal\nformula property. This kind of mapping can be viewed as a one-hidden-layer\nneural network with one neuron on the hidden layer and $\\sin$ activations; they\nconjecture that the same separation holds for similar architectures with\nmultiple neurons in the hidden layer. \nWith these results established, they discuss known results on architectures\nthat do constitute universal formulas, and possible paths to characterize\nnecessary and sufficient conditions to be a universal formula further.\n\n", "questions": "### Questions and Comments\n\nDoes the \"GeLU\" activation function ($x \\mapsto x \\Phi(x)$, where $\\Phi$ is the\nstandard normal cumulative distribution function) satisfy the\nalgebraic-exponential property? I am not sure if it would, because it is\ndefined with an integral, but if so, it might be interesting to mention here\n(this activation is used in some modern transformer architectures).\n\n\n### Minor Fixes\n\nCaption of Figure 1: typo \"uiversality\"\n\nLine 186: the $2\\pi$ is on the wrong factor in the quotient? (the reals,\n\"modulo\" $2\\pi$).\n\nLine 187: is this supposed to be the \"fractional part\" operator (based on its\nspecified domain) rather than the \"floor\" operator (which as I understand gives\nthe next-lowest integer)?\n\nLine 345: \"Then the existence of a ...\" -- should this be \"Then there exists\na...\"?\n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The writing, both technical and expository, is clear and precise. The authors\ngo to great lengths to present a broad view of the problem and prior work in\nthe introduction, which makes the subsequent technical analysis accessible to a\nnon-expert reader.\n\nThe authors defer more technical proofs to the appendices, but always give a\nclear indication in the main submission what the types of arguments developed\nare (e.g., algebraic methods vs.\\ Pfaffian function theory). This will make the\nwork useful for follow-up work.\n\nThe discussion section (section 8) seems uncommonly interesting for a\nsubmission in this venue, in that it lists several open problems that the\nauthors' work suggests, and which should lead to interesting follow-up work.\n", "weaknesses": "It is not a weakness per se, but as the authors themselves note, the\ninvestigation is mostly of mathematical interest as \"... the universality of\nuniversal formulas is... an idealization that requires their parameters to have\nunbounded precision or magnitude\". Nonetheless, there are neural networks\ncommonly used that have structures similar to some of the near-universal\nformulas studied (the authors mention SIREN, which uses periodic activations in\nneural radiance field learning), and these kinds of periodic constructions have\nbeen shown to be useful in studying general deep/shallow neural network\napproximability (e.g., work of Telgarsky).\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the careful reading of our paper and giving a very detailed and careful summary of our work.\n\nIndeed, the GeLU function unfortunately does not belong to our polynomial-exponential-algebraic class.\n\nAll your minor fixes are spot-on (except for the last one: we did actually mean \"existence\" because our statement was about the decidability of an existence predicate; we will rephrase this sentence to make it clearer).\n\nThanks again for many useful comments and positive evaluation of our work!"}, {"review_id": "4W2uUhNLud", "reviewer": "Reviewer_FCbX", "summary": "The authors isolate the study universal hypothesis subclasses of $C([0,1])$ for the compact-open and point-open topologies respectively, and they compare universality here to infinite VC-dimension.  The results are interesting, though perhaps not that surprising nor novel, but are still publishable (in my opinion).\n\nSome of the author's derivations could use more mathematical rigour and the terminology \"formulas\" is misleading as it alludes to logic/model theory, which does not appear in the paper.  The authors could also add some references to approximation theory in ML (some of which I provide below) to better tie in their results.  Details below in the Weakenesses section.", "questions": "- Related to requested change 2: is there a topology $\\tau$ on $C([0,1])$ such that $\\mathcal{G}_{\\tau}=\\mathcal{G}_0$?\n- In the proof of Theorem 2, does one really need to index over $\\mathbb{R}$; isn't $\\mathbb{R}\\setminus \\mathbb{Q}$ enough?\n- Why do you call these formulas?  Is there any connection to logic/model theory?  To me the correct/standard term is universal hypothesis/function classes, in the context of approximation theory and universal approximation theorems.", "limitations": "Not really, but this section doesn't really affect this paper.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "As stated above, the results are interesting, though perhaps not so surprising.", "weaknesses": "0. Add details to all proofs.  My main issue with this paper, is that many of its proofs contain handwavy and imprecise statements such as: 1) \"Specifically, isolate the variables gn(x) in the polynomials\" (line 739-740).  This is not rigorous and vague 2) equation (94) what space is this limit taken in; to me it seems to be $\\mathbb{C}$ with its modulus as a norm, or 3) \"by a classical theorem of Kronecker's\" on lien 188; which one? (citation missing)... There are many such instances in derivation.\n\n**Requested Change 0:**  Make all proofs rigorous and remove handwaved details (clear limits, clear steps, no missing references)\n\n1. This sentence \"especially dangerous from the generalization point of view\" is purely speculative in the context of the paper, and one can doubt its accuracy [4] and [5] on benign overfitting for high-capacity models.  \n\n**Requested Change 1:** Since the authors only deal with approximation, they should remove this claim in the final version.\n\n2. The hierarchy $G_1\\subset G_2$ in (3) is misleading - The class $G_1$ is simply the set of subsets $A$ of $\\mathbb{R}^{[0,1]}$ satisfying $A$ is dense in $\\mathbb{R}^{[0,1]}$ for the point-open topology, which I denote $\\tau_{PO}$; i.e. the topology of pointwise convergence (see [1] - Section 46, page 281).  So the inclusion of $G_1$ into $G_2$ is immediate and has a simple topological meaning; since $G_2$ is the same but for the compact-open topology (see [1] - Section 46, page 285).  \n\nFrom these remarks, and say Theorem 46.7 and Theorem 46.8 - both on page 281 of [1], imply $G_1\\subset G_2$  and they give a topological interpretation of $G_1\\subset G_2$.  \n\nI point this out because, from this perspective, one has a more general phenomenon.  Let us focus only on continuous functions.  \nConsider the standard poset $(\\mathcal{T},\\lesssim)$ of topologies on $C([0,1])$ with the partial order relation  $\\tau_1\\lesssim \\tau_2$ if and only if $\\tau_2$ is at-least as fine as $\\tau_1$ (i.e.\\ $\\tau_1\\subseteq \\tau_2$).  For any $\\tau\\in \\mathcal{T}$ define the class\n$G_{\\tau}:=\\{A\\subset C([0,1]): \\bar{A}^{\\tau} = C([0,1])\\}$\nwhere $\\bar{A}^{\\tau}$ denotes the closure of a subset $A$ of $C([0,1]$ with respect to the $\\tau$ topology.  One immediately then deduces the contravariant-functorial relation: for all $\\tau,\\tilde{\\tau}\\in \\mathcal{T}$\n$\\tau \\lesssim \\tilde{\\tau} \\Rightarrow G_{\\tilde{\\tau}}\\subseteq G_{\\tau}$.\nSo this type of construction holds in greater generality.  In fact, strictly finer topologies than the compact-open topology (i.e. the topology of uniform convergence since $[0,1]$ is compact and $\\mathbb{R}$ is equipped with a metric - see Munkres Theorem 46.8) and it has been studied in the context of kernel methods [3] (see the strict topology) and non-uniform topologies on $L^1([0,1])$ were considered in [2] (see Theorems 1 and 2) in the context of deep learning.\n\n**Requested Change 2:** Please add such comments circa (3), and emphasize that there are many such \"classes\" between $G_1$ and $G_2$, as well as, below or above then in the chain of inclusions (3).  Clearly the top of the chain consists of $G_{\\tau_{disc}}$ where $\\tau_{disc}$ is the discrete topology on $C([0,1])$ and the *correct* bottom of the chain consists of $G_{\\{C([0,1]),\\emptyset\\}}$ (i.e. $\\{C([0,1]),\\emptyset\\}$ is the trivial topology on $C([0,1])$.  \n\n3. Line 183 - You are considering $\\mathbb{R}$ as an (infinite-dimensiona) $\\mathbb{Q}$-module (vector space over the rationals).  This is not clear for readers who did not have a class or two on algebra during their studies.\n\n**Requested Change 3:** Add an explanation of how $\\mathbb{R}$ is an infinite-dimensional $\\mathbb{Q}$-module.\n\n4. Theorem 2 is not rigersouly stated.  What does \"can approximate any R-valued function on X\".  In reading the theorem's proof you must mean the point-open topology (which in this case consides with the compact-open topology, trivially).\n\n**Requested Change 4:** Remove \"can approximate any R-valued function on X\" in the pointwise/point (in this case compact-open/uniform topologies.  Please write what is meant clearly, with \"the usual for all $\\epsilon$ theres exists an f satisfying .... \" type statement.\n \nWithout this modification I cannot bump my score up to a pass, since the paper must be precise.\n\n5. Missing Reference\n**Requested Change 5:** Please add a precise reference to this hand-waving: \"by classical Kronecker’s theorem\" in the proof of Theorem 2 (it is classical if one has seen such results, but not in general).\n\n6. Branching expressions terminology\n\n**Requested Change 6:** Please call these piecewise functions.\n\n---\n\nI believe the manuscript will be in publishable condition when these changes are made.\n\n**References**\n\n[1] Munkres, James. \"Topology James Munkres Second Edition.\"\n\n[2] Kratsios, Anastasis, and Behnoosh Zamanlooy. \"Do ReLU Networks Have An Edge When Approximating Compactly-Supported Functions?.\" Transactions on Machine Learning Research (2022).\n\n[3] Chevyrev, Ilya, and Harald Oberhauser. \"Signature moments to characterize laws of stochastic processes.\" The Journal of Machine Learning Research 23.1 (2022): 7928-7969.\n\n[4] Bartlett, Peter L., et al. \"Benign overfitting in linear regression.\" Proceedings of the National Academy of Sciences 117.48 (2020): 30063-30070.\n\n[5] Tsigler, Alexander, and Peter L. Bartlett. \"Benign overfitting in ridge regression.\" J. Mach. Learn. Res. 24 (2023): 123-1.\n\n\n**Note** I did not use mathcal since open-review had compilation issues with it...", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comprehensive reading of our paper including the proofs, and a positive evaluation of our work. We also appreciate your many comments, though we respectfully disagree with some of them.\n\n**Requested changes.**\n\n0. We don't actually see what is imprecise in the examples you give, except for the reference for Kronecker's theorem which is indeed missing. \n\n    1) We don't see what is not rigorous and vague here. You cite the beginning of a sentence; the end of the same sentence specifies the exact sense in which the variable is isolated - namely, by expanding the polynomial as a univariate polynomial in this variable with coefficients in the ring of polynomials in the remaining variables (Eq. (115)).\n\n    2) Equation (94) is a statement on convergence of a sequence of complex numbers. There is a unique standard meaning of this convergence known from the basic calculus course; we don't see what is ambiguous here.\n\n    3) Indeed, a reference to Kronecker's theorem is missing. We will add it to the paper (the original Kronecker's paper is [1], and a recent survey can be found in [2]). Thank you for this suggestion.  \n\n1. We don't see why this sentence is speculative. By definition, the models in the class $\\mathcal G_1\\setminus\\mathcal G_2$ can approximate any target function on any finite set, but, in general, cannot approximate a continuous target function on the whole domain $[0,1]$. This means that a model from this class can be fitted on any finite training set, but, in general, outside the training set the deviation from the target will not decrease to 0 as the size of the training set grows. This implies that the model can be fitted, but cannot properly generalize.   \nWe don't see why the papers on benign overfitting that you cite are relevant here - these papers deal with a completely different setting of high-dimensional linear models under special assumptions.  \n\n2. Thank you for this comment. We only consider the classes $\\mathcal G_0, \\mathcal G_1, \\mathcal G_2$ in our paper because they have a simple meaning and because we prove something nontrivial about them. We don't claim that this hierarchy is exhaustive; of course, there are many other classes, in particular those induced by different topologies as you describe. However, we don't see a point in discussing them in the paper since we don't prove anything about them. Discussing topological and other issues would only distract the reader from the essense of our work and make our paper less accessible. As you can see from the neighboring review of Reviewer 2cHj, our work is already criticized for being too focused on abstract math.\n\n3. Respectfully, adding terminology like \"$\\mathbb Q$-module\" would not add any substance to our paper, but would certainly make it less accessible.\n\n4. We don't see why Theorem 2 is not rigorously stated. After restriction to the finite set $X$, approximation becomes finite-dimensional and has a unique standard meaning.\n\n5. Done, thank you.\n\n6. Thank you for this suggestion, but we want to keep the term \"branching expressions\" because it reflects the actual branching involved in the computation of these expressions.\n\n\nWe call our functional families \"formulas\" because they are defined by finite expressions composed of numbers, arithmetic operations and elementary functions. One can think of these formulas as words in a finite alphabet; this connects them to formulas in logic/model theory. It is important in our context that a model consists of a finite number of explicit standard operations. In contrast, general hypothesis/function classes are not that restrictive; even the class of single-hidden-layer neural networks $f(\\mathbf x)=\\sum_{n=1}^N c_n\\sigma(\\mathbf a_n\\cdot \\mathbf x+h_n)$ contains an operationally indefinite activation $\\sigma$, not to mention classes like Sobolev spaces, etc.\n\n\n[1] L. Kronecker, Näherungsweise ganzzahlige Auflösung linearer Gleichungen, Monats. Königl. Preuss. Akad. Wiss. Berlin, 1179–1193 (1884), pp. 1271-1299\n\n[2] S. M. Gonek, H. L. Montgomery, Kronecker’s approximation theorem, Indagationes Mathematicae, Volume 27, Issue 2, 2016, Pages 506-523, (https://www.sciencedirect.com/science/article/pii/S0019357716000148)\n\n**Our question.** You write: *The results are interesting, though perhaps not that surprising nor novel*. If our results are not novel, can you please cite specific publications containing our theorems 4, 5, 6, 10 or their close analogs?\n\n\n\n \n\n "}, {"review_id": "wl63MCc3Z1", "reviewer": "Reviewer_Lm8e", "summary": "The paper advances the basic understanding of the expressive power of fixed-complexity function families on [0, 1]. It defines three classes of function families: $\\mathcal{G}_0$, whose members are infinite VC-dimension families, $\\mathcal{G}_1$, whose members can approximately fit any finite number of points, and $\\mathcal{G}_2$, whose members can achieve uniform approximation over the domain [0, 1]. Previous work has identified certain function families that belong to $\\mathcal{G}_2$. This paper focuses on the difference sets, namely $\\mathcal{G}_0 \\setminus \\mathcal{G}_1$ and $\\mathcal{G}_1 \\setminus \\mathcal{G}_2$.", "questions": "- Should Line 327 say $H_N^{(5)}$ instead of $H_N^{(2)}$?\n\n[other minor suggestions]\n\n- Line 353 “suggests” → “suggest”\n- Line 183 “over the field Q” → “over the field Q of rational numbers” (as the field appears less frequently than R or Z in machine learning papers).\n- Line 165 “is a subset” → “is a non-empty subset”", "limitations": "The paper acknowledges a limitation in its methodology, which is explained in the paragraph starting from Line 363. Specifically, the three methods used in the paper cannot effectively distinguish between $\\mathcal{G}_1 \\setminus \\mathcal{G}_2$ and $\\mathcal{G}_2$. As a result, the investigation in the paper is not completed and requires further research.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "[originality]\n\n- The paper explores the expressiveness of function classes that have fixed complexity and infinite VC dimension. To the best of my understanding, this research area remains largely unexplored beyond the prior results on universal formulas.\n\n[quality]\n\n- The mathematical framework is clearly defined, and the analysis is conducted rigorously.\n\n[clarity]\n\n- The paper is well-written.\n\n[significance]\n\n- The paper identifies certain specific function classes (such as $H^{(5)}$) that are seemingly complex and expressive but do not belong to $\\mathcal{G}_2$ and belong to $\\mathcal{G}_1$.", "weaknesses": "[originality]\n\n- None in particular\n\n[quality]\n\n- None in particular\n\n[clarity]\n\n- None in particular\n\n[significance]\n\n- This paper only focuses on one-dimensional functions, which inevitably restricts the immediate applicability of the presented results to the field of machine learning. However, I consider this limitation to be a reflection of the fact that this area of analysis is still in its early stages.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the careful reading and positive evaluation of our work! We agree with all your fixes, thanks!"}, {"review_id": "fsAnwa794R", "reviewer": "Reviewer_2cHj", "summary": "This paper studies function approximation in the spirit of the Kolmogorov-Arnold representation theorem.\nA definition of expressivity classes is made which distinguishes pointwise and uniform approximation.\nFunction families with the form of neural networks are proposed and approximation results proven.", "questions": "How could this line of work bear on or influence approximation theory which (like ref. [4]) is relevant for practical computation?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Definitions are systematic and arguments are clear.", "weaknesses": "As discussed at the bottom of p. 2, these constructions and arguments rely on infinite precision arithmetic\nand are badly behaved when restricted to finite precision.  This is as expected for finite dimensional families\nwhich live in the classes G_n of section 2.  The results are of mathematical interest but I do not see the interest \nfor the machine learning community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*How could this line of work bear on or influence approximation theory which (like ref. [4]) is relevant for practical computation?*\n\nThank you for this reasonable question.\n\n1. You mention Kolmogorov-Arnold, but the big difference between KA and our results is that the KA-type models include very complicated, non-elementary functions that do not naturally occur in real computations. In contrast, we consider only models that are explicitly defined by a finite number of elementary functions and arithmetic operations. Such models easily can/do occur in practice. \n\n2. The effects we discuss are formulated irrespective of the limit of infinite magnitude/precision, and may potentially occur in realistic models. For example, we identify some functional families as belonging to the class $\\mathcal {G}_0\\setminus\\mathcal {G}_1$ of constrained models that can shatter arbitrarily large finite sets, or to the class $\\mathcal G_1\\setminus\\mathcal G_2$ of models that can approximate functions on any finite set but not on the whole domain. It is concievable that such deficiencies may occur in practice. You may call this conjecture a stretch, but practical interpretation of classical approximation theorems like Cybenko's [4] also involves various stretches. For example, Cybenko's theorem does not say anything about how many neurons, $10$ or $10^{10^{10}}$, are needed for a reasonable accuracy in a realistic problem. Rather, the value of this theorem is in showing that there are no fundamental constraints preventing single-hidden-layer networks from fitting generic functions; after that one just hopes that a moderate number of neurons is enough. Likewise, we see the main value of our results in showing that there are, or aren't, fundamental constraints present in a few natural functional families.  \n\n3. Moreover, our work can be viewed as clarifying conditions and conclusions of classical theorems like Cybenko's. This classical theorem guarantees approximability in the limit of infinitely many neurons, but does not rule out the possibility that the same approximability can be achieved with finitely many neurons. Imagine that such a strengthening of Cybenko's theorem would be true; wouldn't this have a profound effect on its interpretation in the context of ML? It turns out that this strengthening is not true in general for classical single-hidden-layer networks, but it does hold for relatively simple modified models. Our work sheds light on conditions necessary for such models. \n\n4. Our class $\\mathcal G_1\\setminus\\mathcal G_2$ is particularly appealing for practical interpretation. Its elements represent models that can fit any function on any finite set but cannot fit general continuous target functions on the full domain $[0,1]$. This implies that such models are trainable but poorly generalize: for a generic continuous target the deviation of the model from the target outside the training set does not decrease even if the size of the training set grows. In section 7 we give examples of sin-networks in this class, and our central conjecture is that general sin-networks with more than one hidden layer lie in this class. Now, our work was in fact partly motivated by an experimental observation that sin-networks tend to poorly generalize. Admittedly, we have not done any comprehensive experimental studies of this effect, but we typically observe that sin-network tend to overfit more than, say, ReLU networks whenever they train well on a training set (see examples in our [general author rebuttal](https://openreview.net/forum?id=gmVoaAxB1R&noteId=1hE4zF1UCW)), We think that our theoretical results contribute to a better understanding of this effect. "}]

Author rebuttal:
We thank all the reviewers for the careful reading of our work and useful feedback, both positive and critical. 

As we mention in the response to Reviewer 2cHj, our work is partly motivated by an experimental observation that neural networks with the activation function $\sin$ apparently can easily overfit. We attach a .pdf figure illustrating this with a simple example of a two-hidden-layer network fitted by gradient descent to a one-dimensional target function. The network fits the training set reasonably well, but wildly oscillates outside. This is the sort of behavior we expect from models in our class $\mathcal G_1\setminus\mathcal G_2$ (trainable, but poorly generalizing). A ReLU-networks of the same architecture is trained to a comparable accuracy on the training set, but shows a much better generalization. In a weaker form, we also observe this effect in MNIST classification: $\sin$-networks again seem to be somewhat more prone to overfitting than ReLU-networks of the same architecture. Our theoretical setting of universal formulas can be viewed as an extreme case of these experiemental setups, when the network size is small and fixed, the weights are trained by some ideal optimization algorithm, etc. The above experimental observations seem to agree with our theoretical results and conjectures regarding the multi-layer $\sin$-networks being in the class $\mathcal G_1\setminus\mathcal G_2$, in contrast to ReLU-networks. 

Meta-review: The paper explores the expressive power of "universal formulas" which are fixed-complexity function families on $[0, 1]$. This is in contrast to "universal approximation" results for neural networks that state that neural networks can approximate any continuous function on $[0,1]$ by increasing the width sufficiently (changing the complexity). The authors present a hierarchy of three nested expressiveness classes and show interesting separations where a function class may be able to fit any finite size set but no generalize to the rest of the domain. They connect their observations to explain overfitting by $\sin$ activations. The contributions are summarized exceptionally well by [reviewer BXX4](https://openreview.net/forum?id=gmVoaAxB1R&noteId=5DqlHjhgWB).

The main drawback of the work is perhaps that it is mostly a mathematical exploration given the use of infinite precision, and one dimensional functions. Nevertheless, as all the reviewers agree, the results are interesting and novel, and useful for the community to know. Therefore, I recommend acceptance. I encourage the authors to incorporate the feedback from the reviewers (as they see fit), and add discussions about connections to approximation theory.
Decision: Accept (poster)