A closer look at the approximation capabilities of neural networks
Authors: Kai Fong Ernest Chong
Venue:  (2020)
Keywords: deep learning
approximation
universal approximation theorem

Abstract: The universal approximation theorem, in one of its most general versions, says that if we consider only continuous activation functions σ, then a standard feedforward neural network with one hidden layer is able to approximate any continuous multivariate function f to any given approximation threshold ε, if and only if σ is non-polynomial. In this paper, we give a direct algebraic proof of the theorem. Furthermore we shall explicitly quantify the number of hidden units required for approximation. Specifically, if X in R^n is compact, then a neural network with n input units, m output units, and a single hidden layer with {n+d choose d} hidden units (independent of m and ε), can uniformly approximate any polynomial function f:X -> R^m whose total degree is at most d for each of its m coordinate functions. In the general case that f is any continuous function, we show there exists some N in O(ε^{-n}) (independent of m), such that N hidden units would suffice to approximate f. We also show that this uniform approximation property (UAP) still holds even under seemingly strong conditions imposed on the weights. We highlight several consequences: (i) For any δ > 0, the UAP still holds if we restrict all non-bias weights w in the last layer to satisfy |w| < δ. (ii) There exists some λ>0 (depending only on f and σ), such that the UAP still holds if we restrict all non-bias weights w in the first layer to satisfy |w|>λ. (iii) If the non-bias weights in the first layer are *fixed* and randomly chosen from a suitable range, then the UAP holds with probability 1.

Published as a conference paper at ICLR 2020
A CLOSER LOOK AT THE APPROXIMATION CAPABILI- TIES OF NEURAL NETWORKS
Kai Fong Ernest Chong
Information Systems Technology and Design (ISTD) pillar, Singapore University of Technology and Design, Singapore ernest_chome sew.geeeduddddu....... sg
ABSTRACT
The universal approximation theorem, in one of its most general versions, says that if we consider only continuous activation functions o, then standard feedfor- ward neural network with one hidden layer is able to approximate any continuous multivariate function f to any given approximation threshold c, if and only if a is non-polynomial. In this paper, we give a direct algebraic proof of the theorem. Furthermore we shall explicitly quantify the number of hidden units required for approximation. Specifically, if X C IR" is compact, then a neural network with n input units, m output units, and single hidden layer with ("td) hidden units (independent of m and E). can uniformly approximate any polynomial function f X Ih' whose total degree is at most d for each of its m coordinate fune- tions. In the general case that f is any continuous function, we show there exists some N E ((e (independent of m), such that N hidden units would suffice to approximate f. We also show that this uniform approximation property (UAP) still holds even under seemingly strong conditions imposed on the weights. We highlight several consequences: (i) For any 5 >> 0, the UAP still holds if we re- strict all non-bias weights in the last layer to satisfy |w| < 6. (ii) There exists some X > 0 (depending only on f and a), such that the UAP still holds if we restrict all non-bias weights w in the first layer to satisfy |w] > X. (iii) If the non-bias weights in the first layer are fixed and randomly chosen from suitable range, then the UAP holds with probability
INTRODUCTION AND OVERVIEW
A standard (feedforward) neural network with n input units, m output units, and with one more hidden layers, refers to a computational model N that can compute a certain class of functions p R + RmM. where p PW is parametrized by W (called the weights of N/. Implicitly, the definition of depends on a choice of some fixed function a R + IR, called the activation function of N. Typically, is assumed to be continuous, and historically, the earliest commonly used activation functions were sigmoidal.
A key fundamental result justifying the use of sigmoidal activation functions was due Cybenko (1989), Hornik et al. (1989), and Funahashi (1989), who independently proved the first version of what is now famously called the universal approximation theorem. This first version says that if is sigmoidal, then standard neural network with one hidden layer would be able to uniformly approximate any continuous function f X + R. whose domain X S R is compact. Homik (1991) extended the theorem to the case when is any continuous bounded non-constant activation function. Subsequently, Leshno et al. (1993) proved that for the class of continuous activation functions, standard neural network with one hidden layer is able to uniformly approximate any continuous function f X + R. on any compact C R", if and only if is nol-pollnomial.
Although single hidden layer is sufficient for the uniform approximation property (UAP) to hold, the number of hidden units required could be arbitrarily large. Given a subclass F of vell-valued continuous functions
compact set X C R", fixed activation function σ, and some E > O, let N = N(F, a, E) be the minimum number of hidden units required for single-hiddee-llyerr neural network be able uniformly approximate every f F within approximation error

---

Published as a conference paper at ICLR 2020
threshold of E. If o is the rectified linear unit (ReLU) r max(0, then N is at least D )e) when F is the class of C² non-linear functions (Yarotsky, 2017), or the class of strongly convex differentiable functions (Liang & Srikant, 2016); see also (Arora et al., 2018). ) If a is any smooth non-polynomial function, then N is at most ((e~a) for the class of C' functions with bounded Sobolev norm (Mhaskar, 1996); cf. (Pinkus, 1999. Thm. 6.8), (Maiorov & Pinkus, 1999). As a key highlight of this paper. we show that if an arbitrary continuous non-polynomial function, then N is at most ((="") for the entire class of continuous functions. In fact, we give an explicit upper bound for N in terms of E and the modulus of continuity of f. so better bounds could be obtained for certain subclasses F, which we discuss further in Section 4. Furthermore, even for the wider class F of all continuous functions f: X - Rm the bound is still (ee independent of m.
To prove this bound, we shall give direct algebraic proof of the universal approximation theorem, in its general version as stated by Leshno al. (1993) (i.e. is continuous and non pon-ooonnomia), An important advantage of our algebraic approach is that we are able to glean additional information on sufficient conditions that would imply the UAP. Another key highlight we have that F is the subclass of polynomial functions f X R" with total degree most d for each coordinate function, then ("++²) hidden units would suffice. In particular, notice that our bound N s ("t") does not depend on the approximation error threshold E or the output dimension m.
We shall also show that the UAP holds even under strong conditions the weights. Given any 5 > O, we can always choose the non-bias weights in the last layer to have small magnitudes no larger than 8. Furthermore,
show that there exists some À >> (depending only on and the function f to be approximated), such that the non-bias weights in the first layer can always be chosen to have magnitudes greater than X. Even with these seemingly strong restrictions on the weights, we show that the UAP still holds. Thus, our main results can be collectively interpreted as a quantitative refinement of the universal approximation theorem, with extensions restricted weight values.
Section 2 covers the preliminaries, including relevant details on arguments involving dense sets. Section 3 gives precise statements of our results, while Section 4 discusses the consequences of our results. Section 5 introduces our algebraic approach and includes most details of the proofs of our results; details omitted from Section 5 can be found the appendix. Finally, Section 6 concludes our paper with further remarks.
Outline:
2
PRELIMINARIES
2.1 NOTATION AND DEFINITIONS
Let N be the set of non-negative integers, let 0, be the zero vector in RR and let Mat E) be the vector space of all k-by-& matrices with real entries. For any function f 12" + RT let fill denote the 1-th coordinate function of f (for each < t < m). Given = -ai,...,,,) an) E N and any n-tuple x = (21....,,T, we write xº to mean 21 ....%% If x E R". then x² is real number, while if x is sequence of variables, then x" is monomial, i.c. an navatae polynomial with a single term. Let Wm. := {W E Mat(n + 1, N) x Mat(N + 1, m)} for each N 1, and define Wm = UN21 WM. If the context is clear, we supress the superscripts n, m. in W and Wn...
Given any X ECR. R", let C(X) be the vector space of all continuous functions f X + R. We use the convention that every f E C(X) is function f' f( :.,) in terms of the variables x1, .i.....22 Tn unless n 1, in which case is in terms of a single variable (or y). We say f is non-zero if f is not identically the zero function on X. Let P(X) be the subspace of all polynomial functions in C(X). For each d N, let Psa(X) (resp. Pa(X)) be the subspace consisting of all polynomial functions of total degree < d (resp. exactly d). More generally, let C(X, Rm)) be the vector space of all continuous functions f X + 1²T and define P(X, )",, Psa(X, RT)., Pu 12 analogously.
()
Throughout, we assume that a E C(R). For every W = (1) W(2) E W, let w be the j-th column vector of (R),, and let w/)) be the (i, entry of (()) (for k 1,2). The index begins at i = 0, while the indices & begin at j 1, k = 1 respectively. For convenience, let
w (k)
denote the truncation of (k) obtained by removing the first entry wo Define the function
(k)
Ply: R
IR" m so that for each 1 ك m, the j-th coordinate function PW
" [i] is given by the map
- w + Σ Nl (1) (1,x)),
2

---

Published as a conference paper at ICLR 2020
where "." denotes dot product, and (1, x)) denotes column vector in R=+1 formed by concatenating before z. The class of functions that neural networks W with one hidden layer can compute is precisely fpr W E W). where is called the activation function N (or of ply ). Functions Ply satisfying W E Wy correspond to neural networks with N hidden units (in its single hidden layer). Every i is called weight in the k-th layer, where wij is called bias weight (resp. non-bias weight) if = 0 (resp. * 0).
(k)
Notice that we do not apply the activation function a to the output layer. This consistent with previous approximation results for neural networks. The reason is simple: a Pw
[ (restricted to domain X S I) cannot possibly approximate f X R if there exists some To E X such that or (X) is bounded away from f((rr). If instead f(X) is contained in the closure of (XX), then applying PW
a [i] has essentially the same effect as allowing for bias weights w/?)
Although some authors, c.g. (Leshno et al., 1993), do not explicitly include bias weights in the output layer, the reader should check that if is not identically zero, say (vo) # O, then having a (2) = 0 (i.e. no bias weight in the output layer) and introducing an (N + 1)-th hidden unit, with corresponding weights w = Yo. w = 0 for all < S n, and w +111 o( this means our results also apply to neural networks without bias weights in the output layer (but with one additional hidden unit).
bias weight Wo, (2) = is equivalent to setting o
2.2 ARGUMENTS INVOLVING DENSE SUBSETS
key theme this paper is the use of dense subsets of metric spaces. We shall consider several notions of "dense". First, recall that a metric on set S is any function d S x S - E such that for all x, y, = E S, the following conditions hold:
(i) d(z y) 2 with equality holding if and only if y (z, y) = D(y. z);
(iii) 0 (xx, 2) S ((r, v) + d(y, 2).
The set S, together with metric on S, called a metric space. For example, the usual Euclidean norm for vectors in R" gives the Euclidean metric (u, v) + ||u ell2, hence R" is metric space. In particular, every pair in Wx can be identified with a vector in [(m+a+1)N so WN, together with the Euclidean metric, is a metric space.
Given metric space X (with metric d), and some subset U S X, we say that U is dense in X (w.rt. 0) if for all & > and all x E X, there exists some u E U such that d(z, u) < c. Arbitrary unions of dense subsets are dense. If U C U' Ç X and U is dense in X, then U' must also be dense in X.
A basic result in algebraic geometry says that if p E P(IR") is non-zero, then {a E I2 p(x) + 0} is a dense subset of R (w.rt. the Euclidean metric). This subset is in fact open set in the Zariski topology, hence any finite intersection of such Zariski-
open sets is dense; see (Eisenbud, 1995). More generally, the following is true: Let P1.... .......PP. P& E P(R"), and suppose that X == {x e R. : (x)) = 0 for all < í S k). If p E P(()) is non-zero, then {ar E X p(x)) F 0) is dense subset of X (w.r.t. the Euclidean metric). In subsequent sections, we shall frequently
these facts.
Let X C R" be a compact set. (Recall that X is compact if it is bounded and contains all of its limit points.) For any real-valued function ʃ whose domain contains X, the uniform norm of I on X is || = (u)( : x E X3. More generally, if f : X - Rm, then we define llffloo.x == max[Il | 1 S j S m}. The uniform norm of functions on X gives the uniform metric (f.g) + |f glloo,x, hence C(X) is a metric space.
2.3 BACKGROUND ON APPROXIMATION THEORY
Theorem 2.1 Weirstrssss theorem). Let X C RDd be compact. For any I E C(X), there such
exists a sequence [pk kEN of polynomial functions in P(X) such that limg--oo [| Ps loc, = 0.
Let X C IR be compact. For all d E N and f E C(X), define
Ea(S) inf (1] pllox,x x PP PPs((X))
3

---

Published as a conference paper at ICLR 2020
A central result in approximation theory, due to Chebyshev, says that for fixed d, f. the infimum in (1) is attained by some unique p" E (R);; see (Rivlin, 1981, Chap. 1). (Notice here that we define p" to have domain R.) This unique polynomial p" is called the best polynomial approximant to f of degree d.
Given metric space X with metric d, and any uniformly continuous function X - R, the modulus of continuity of f is a function w : [0, oo] - [0, oo] defined by
w (6( == sup(lf(z) f(y) x, E X, (z y) 63.
By the Heine-Cantor theorem, any continuous f with a compact domain is uniformly continuous.
Theorem 2.2 (Jackson's theorem; see (Rivlin, 1981, Cor. 1.4.1)). Let d 2 be an integer. and let Y S R be closed interval of length r 2 0. Suppose f C(Y). and let p" be the best polynomial approximant to f of degree d. Then Il. polloo,y Ea(f) S (
MAIN RESULTS
Throughout this section, let X R be a compact set.
Theorem 3.1. Let d 2 2 be an integer, and let J (X, R)") (i.e. each coordinate function fl] has total degree S d). If E C(R))Pa-1(()) then every there exists some W ((m)))) such that f -P
Furthermore, the following holds:
(i) Given any > O, we can choose this W to satisfy the condition that [wo < À for all
non-bias weights wi.j (i.e. i + 0) in the second layer.
(ii) There exists some X' > O, depending only on f and a, such that we could choose the weights of W in the first layer to satisfy the condition that 1o/21/2 X for forall j.
Theorem 3.2. Let f E C(X, )., and suppose a E C(R),P(R)) Then for every > 0, there exists an integer N Ose-)) (independent of m), and some W WN. such that f Pw ll,e, < e. In particular, if we let D == sup ||æ y 22
E X} be the diameter of X, then we can set D
N = =(tadr where de == min(d E Z d 2 2, ytol 2d < for all S m}. (Note that de is well-defined, since lims y (8) 0 for each t.) Furthermore, we could choose this W to satisfy either (i) or (ii), where (i), (ii) are conditions on W as described Theorem 3.1.
Theorem 3.3. Let f E C(X,RR" R.)), and suppose that o E (((R))((R)) Then there exists > (which depends only on f and a) such that for every & >> 0, there exists integer N (independent of such that the following holds:
Let W Wy such that each w (1) RD (for 1 S N) is chosen uniformly at random from the {u E RD ||ullp A}. Then, with probability there exist choices for the bias weights Woo (for 1 < j S N) in the first layer, and (both bias and non-bias) weights
(2) wij in the second layer, such that [f - 1ool <.
Moreover, N E O(r="))orr general f E (R"), and we can let N = ((tte) E
4 DISCUSSION
The universal approximation theorem (version of Leshno et al. (1993)) is an immediate consequence of Theorem 3.2 and the observation that a must be non polynooal for the UAP hold, which follows from the fact that the uniform closure of PX)((X) is P=a(X) itself, for every integer d 2 1. Alternatively, we could infer the universal approximation theorem by applying the Stone- Weirstrasss theorem (Theorem 2.1) to Theorem 3.1.
Given fixed n, m, d, a compact set X C R", and a E C(R)) Theorem 3.1 says that we could use fixed number N of hidden units (independent of E) and still be able to approximate any function of f Px,(X,EU RT) to any desired approximation error threshold e. Our e-free bound, although possibly surprising to some readers, is not the first instance of e-free bound: Neural net- works with two hidden layers of sizes 2n + and 4n + 3 respectively are able to uniformly approx- (somewhat pathological) activation function (Maiorov
imate any f E C(X), provided that
4

---

Published as a conference paper at ICLR 2020
& Pinkus, 1999); cf. (Pinkus, 1999). Lin et al. (2017) showed that for fixed n. d, and fixed smooth non-linear 0, there is a fixed N (i.e. E-free), such that a neural network with N hidden units is able to approximate any f E (xa(XX. An explicit expression for N is not given, but were able to 4 hidden units are required, over d
infer from their constructive proof that N = =("" d hidden layers (for d 2 2). In comparison, we require less hidden units and single hidden layer.
Our proof of Theorem 3.2 is an application of Jackson's 's theorem (Theorem 2.2) to Theorem 3.1, which gives explicit bound in terms of the values of the modulus of continuity wy of the function to be approximated. The moduli of continuity of several classes of continuous functions have explicit characterizations. For example, given constants k 0 and < a S 1, recall that continuous function f f: X + R (for compact X C R is called k- k-Lipschitz if [f f()) - k||z vll for all x, y E X, and it is called a o-HHleer if there is some constant such that [x() f(v) S c||æ-yحl for all y E X. The modulus of continuity of a k-Lipschitz (resp. a-Hölder) continuous function I is (1) = kl (resp. (1) = cla), hence Theorem 3.2 implies the following corollary.
Corollary 4.1. Suppse E C(R))P(R).
(i) If f [0 + IR is k-Lipschitz continuous, then for every & > 0, there exists some W WN that satisfies || fl 1loo, < where N = =1+t1² (ii) If f [0, 11" + I is a-Hölder continuous, then there is constant k such that for every
> O, there exists some W E WW that satisfies II --w bo,,x < E, where N =(=dd)
and (aa.
An interesting consequence of Theorem 3.3 is the following: The freezing of lower layers of a neural network, even the extreme case that all frozen layers are randomly initialized and the last layer is the only "non-frozen" layer, does not necessarily reduce the representability of the resulting model. Specifically, in the singlehhidden-apg first layer are fixed and randomly chosen from some suitable fixed range, then the UAP holds with probability 1. provided that there are sufficiently many hidden units. Of course, this representability does not reveal anything about the learnability of such model. In practice, layers are already pre-trained before being frozen. It would be interesting to understand quantitatively the difference between having pre-trained frozen layers and having randomly initialized frozen layers.
case, we have shown that if the non-bias weights in the
Theorem 3.3 can be viewed as a result on random features, which were formally studied in relation to kernel methods (Rahimi & Recht, 2007). In the case of ReLU activation functions, Sun et al. (2019) proved an analog of Theorem 3.3 for the approximation of functions in a reproducing kernel Hilbert space; cf. (Rahimi & Recht, 2008). For a good discussion on the role of random features in the representability of neural networks, see (Ychudai & Shamir, 2019).
The UAP also studied in other contexts, most notably in relation the depth and width of neural networks. Lu et al. (2017) proved the UAP for neural networks with hidden layers of bounded width, under the assumption that ReLU is used as the activation function. Soon after, Hanin (2017) strengthened the biith UAP result by considering the approximation of continuous convex functions. Recently, the role of depth in the expressive power of neural networks has gathered much interest (Delalleau & Bengio, 2011; Eldan & Shamir, 2016; Mhaskar et al., 2017: Montúfar et al., 2014; Telgarsky, 2016). We do not address depth in this paper, but we believe it is possible that our results can be applied iteratively to deeper neural networks, perhaps in particular for the approximation of compositional functions; ef. (Mhaskar et al., 2017).
AN ALGEBRAC APPROACH FOR PROVING UAP
We begin with a "warm-up" result. Subsequent results, even if they seem complicated, are actually multivariate extensions of this "warm-up" result, using very similar ideas.
Theorem 5.1. Let p(x) be a real polynomial of degree d with all-non-zero coefficients, and let a1.- a1..... ad+1 be real numbers. For each 1 < j S d + 1, define fq RR - R R + p(azz). Then fi...., fat1 are linearly independent if and only if aff......a. adt1 are distinct.
k < d and each S S d 1, let f(0) (resp. (l) be the i-th derivative of f/ (resp. p), and let a be the coefficient of x in p(() (z). Recall that the Wronskian of (fr..... fa+1) is defined to be the determinant of the matrix M M(x) = [ ( (1) (x)) Since f1.-.., so+
Proof. For each 0 < <i,k
5

---

Published as a conference paper at ICLR 2020
polynomial functions, it follows that (f1..... ff+1) is sequence of linearly independent functions and only if its Wronskian is not the zero function (LeVeque, 1956, Thm. 4.7(a)). Clearly, a, 0j for i & j. then det (x) is identically zero. Thus, it suffices show that if 01,.... 1d+1 are distinct, then the evaluation det M(1) of this Wronskian at x = gives a non-zero value.
Now, the (i. -tth entry of (1) equals aj (a))))))))a), so M(1) M'M", where M' is upper triangular matrix whose (i. j-th entry equals a a and M" [o] [o)-"] 'Isiijaa is the transpose of a Vandermonde matrix, whose determinant is
det(M")
II (a. a.).
ssicjsd-1
Note that the k-th diagonal entry of M' is af--1))))))))))))) = (k: 12 which is non-zero by assumption, so det( * O. Thus, if a...... ad+1 distinct, then det (1) (M') det(M") # 0. O
Definition 5.2. Given 2 1, W E WN Zo E R", and any function R - R, let Fg.zo (W) denote the sequence of functions [i]]....,[N,, such that each ʃg I R defined by the map x + g (w)))
(1) (x - -xo)). Also, define the set
9 "Wiad N,N = ( "N"" F. (W) is linearly independent)..
Note that the value of m is irrelevant for defining 'Wird N.N:
Remark 5.3. Given a = (ai.... an) E R", consider the ring automorphism y P(R") ((R") induced by H; + Z2- a, for all < i S. For any fi...., fo E P(RR*) and scalars 0i,,.... Og. R. note that a1 + ... + f& = 0 if and only if a1 + ... + ((k) = 0, thus linear independence is preserved under yp. Consequently, if the function g in Definition 5.2 is polynomial, then " WWind N,No
9 Wind n,N for all 2o R".
Corollary 5.4. Let m be arbitrary. I E Pa(R)) has all-non-zero coefficients, then Wiid+ is a dense subset of Wa (in the Euclidean metric).
Proof. For all 1 j < let Ags' == =(W E Whet wff. - wft * 0). and note that A 1,d+1:0 Nisisren Aj. is also dense in Wi.m. 1
is dense in WI.M So by Theorem 5.1, "Wind
As we have seen in the proof of Theorem 5.1, Vandermonde matrices play an important role. To extend this theorem (and Corollary 5,4) to the multivariate case, we need generalization of the Vandermonde matrix described in (D' Andrea & Tabera, 2009). (Other generalizations of the Vandermonde matrix exist in the literature.) First, define the sets
a {(a1 an) E N" a1 +... + an S sd];
M ((I+2)) E P(R"): : Aga)-
is easy to show that |A//l = (*+d). and that the set M of monomial functions forms a basis for (R)). Sort the n-tuples in A.. in colexicographic order, i.e. (a1, an) < (af..... a4)) and only if a; < af for the largest index such that (;; * a4. Le < .... < X(m2d) denote all the ("*d) n-tuples in Aža after sorting. Analogously, let qı, (1,...Q((**) be all the monomial functions in M in this order, i.e. each qu : R - R is given by the map xd Given any sequence (Ui,..., of vectors in IR", the generalized Vandermonde matrix associated it is
Q = Q(vi...................... ((l.....,.(())))))) = [q: ("
(2)
Definition 5.5. Given any W E Whatyy we define the non non-bias Vandermonde matrix of W to be the
generalized Vandermonde matrix Q[W]= = (w(( ( )1s1s5(()))) associated (w(1) ..... w (1)
Theorem 5.6. Let m be arbitrary, let p E PR( and suppose that p has all-non-zero coefficients. Also, suppose that Pi..... .P. E P( are fixed polynomial functions on the non-bias weights
of the first layer. Define the following sets:
U == {W E Witmm
(W) for all 1 siisk
Pyiiud = [W e Fp.o. is linearly independent).
If there exists W E ll such that the non-bias Vandermonde matrix of W is non-singular, then yinn dense in U (w.rl. the Euclidean metric).

---

Published as a conference paper at ICLR 2020
Proof. We essentially extend the ideas in the proofs of Theorem 5.1 and Corollary 5.4, using the notion of generalized Wronskians; see Appendix A.1 1.1 for proof details.
Corollary 5.7. Let m be arbitrary. P E P(R) is a fixed polynomial function of degree d with all-non-zero coefficients, then P "Wi(" == a dense subset of W
Proof. By Theorem 5.6, it suffices to show that there is some W E Winty such that the non-bias Vandermonde matrix of W is non-singular; see Appendix A.2 for proof details.
Remark 5.8. The proof of Corollary 5.7 still holds even if we restrict every non-bias weight Wigj in the first layer to satisfy [w2.] < x for some fixed constant À 0.
(1)
For the rest of this section, let {> kEN be a divergent increasing sequence of positive real numbers, and let {Yx}EeN JEN be a sequence of closed intervals of IR, such that YE C Ys whenever k' I k, and such that each interval Y& [v/. v/4 has length Ax- Let d 2 1 be an integer, and suppose a E C(RR). ).). For each k E N. let FF be the best polynomial approximant to oly, of degree d. Given >> 0 and any integer N 1, define the closed ball B == {x R ||=1||2 S r}
oc, and X E (2(k)) for some y > O, then for every 8 > O, there is a subsequence (Ki heN of N, and sequence {yA, JoEN of real numbers, such that s/s < yk. < Ver (yNa) = The (Uka). and
Lemma 5.9. If d 2 2, limg Ea(olv))
min(lyk, - -hh l.1kk 1B/. VK.
1
d+1
for all t E N. (See Appendix B for proof details.)
The proofs of the next three lemmas can be found in Appendix Lemma 5.10. For any constant > 0,
- -oloo,o 0.
lim 1-0000
(Az))++
Lemma 5.11. Let 2 N integers, lel ro, vo.....'' UN 2 1 be fixed real numbers, and let S()) be a sei (Po()),.... "pp.... of N 11 aaffinely independent points in lR parametrized by X > 0. where each point (A) has (Cartesian) coordinates PP.......... X X''p.k) ) for some fixed non-zero scalars Pi.1..... P..K. Let ((A) be the convex hull of S()), i.e. A(X) is an N -ismplex, for each
S N, let (A) be the height of ((A) w.rs. apex Pa (A). Let (((A) := (axx(h;(A) : 0 S i S N}
and miin == min frinfri...,,.1. )N Tf > Tmin for some S j S N, then there exists some 7 >
such that h(A) E (2(mmin+7) 7
Lemma 5.12. Let N 1 be integers, let > and let 0 < 0 < Suppose ip : R + R is a continuous open map such that ((00) = ON. and ((xx) 2 Xp(x) for all x E RM, A > 0. Let {Uk) bek be a sequence where each Us is a dense subspace of B BBA. Then for every there exists some (sufficiently large) k E N. and some points ug. uN in Uk. such that for each point p B,N. there are scalars bo. ................................ by 2 0 satisfying p Ei bup(u:) bo +... bb 1, and bb. N < 8 for all 0 < N.
0,
Eizo
Outline of strategy for proving Theorem 3.1. The first crucial insight is that (R"( as a real vector space, has dimension ("=d). Our strategy is to consider N (x+td) hidden units. Every hidden unit represents continuous function g; X + R determined by weights W and the activation function a. If ......, IN can be well-approximated (on X) by linearly independent poly- nomial functions in (RR"), then we can choose suitable linear combinations of these N functions to approximate all coordinate functions f(l (independent of how large m is). To approximate each gj. we consider a suitable sequence )ee of degree d polynomial approximations to so that Bj is approximated by sequence of degree d polynomial functions (6))
(0 1 We shall also vary W concurrently with k so that [w(3))//2 increases together with k. By Corollary 5.7, the weights
can always be chosen so that D Di.::-..::5 .NN. are linearly independent.
-W
The second crucial insight is that every function in (R)) can be identified geometrically point in Fuclidean (*+ -space. We shall choose the bias weights so that GW Pi.ki---: . correspond

---

Published as a conference paper at ICLR 2020
to points a hyperplane, and we shall consider the barycentric coordinates of the projections of both f(l] and the constant function onto this hyperplane, with respect to -i.k: SW N As the values of k and || || increase, both projection points have barycentric coordinates that approach . }) ) and their difference approaches O; cf. Lemma 5.12. This last observation, in particular,
when combined with Lemma 5.9 and Lemma 5.10, is a key reason why the minimum number N of hidden units required for the UAP to hold is independent of the approximation error threshold &.
Proof of Theorem 3.1. Fix some E >> 0, and for brevity, let N = (a+1). Theorem 3.1 is trivially true when f is constant, so assume f is non-constant. Fix a point 20 E X, and define fo E C(X, (X,XXT" R") by 10d := f fl (2o) for all 1 S S m. Next, let Tx(xx) == sup || 20l12 E X). and note that rx (x(xx(()))) (2o) < oc, since X is compact. By replacing X with a closed tubular neighborhood of X if necessary, we may assume without loss of generality that rx(x)) > 0.
Define {Aa (Ya and {ox keN as before, with an additional condition that X E (((k)) for some J O. Assume without loss of generality that there exists a sequence {UK of real numbers, such that 5/4 < yk < V (yn) = on (yx), and
min 1/1. 1. lyVe
w/ll min lyk 1/cl, Dk
VKD
A
11/e
+ 2
for all l E N. The validity of this assumption in the case lim Ea(a vv) = o is given by Lemma 5.9. If instead lim Ed(a)(s) so, then as + co. the sequence ( converges to some ā E (R)( Hence, the assumption is also valid in this case, since for any y E R such
2/ = y for all & E N, which then that o (ū) = (Ø),, we can always choose (Yr [KN to satisfy 2
allows us to choose {yk JEEN that satisfies lim4--00
minflye li -vill Av
"+2'
By Lemma 5.10, we may further assume that |1o - -l < 2 for all & E N. where C' > 0 C
and y > 0 are constants whose precise definitions we give later. Also, for any W E W we can choose o' E C(R) that is arbitrarily close to in the uniform metric, such that l l is arbitrarily small. Since a E ((lB)(Psd11
(IR) by assumption, we may hence perturb a necessary, and assume without loss of generality that every 0% is a polynomial of degree d with all-non-zero coefficients, such that on (yk) + O.
|| I for all S s N}. and define For every 0 and & E N. let W == ( E W
X/ = sup f > 0: {u + (0) (x - (x) E E W C Yg for all 1 وك S N
Each X/ is well-defined, since rx (mo) < co. Note also that M (zo) = min( - v/l 18kk - 1/' by definition, hence it follows from (3) that Ap X, < (d + 2)rx (Zo). In particular, (X/ 1eEN is a
divergent increasing sequence of positive real numbers.
Given any p E (I") let v(p) E RN denote the vector of coefficients with respect to the basis {gr (z - zo). IN (x za)} (i.e. if v(p) = (V1, (V1...., ,N), then p(z) Eiseen Peg((z xx)), and let (p)) E R-N-1 be the truncation of v(p) by removing the first coordinate. Note that 9 (x) is the constant monomial, convenience, let ns (p) (resp. (p)) be the i-th entry of v(p) (resp. (p))).
this first coordinate 21 is the coefficient of the constant term. For
For each & E N, W E W , 1 و S N. define functions 9.W, D3.k in C(X) o(w (1,x)) and x + ak (()) (1, .)) respectively. By definition, (x(0) can be treated as a function of W. and note that 14 XW
( ) = 2 for any À > 0. (Here, deg qi denotes the total degree of q..) Since deg qi only if 1, it then follows that ( 2 (B: for all X > O.
For each,k k E N, define the "shifted" function of. Y2 + IR by y + only + ya). Next, let W : o Wiidd N:zo n nW,, (.o.ox)) ). and suppose W E W Note that in the definition of W we do not impose any restrictions on the bias weights. Thus, given any such W, we could choose the bias weights of W(I) to be w!! y/k w(")) To for all 1 1 j S N. This implies that each g represents the map & + Thk (1) (x (or)))) + vK), hence D3. (xn) = (v() o (yx). Consequently,
8

---

Published as a conference paper at ICLR 2020
by the definitions of Y3 and Wx. we infer that W
llop 1oo (dx))Lty C
(4)
By Corollary 5.7 and Remark 5.3, W is dense in (W2, Wh.s,, ). so such a W exists (with its bias weights given as above). By the definition of of independent and hence spans (X). Thus, for every S t I m, there exist 40
Wi n.N:zo" we infer that (gi,k..... IN k.) linearly
1,k .N E R,
which are uniquely determined once k is fixed, such that for - "1,491 + ................ -. a NNN, N, Evaluating both sides of this equation at x = zo. we then get
[t] g
1 + ................................ + NN = O.
[t]
(5)
For each E IR, define the hyperplane HA == {(u1,..., uN) E RN u1 = {}. Recall that qi (x) the constant monomial, so the first coordinate of each v(O),k) equals (By)), which implies that v(91,)).... N are N points on Ha(y)) = RN-1, Let ey == max [|((f()))
S t S m). (This is non-zero, since f is non-constant.) Note that ON and )( (for all t) are points in By- So for any 8 > O, Lemma 5.12 implies that there exists some sufficiently large k E N such that we can choose some W E WK, so that there are non-negative scalars ",,e (for S S N. 1 t m) contained in the interval ( 8, No4 5) that satisfy the following:
11th + +.... + b b/4 +.............................. UV =1 (for all 1 S 1 $ m):
ON-1 = 0N-1= -E / ((T))) D(Hl)) - Ejnn, u/u (( (for all 1 S m))
Note that v(((0 + (2x)) 61t "((,)) +....+ 66 ((OW and (ON-1, ((u)) (( + ... + U/ (N k, so we get
s!'l = 14]
+ + (b - b'x,))
Since 4/ [H] n are unique (for fixed k)), we infer that jjk 11/1/
[1]
8/ for each 1 1si5 N.
Thus, for this sufficiently large k it follows from 6/t R/ E { - 5, 1
+ 6) that
N
[e] j.
2 G - 5) - G + 5) 2 -25.
(6)
Let Sk : (D DONN.) ). let As be the convex hull of Sk, and for each j. let hy (Ax) be the height of A w.r.t. apex PO Let M(Ax)= = max max(h; (A,( : 1 S j S N). Since D. ( = deez 4i D. (o)l for all i, and since d 2 2 (i.e. dog > 1), it follows from Lemma 5.11 that there exists some 7 > O such that h(Aa) E ((((()))))))))) Using this particular 7 > 0. we infer M[A+) < C" for all sufficiently large k.
that there exists some constant 0 < C < do such that (x))
Note that 25 is an upper bound of the normalized difference for each barycentric coordinate of the two points D(rl1) and ON-1 (contained in B1)-1), which satisfies
of 28 - h(Aa)
es
AAk
1+y (X)
CJ (Au) I(d 2)xx
(Ae))
(%)
h(Aa)
<
(7)
Now, define C = 2Nc;((d + x)) C-' > O. Thus, for sufficiently large k. it follows from (5). (6) and (7) that
10 |af.1l+ +ol++... Na S a +... N. + +4NO 4N8 S (Ax)
[t]
[t]
C
(8)
For this sufficiently large k. define g E C(X, Rm)) by 9 = ai Using (4) and (8), it follows that
[c] W +... + al2 NNN for each
t.
l |oo.x l1a (o W - I1.k) + +... 2 W. s wW...
< |
11 - -WWWll blo, + + 1a 1loNN - 2W lloxx

---

Published as a conference paper at ICLR 2020
Finally, for all 1 V m, let W alik for each 1 S j N, and let w0,1 (zn)) This gives pi - 9th + fl (zo). Therefore, the identity f fo flll (zo) implies | Pi oo.
(2)
Notice that for all 8 > we showed in (6) that there sufficiently large ks such that off 28. A symmetric argument yields alik I 25. Thus, for all A >> O, we can choose W so that all non- weights in (72) are contained in the interval (-X, A); this proves assertion (i) of the theorem.
Note also that we do not actually require > be arbitrarily small. Suppose instead that we choose & E N sufficiently large, so that the convex hull of Ss. contains 0x-1 and f(((4) (for all (). In this case, observe that our choice of depends only on / (via ((r(1)) and (via the definition of b/
{Ax KEN). The inequality (7) still holds for any d satisfying b,k.0 ( 6, N + 6) for all j,t. Thus, argument to show I Pfllx,, < holds verbatim, which proves assertion (ii).
Proof of Theorem 3.2. Fix some > O, and consider an arbitrary t E {l...., For each integer d let pld be the best polynomial approximant ff of degree By Theorem 2.2, we have [[ p .lo I nn ( for all d 2 hence it follows from the definition of de that
| -1 loc,x 6w yt (2d <<
[4] Pde
1.1.s m). Note that e' > O, and 11110-ppl bo, S S5-E' (for Define e' = 8- max (owirol 2d.
all <t 5 m). By Theorem 3.1, there exists some W E Windee) satisfying I|p| PW (1
loc <E'
for all 1 < S m, which implies
Il Pw a 1 S [1
p!d lbc. + 11 PW l < (66-))++'=-
therefore |l - - |lo,x < s. Conditions (i) and (ii) follow from Theorem 3.1. Finally, note that w ( (12) (for fixed D), i.e. de O()), hence ("td)) m(n- (n... d (ee O
n!
Proof of Theorem 3.3. Most of the work has already been done earlier in the proofs of Theorem
3.1 and Theorem 3.2. The key observation is that det(Q[W1] is a non-zero polynomial in terms of the weights W, hence (dct(Q(WT) * W E W(nd)) is dense Wingo), or equivalently, its complement has Lebesgue measure zero.
CONCLUSION AND FURTHER REMARKS
Theorem 5.6 is rather general, and could potentially be used to prove analogs of the universal ap- proximation theorem for other classes of neural networks, such as convolutional neural networks and recurrent neural networks. In particular, finding single suitable set of weights (as represen- tative of the infinitely many possible sets of weights in the given class neural networks), with the property that its corresponding "non-bias Vandermonde matrix" (see Definition 5.5) is non-singular, would serve as a straightforward criterion for showing that the UAP holds for the given class of neural networks (with certain weight constraints). We formulated this criterion be as general as we could, with the hope that it would applicable to future classes of "neural-like" networks.
We believe our algebraic approach could be emulated eventually yield unified understanding of how depth, width, constraints on weights, and other architectural choices, would influence the approximation capabilities of arbitrary neural networks.
Finally, we end our paper with an open-ended question. The proofs of our results in Section 5 seem suggest that non-bias weights and bias weights play very different roles. We could impose very strong restrictions on the non-bias weights and still have the UAP. What about the bias weights?
ACKNOWLEDGMENTT
This research is supported by the National Research Foundation, Singapore, under its NRFF program
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. International Conference on Learning Representations, 2018. URL wwtp://rteeeee.eeoooommmddBBlB/
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems. 303)3303- December 1989. doi: 10.10007/BF02551274. URL htips:
Carlos D' Andrea and Luis Felipe Tabera. Tropicalization and irreducibiltyy of generalized Van- dermonde determinants. Proc. Amer: Math. Soc.. 137(11):364733666 2009. ISSN 0002-9939. doi: 10.
URL
00002-9939-00-0095119
Olivier Delalleau and Yoshua Bengio. Shallow vs. deep sum-product networks. In Shawe- Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger (eds.), Advances in Neu- ral Information Processing Systems 24, pp. 666-674. Curran Associates, Inc., 2011. URL
ve -e---ep--deeeee-ee www.://eeee----ppuuuuurrtttooso. produuct-ntttwors......
Ronald A. Verore, Ralph Howard, and Charles Micchelli. Optimal nonlinear approximation. doi: 10.10////011777759 URL
Manuscripta Math., 63(4):469 1989. ISSN 0025-2611.
https://doo-oor.liibaaatt wtg..ibbarryssudd..d....222244 111.///0110000011100000001100011
David Eisenbud. Commutative algebra, volume 150 of Graduate Texts in Mathematics.
Springer-Verne New York, 1995. ISBN 0-387-94268-8 0-387-94269-6. doi: 10.1007/ 978-1-4612-5350-11 URL http://bb..booorr//11100/99/ 4612-5350--11 With view toward algebraic geometry.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Vitaly Feld- man, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annual Conference Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 907-940, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL eldan16.html.
K. Funahashi. On the approximate realization of continuous mappings by neural networks. Neural URL
Nerw., 2(3):183-192 May 1989. ISSN 0893-6080. doi: http://ck.doo.oog/11.110100. (0000008089660000099900-----00
Boris Hanin. Universal function approximation by deep neural nets with bounded width and relu activations. 08 2017. Preprint arXiv: 1708.0269) [st]..ML.].
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approxi- mators. Neural Netw., 2(5):359-366, July 1989. ISSN 0893-6080. doi: 00.101600833-080099) 90020-8. URL http://dd..cci..oooooooooo/////0
Kurt Horikk Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251 257, 1991. ISSN 0893-6080. doi: https://doi.org/// 101.://.orrr1111111/0/01000
URL
M. Kadec. On the distribution of points of maximum deviation in the approximation of continuous functions by polynomials. Uspehi Mat. Nauk, 15(1 191)):199-202, 1960. ISSN 0042-1316
M. I. Kadec. On the distribution of points of maximum deviation in the approximation of continuous functions by polynomials. Amer. Math. Soc. Transl. (2), 26:231-234 1963, ISSN 0065-9290, doi: 10. 10.10990trans22/226/99 URL https://doi-org http:///dooooo...bbbr......u wtt.://...duu.g24431110.10000000
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with nonpolynomial activation function can approximate any function. Neural Nenworks, 6(6):861 867, 1993. ISSN 0893-6080. doi: https://doi 1ttp:///oo..r//1....110100 6//00893-60000555
William Judson Ve Topics in number theory. Vols. and 2. Addison- Weeolyy Publishing Co., Inc., Reading, Mass., 1956.
11

---

wtw.:rrriiiibbrruuuuduuu....e/ee Published as a conference paper at ICLR 2020
Shiyu Liang and R. Srikant. Why deep neural networks? CoRR, abs/1610.04161, 2016. URL http://www..rrrrrs///.1...0....
Henry W. Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work well?
Journal of Statistical Physics, 168(6):123-1247, Sep 2017.
Zhou Lu, Hongming Pu, Feicheng Wang. Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Process- ing Systems 30, pp. 6231 6231- Curran Associates, Inc., 2017. URL http://papprs hwtpaapper.niss.ccpppppooo width.pdff
V. E. Maiorov and R. Meir. On the near optimality of the stochastic approximation of smooth functions by neural networks. Adv. Comput. Math., 13(1):79-033, 2000. ISSN 1019- 7168. doi: 1018993908478.
URL
Vitaly Maiorov and Allan Pinkus. Lower bounds for approximation by mlp neural networks. Neuro- computing, 25(1):81 -1, 1999. ISSN 0925-2312. doi: https://doi.orr/// 20110000-22222212008 00111-8. URL
H. N. Mhaskar. Neural networks for optimal approximation of smooth and analytic functions. Neu- ral Computation, (61):164-777, Jan 1996. doi: 10. 162/necooc..oo 19002//cco.199..8.. 1996.8.1.164..
Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better than shallow ones?, 2017. URL https://aaai.org//seee
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS' 14, pp. 2924-2932, Cambridge, MA, USA, 2014. MIT Press. URL http://dd..oooooccccctaooommm/dd 15519,99..
Allan Pinkus. Approximation theory of the mip model in neural networks. ACTA NUMERICA, 8: 143-195, 1999.
A. Rahimi and B. Recht. Uniform approximation of functions with random bases. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pp. 555-561, Sep. 2008. doi: 10. 10.1199ALEETTO022088777777 47996607.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceedings of the 20th International Conference Neural Information Processing Systems, NIPS'07, pp- 1177-1184, USA, 2007. Curran Associates Inc. ISBN 978- 778-1-60050-352-00 URL http://ll.acm irg/eiaatioo.ffmm//-228888116
Theodore J. Rivlin. An introduction to the approximation of functions. Dover Publications, Inc., New York, 1981. ISBN 0-486-64069-8. Corrected reprint of the 1969 original, Dover Books on Advanced Mathematics.
Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Ad- vanced Mathematics. Cambridge University Press, Cambridge, 1999. ISBN 0-521-56069-11 0-521-78987-7.
doi: 10.1017/H8078855116999 0133/0..1117CB0097880 1609589. Sergey Fomin.
wtw.librrr..sdd.duuu.... With foreword by Gian-Carlo Rota and appendix I by
URL
Yitong Sun, Anna Gilbert, and Ambuj Tewari. On the approximation properties random ReLU features. Preprint 1eXiv:1810.04377 [sta August 2019.
Matus Telgarsky. benefits of depth in neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.). 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 1517-1539, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL http::/ppoeeeeinns....esss////ee 16.mml.
12

---

Published as a conference paper at ICLR 2020
K. Wolsson. Linear dependence of a function set of m variables with vanishing generalized Wron- skians. Linear Algebra Appl., 117:73-80 80. 1989. ISSN 0024-3795, doi: 10.101600024-37955()) 90548-X. X. URL
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Newworks, 94:103 114, 2017. ISSN 0893-6080. doi: https///doi.or/10.1111111 10w..///........ee101..11.
URL
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. Preprint 110.::1994000087777 [stat.MI.], June 2019.
A GENERALIZED WRONSKIANS AND THE PROOF OF THEOREM 5.6
First, we recall the notion of generalized Wronskians as given in (LeVeque, 1956, Chap. 4.3). Let Ag,- A AN-I any N differential operators of the form
4
where on + ........ + On S k.
Let fN. P( The generalized Wronskian of (fi...., fN) associated to Ao...... , AN-1 defined as the determinant the matrix M = (=]1f(())]ssssss In general, (f1...., fN) has multiple generalized Wronskians, corresponding multiple choices for Ap..... AN-1-
A.1 PROOF OF THEOREM 5.6
For brevity, let N = (*+") and let x (I1, Tn)) Recall that X <.. ... < AN are all the n-tuples in A in the colexicographic order. For each S i, S N, write 2 (AR,I..... AB,)), ( 88 Ap. and let dx2 be the coefficient of the monomial 9h (x) in Ax)) Consider an arbitrary W E U. and for each 1 S j S N, define (fi..... fN) and note that det Mw (x)
8 A define the differential operator Ax, = (aey
fy E (R" by the map x + p w (1) ( Note that (P) by definition. Next, define the matrix Mw (x) == [Ar the generalized Wronskian of (fi...., fN) associated to A....., AN. In particular, this generalized Wronskian is well-defined, since the definition of the colexicographic order implies that A + Ak. <. k for all possible k. Similar to the univariate case, (fi...., fx) is linearly independent if (and only if) its generalized Wronskian not the zero function (Wolsson, 1989). Thus, to show that W E "yrind it suffices to show that the evaluation det Mw (1,)) of this generalized Wronskian at 1n gives non-zero value, where 1, denotes the all-ones vector in R
21,
Observe that the (i. j-th entry of Mw (1,) equals (w) ( Mw (I,,) M' M" where M' is an N-by-N matrix whose (i, ji-h entry is given by
(Ax,
hence we can check that
a (
if A X E AZai
Mr
-
0,
if if A & A
and where M" = Q[W) is the non-bias Vandermonde matrix W.
It follows from the definition of the colexicographic order that Aラ X; necessarily contains at least one strictly negative entry whenever j < i, hence we infer that M/ upper triangular. The diagonal entries of M are a!") a... ..... 2
(N) and note that e (A ... As.n!)a( for each 1 < i S N,
(i)
where At,1! \i,n! denotes the product of the factorials of the entries of the n-tuple A, partieular,
At,1!... Ain!! + 0, and axx; which is the coefficient of the monomial q: (x() in p(x), is non-zero. Thus, det dM'' + 0.
(1)
We have come to the crucial step of our proof. If we can show that det(M") = QQ[[)) + O. then det
= (M'' det( A)" * 0, and hence we can infer that W E Pzgind This means that "iqind contains the subset 2 C consisting of all W such that Q[W] non-singular. Note that dQW() is a polynomial in terms of the non-bias weights in W(I) as its variables, could write this polynomial as r(W). Consequently, if we can find single W U such that Q[W] is non-singular, then r(W) is not identically zero on U, which then implies that 4 = (W E 24 rWW of 0) is dense in 2/ (w.r.t the Fuclidean metric).
13

---

Published as a conference paper at ICLR 2020
A.2 PROOF OF COROLLARY 5.7
Let N : (" By Theorem 5.6, it suffices to show that there exists some W E WN such that the non-bias Vandermonde matrix of W is non-singular. Consider W " such that w (wff) Recall that the monomials in M are arranged in colexicographic order, i...
1, 2.. .T, 22, 21 of02. 22.2122............... 2
Thus, there are fixed integers 0 B1 < B2 < < BN, such that the j-th entry of Q[1 is (wf)) )ok Such matrices are well-studied in algebraic combinatorics, and the determinant of Q[W] is Schur polynomial: see (Stanley, 1999). In particular, if we choose positive pairwise distinct values for ( (for 1 J j S N), then Q[W] is non-singular, since a Schur polynomial can be expressed as (non-negative) sum of certain monomials; (Stanley, 1999, Sec. 7.10) for details.
B AN ANALOG OF KADEC'S THEOREM AND THE PROOF OF LEMMA 5.9
Throughout this section, suppose C(R) and let d 2 be an integer. We shall use the same definitions for {Ae JEN, (YE) and { TEEN as given immediately after Remark 5.8. Our goal for this section is prove Theorem B.1 below, that we can infer Lemma 5.9 consequence of Theorem B. Note that Theorem B. is an analog of the well-known Kadec's theorem (Kadec, 1960) from approximation theory. To prove Theorem B.I, we shall essentially follow the proof of Kadec's 's theorem as given in (Kadec, 1963).
We begin with a crucial observation. For every best polynomial approximant oy oly, of degree d, it is known that there are (at least) d + 2 values
1/4 S d
(k)
aj (k) <.. <a ad+1 S v/K
(k)
and some sign & E {+1), such that (a see (Rivlin, 1981, Thm. 1.7). Define
(k) on
(a (k))
(a(ttt) = Ealova)) for sisd++;
{
a 1/2
i
:0sisd+1
A = max
1/2
1/2
d+ d+1.
A&ht
Theorem B.1. If lim Ed(d)rz) = oc, then for any y > 0. we have lim inf
= 0.
k-000
17
Proof. For every & E N, define the functions ek ok and 0x+1 oh 0k+1 ck+1 Es-
Note that eg E C(R) and Φx+1 E (R). Since V4+1 S ah I yhs1 by assumption, it follows from the definition a++1 that - Ea(olye))) S (at)(a!t)) S Ea(olyin)). By the definition of a(*), we have (a()))) = (-1)
Consequently,
Ea(olve) - Ed (oo S (-1) ea+1)(a (1) Ea(olx)) + Edlolvesiss
equivalently, Ea(o) Ea(olven)) S (-1))82 (a( Ea(alvn4)) - Ea(alxi)-
Since Y2 S Yk+1 implies Ea < Ea(olye..). ), it follows that a2 S a. S azi (for each 0 < i < d 1), where 02;-1 and 02g the roots of the equation (dx+1 Ea(olya-n)
Eala lva
If E = Ea(o)r then 0++1 = o by definition, so we could set (*+11) = a(*) for all i, Le. there nothing to prove in this case. Henceforth, assume Ea (olx)))) * Fa(alv, ). and consider the polynomial function
d (v v)) ((v) Ed(alye.)) Fa(a)x))
then follows from (Kadec, 1963, Lem. 2) that
0
1 arcosh Ea(alrea + Ea(alv))
A < d d+1 d (d 1)0
Ea(alre.)) - Fa(a)v))
where 0 is an arbitrary real number satisfying 0
14

---

1+r Published as a conference paper at ICLR 2020
Ea(alyan) Ea(a
Since lim Fa(ollr.)) by assumption, the infinite product k=+00
diverges, and thus
k=0
Ea(a) - Ed(olx) also diverges. It then follows from (9) that Ed va+1) + Ea(aly))
the series
k=
00,
cosh (A a AN (d+ 1)0
hence
(D = 00 for any D > 1. If we compare the divergent series
( with
k=
the convergent series
(for any 0), we thus get
kI+7
inf DKAR k0000 1(1+r)/D
Therefore, the assertion follows by letting 7 D
AsdE = for any > 0.
Proof of Lemma 5.9. Fix & 0. By Theorem B.1, we have lim inl
k0000
Thus, by the definition of lim inf, there exists subsequence {k/ of N such that
Du: Au (K))
<
for all E N (given any 7 > 0). Since d is at least ((A7)) for some >> O, we can use this particular Agg
to get that lim inf
(-100 (Kg(7 > 0. Consequently, there is subsequence {ke heN of {K]en such that
| < e for all t E N. Since d 2 2 by assumption, it then follows that
1 d d+1
a (kc)
Vk.
(ke)
d+1 tE.
(10)
Ake
Ake
(ks). there is some (ki)
(k))
Now a ob, is continuous, so by the definition of ag
aj
< yk. < 02
such that
(Vk.) = The (uk,) From (10), we thus infer that min (lane Mi, liw,,, -V6, > I+I E as desired. D
C PROOFS OF REMAINING LEMMAS
C.I PROOF OF LEMMA 5.10
Theorem 2.2 gives |0, - olboo,,, = Ea(aly, s Gwaly, (2)) Recall that any modulus of continuity
wy is subadditive (i.e. wy(x + y) S wy(x) + (v) for all y); see (Rivlin, 1981, Chap. 1). Thus for fixed d, we have Wa 24 O()x), which implies (K + | alloo.rx) E o(11+))
C.2 PROOF OF LEMMA 5.11
Our proof of Lemma 5.11 is straightforward application of both the Cayley-Menger determinant formula and the Leibniz determinant formula. For each S i < N. let (A() == S (P)( and let (A) be the convex hull of Š,()). Let V(A(A)) (resp. (A),( denote the N-dimensional
(resp. (N - -)dimenniional) volume of A(8) (resp. (A)). Define the (N + b)- + 2)
matrix (() (A),, as follows: (A) = ((P%(A) (>) for all 0 $ i,j N
MN+1, (A) MA, = for all 0 < < N; and M (N+ 0.
N+1
The Cayley-Menger determinant formula gives [V((())] = (Níj.p det(M(() (A)). Analogously,
if we let (A) be the square submatrix of M M() obtained by deleting the first row and column from
15

---

Published as a conference paper at ICLR 2020
(ー1) M(A), then (V(ao [(N- 1-1-1))-2--- det (A)) Now, v(((A)) = V(Co(A))MO(A)
-1 det(M(())
[bo(2)] 2N det M')))
(11)
Without loss of generality, assume that ro ri .... Also, for any integer k: 2 0, let G₂ be the set of all permutations on (O...., k), and let 6 be the subset of 65 consisting of all permutations that are not derangements. (Recall that T E G& is called a derangement if T(i) o for all 0 S s k.) The diagonal entries of M (A) are all zeros, so by the Leibniz determinant formula, we get
det (M)))) = Σ 8gn(T) TT)
II M1r((9 (A), OSiGN-1
TEB
where sgg(T) denotes the sign of the permutation т. Note that MA)(() E O(X2 ((X2max(rs.rs)) for all 0 S i.j V N satisfying i + j. (Here, @ refers to @-complexity.) Consequently, using the fact that M1,N+1 (A) 1M+ for all 0 S i S N, we get that (e)(M(()) E @(22Rx) ) where
2ro + +................. (N
-i rt:
if N is even;
RN
2rp + +... + (N + 1//21 = - ((N-1)/2 + Ei= Te:
(N-11/2
is odd.
The even case corresponds to the derangement T N+ given by rii) - for 0 <is N=2 T N = N + r(N + 1) = N. while the odd case corresponds to the derangement T E G given by (i) = N - i for 0 < i N-3 7( (يا
N+1 T( ( N + 1, -(N + + = 2
N-1
A formula for det (M' can be analogously computed. Consequently, follows from (11) that (a)]² (X2 (ec/2ro-_(w/0 >))/al)). Now, ro 2 r N/2/ by assumption, and ro (being the largest) must satisfy ro mmin thus (o E 2((*)), and the assertion follows by taking Y ro Tmin-
C.3 PROOF OF LEMMA 5.12
Consider any open neighhorhood U of Oas- Since is open and (00w) = ON. the image (U) always choose N 1 points
must contain an open neighborhood of Ov- Thus for any >> O, Wo...., UN in B. }. such that the convex hull of (.. ((WN)] contains the point ON. Since (Ax) 2 Xxp(x) for all
R.M À 0, and since y is continuous, then follows from definition that for every lo E N. we can choose N+1 points u/ ..... u in UR. such that the convex hull of U3- = ((( )...., ( contains ON- Define T == sup(r > 0: B C ( (Bx))) )} for each & E N, and note also that limg-+00 Th Thus, given ball B& of any desired radius, there is some (sufficiently large) such that the convex hull of U/ contains B,N.
Now, since 0사x+ < |lu{*)|22 [|2 S d and ((Auff))) 2 {x(x((*) for all 0 S S N O we infer that none of the points (p(u(())..... p(.(..,((((()))) are contained in the ball B Consequently, as k do, have Prk + oc, and therefore the barycentric coordinate vector (bu...., bu) (w.rt. U%) of every point in the fixed ball B: would converge to ( . * (which is the barycentric coordinate vector of the barycenter w.r.t U});; this proves our assertion.
D CONJECTURED OPTIMALITY OF UPPER BOUND OEET)) IN THEOREM 3.2
It was conjectured by Mhaskar (1996) that there exists some smooth non-polynomial function o,, such that at least ((=-)) hidden units is required to uniformly approximate every function in the class G of C2 functions with bounded Sobolev norm. As evidence that this conjecture is true, heuristic argument was provided in (Mhaskar, 1996), which uses a result by Ve et al. (1989); cf. (Pinkus, 1999, Thm. 6.5). To the best of our knowledge, this conjecture remains open. If this conjecture is indeed true, then our upper bound Os=-)) in Theorem 3.2 is optimal for general continuous non-pol nol-polylamial activation functions.
For specific activation functions, such as the logistic sigmoid function, or any polynomial spline function of fixed degree with finitely many knots (e.g. the ReLU function), known that the minimum number N of hidden units required to uniformly approximate every function in & must satisfy (N log N) E ?(==") (Maiorov & Meir, 2000); ef. (Pinkus, 1999, Thm. 6.7). Hence there is still gap between the lower and upper bounds for N in these specific cases. It would be interesting to find optimal bounds for these cases.
16


Reviews:
[{"review_id": "S1eH2aMfqB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This this exciting submission presents a new proof of Leshno's version of the universal approximation property (UAP) for neural networks  -- one of the foundational pillars of our understanding of neural networks. The new proof provides new insights into the universal approximation property. I consider these the main contribution of the paper. Specifically, the authors\n- provide an upper bound on the required width for the neural network\n- show that the approximation property still holds even if strong further requirements are imposed on the weights of the first or last layer. \n\nI rate this submission a weak accept. It’s a very good paper. The work makes useful contributions that should and will be of interest to many in the field. The paper is generally well-written. \n\n\nSome remarks:\n\n- Being somewhat long, the “Proof of Theorem 3.1” would be a much better read if the authors prefixed it  with an outline of the strategy that the proof takes. \n\n- The authors point out that the lack of dependence of Theorem 3.1 on epsilon is surprising, and cite Lin’s work from 2017 who previously found such an independence. Lin’s derivation of the epsilon-independent UAP is much more intuitive than that of this submission, in which the epsilon independence really pops out somewhat magically and for me only made sense when I read the paper again. I would encourage the authors to add to Lin’s paper’s citation sentence that this paper motivates the epsilon independence well. Alternatively, the authors could add a few sentences to their paper to provide intuition on how the epsilon-independence comes about in their line of argument. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxGV3eP2r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "UPDATE TO MY EARLIER REVIEW\n============================\n\nSince this paper presets new findings that will be of significant interest to much of ICLR's audience, and the paper is is well-written, I am changing my rating to \"Accept\". Since Reviewer #1 did not submit a review and Reviewer #2 indicated that (s)he does not feel well-qualified to review this paper (it is very much on the theoretical side after all), it would be great to get one further review from an area chair or otherwise qualified person. \n\nMY EARLIER REVIEW\n=================\n\nThis this exciting submission presents a new proof of Leshno's version of the universal approximation property (UAP) for neural networks  -- one of the foundational pillars of our understanding of neural networks. The new proof provides new insights into the universal approximation property. I consider these the main contribution of the paper. Specifically, the authors\n- provide an upper bound on the required width for the neural network\n- show that the approximation property still holds even if strong further requirements are imposed on the weights of the first or last layer. \n\nI rate this submission a weak accept. It’s a very good paper. The work makes useful contributions that should and will be of interest to many in the field. The paper is generally well-written. \n\n\nSome remarks:\n\n- Being somewhat long, the “Proof of Theorem 3.1” would be a much better read if the authors prefixed it  with an outline of the strategy that the proof takes. \n\n- The authors point out that the lack of dependence of Theorem 3.1 on epsilon is surprising, and cite Lin’s work from 2017 who previously found such an independence. Lin’s derivation of the epsilon-independent UAP is much more intuitive than that of this submission, in which the epsilon independence really pops out somewhat magically and for me only made sense when I read the paper again. I would encourage the authors to add to Lin’s paper’s citation sentence that this paper motivates the epsilon independence well. Alternatively, the authors could add a few sentences to their paper to provide intuition on how the epsilon-independence comes about in their line of argument. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xtdl4CYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors derive the universal approximation property proofs algebraically. They note that this holds even with very strong constraints on the non-bias weights. \n\nThey assert that their results are general to other kinds of neural networks and similar learners. They leave the paper with a question regarding limitations on bias weights. \n\nI do not feel qualified to review this paper. I have opted for a weak accept since it seems thorough and the conclusions offer promise for other applications. However, I will defer to other, more qualified reviewers who have more carefully reviewed the paper than I have. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "B1gx-ia29r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the representation power of single layer neural networks with continuous non-polynomial activation, and specifically, provided a refinement for the universal approximation theorem:\n1.  Established an exact upper bound on the width needed to uniformly approximate polynomials of a finite degree (to any accuracy of which the upper bound is independent), and\n2.  using this error-free bound to deduce a rate (of width) for approximating continuous functions.\n\nThe writing of the paper is concrete and solid.  The techniques used in establishing the results are interesting, in that:\n1.  The proof for polynomial approximation (Thm 3.1) is direct, via a close examination of the Wronskian of the target polynomial function, and\n2.  the analysis provided that the abilty to universally approximate is also preserved after placing certain restriction on the magnitude of the weights in the approximating neural network.  Consequently, this property is inherited by continuous function approximation to which the result is extended (Thm 3.2).\n3.  This analysis and some of the results derived in the proof may be used for other analyses, e.g. representation power of multilayer networks.\n\nSome further discussion of the results may be of interest to the readers.  \n-  (Optimality of Thm 3.2).  When the result in Thm 3.1 is extended to general continous functions via Jackson's theorem, to what extend does the rate deteriorate?  What does the rate look like when using certain common activations (such as ReLU, sigmoid).\n-  (Reference to random features).  Thm 3.3 appears to be related to random feature representation, whose approximating ability has been studied in prior works.  Some comment on those results may be beneficial (e.g. https://arxiv.org/abs/1810.04374).\n-  Although already a straightforward proof, it seems natural, and as a result may promote the presentation and clarity, to organize the proof to Thm 3.1 using smaller parts, which currently spans over 2 pages.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a nice paper on the classical problem of universal approximation, but giving a direct proof with good approximation rates, and providing many refinements and ties to the literature.

If possible, I urge the authors to revise the paper further for camera ready; there are various technical oversights (e.g., 1/lambda should appear in the approximation rates in theorem 3.1), and the proof of theorem 3.1 is an uninterrupted 2.5 page block (splitting it into lemmas would make it cleaner, and also those lemmas could be useful to other authors).
Decision: Accept (Poster)