A standard (feedforward) neural network with n input units, m output units, and with one or more hidden layers, refers to a computational model N that can compute a certain class of functions , where
is parametrized by W (called the weights of N). Implicitly, the definition of
depends on a choice of some fixed function
, 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 to 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 a standard neural network with one hidden layer would be able to uniformly approximate any continuous function
whose domain
is compact. Hornik (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, a standard neural network with one hidden layer is able to uniformly approximate any continuous function
on any compact
, if and only if
is non-polynomial.
Although a 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 real-valued continuous functions on a compact set , a fixed activation function
, and some
, let
be the minimum number of hidden units required for a single-hidden-layer neural network to be able to uniformly approximate every
within an approximation error threshold of
. If
is the rectified linear unit (ReLU)
, then N is at least
when F is the class of
non-linear functions (Yarotsky, 2017), or the class of strongly convex differentiable functions (Liang & Srikant, 2016); see also (Arora et al., 2018). If
is any smooth non-polynomial function, then N is at most
for the class of
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
is 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
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
, the bound is still
, independent of m.
To prove this bound, we shall give a direct algebraic proof of the universal approximation theorem, in its general version as stated by Leshno et al. (1993) (i.e. is continuous and non-polynomial). 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 is that if F is the subclass of polynomial functions
with total degree at most d for each coordinate function, then
hidden units would suffice. In particular, notice that our bound
does not depend on the approximation error threshold
or the output dimension m.
We shall also show that the UAP holds even under strong conditions on the weights. Given any , we can always choose the non-bias weights in the last layer to have small magnitudes no larger than
. Furthermore, we 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
. 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 to restricted weight values.
Outline: 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 in the appendix. Finally, Section 6 concludes our paper with further remarks.
2.1 NOTATION AND DEFINITIONS
Let N be the set of non-negative integers, let be the zero vector in
, and let
be the vector space of all k-by-
matrices with real entries. For any function
, let
denote the t-th coordinate function of f (for each
). Given
and any n-tuple
, we write
to mean
. If
, then
is a real number, while if x is a sequence of variables, then
is a monomial, i.e. an n-variate polynomial with a single term. Let
for each
, and define
. If the context is clear, we supress the superscripts n, m in
and
.
Given any , let C(X) be the vector space of all continuous functions
. We use the convention that every
is a function
in terms of the variables
, unless n = 1, in which case f is in terms of a single variable x (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
, let
(resp.
) be the subspace consisting of all polynomial functions of total degree
(resp. exactly d). More generally, let
be the vector space of all continuous functions
, and define
analogously.
Throughout, we assume that . For every
, let
be the j-th column vector of
, and let
be the (i, j)-th entry of
(for k = 1, 2). The index i begins at i = 0, while the indices j, k begin at j = 1, k = 1 respectively. For convenience, let
denote the truncation of
obtained by removing the first entry
. Define the function
so that for each
, the j-th coordinate function
is given by the map
where “” denotes dot product, and (1, x) denotes a column vector in
formed by concatenating 1 before x. The class of functions that neural networks N with one hidden layer can compute is precisely
, where
is called the activation function of N (or of
). Functions
satisfying
correspond to neural networks with N hidden units (in its single hidden layer). Every
is called a weight in the k-th layer, where
is called a bias weight (resp. non-bias weight) if i = 0 (resp.
).
Notice that we do not apply the activation function to the output layer. This is consistent with previous approximation results for neural networks. The reason is simple:
(restricted to domain
) cannot possibly approximate
if there exists some
such that
is bounded away from
. If instead f(X) is contained in the closure of
, then applying
to
has essentially the same effect as allowing for bias weights
.
Although some authors, e.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
, then having a bias weight
is equivalent to setting
(i.e. no bias weight in the output layer) and introducing an (N + 1)-th hidden unit, with corresponding weights
for all
, and
; this means our results also apply to neural networks without bias weights in the output layer (but with one additional hidden unit).
2.2 ARGUMENTS INVOLVING DENSE SUBSETS
A key theme in this paper is the use of dense subsets of metric spaces. We shall consider several notions of “dense”. First, recall that a metric on a set S is any function such that for
all , the following conditions hold:
The set S, together with a metric on S, is called a metric space. For example, the usual Euclidean norm for vectors in gives the Euclidean metric
, hence
is a metric space. In particular, every pair in
can be identified with a vector in
, so
, together with the Euclidean metric, is a metric space.
Given a metric space X (with metric d), and some subset , we say that U is dense in X (w.r.t. d) if for all
and all
, there exists some
such that
. Arbitrary unions of dense subsets are dense. If
and U is dense in X, then
must also be dense in X.
A basic result in algebraic geometry says that if is non-zero, then
is a dense subset of
(w.r.t. the Euclidean metric). This subset is in fact an open set in the Zariski topology, hence any finite intersection of such Zariski-dense open sets is dense; see (Eisenbud, 1995). More generally, the following is true: Let
, and suppose that
for all
. If
is non-zero, then
is a dense subset of X (w.r.t. the Euclidean metric). In subsequent sections, we shall frequently use these facts.
Let 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 f whose domain contains X, the uniform norm of f on X is
. More generally, if
, then we define
. The uniform norm of functions on X gives the uniform metric
, hence C(X) is a metric space.
2.3 BACKGROUND ON APPROXIMATION THEORY
Theorem 2.1 (Stone–Weirstrass theorem). Let be compact. For any
, there exists a sequence
of polynomial functions in P(X) such that
.
Let be compact. For all
and
, define
A central result in approximation theory, due to Chebyshev, says that for fixed d, f, the infimum in (1) is attained by some unique ; see (Rivlin, 1981, Chap. 1). (Notice here that we define
to have domain R.) This unique polynomial
is called the best polynomial approximant to f of degree d.
Given a metric space X with metric d, and any uniformly continuous function , the modulus of continuity of f is a function
defined by
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 be an integer, and let
be a closed interval of length
. Suppose
, and let
be the best polynomial approximant to f of degree d. Then
.
Throughout this section, let be a compact set.
The universal approximation theorem (version of Leshno et al. (1993)) is an immediate consequence of Theorem 3.2 and the observation that must be non-polynomial for the UAP to hold, which follows from the fact that the uniform closure of
is
itself, for every integer
. Alternatively, we could infer the universal approximation theorem by applying the Stone–Weirstrass theorem (Theorem 2.1) to Theorem 3.1.
Given fixed n, m, d, a compact set , and
, Theorem 3.1 says that we could use a fixed number N of hidden units (independent of
) and still be able to approximate any function
to any desired approximation error threshold
. Our
-free bound, although possibly surprising to some readers, is not the first instance of an
-free bound: Neural networks with two hidden layers of sizes 2n + 1 and 4n + 3 respectively are able to uniformly approximate any
, provided we use a (somewhat pathological) activation function (Maiorov & Pinkus, 1999); cf. (Pinkus, 1999). Lin et al. (2017) showed that for fixed n, d, and a fixed smooth non-linear
, there is a fixed N (i.e.
-free), such that a neural network with N hidden units is able to approximate any
. An explicit expression for N is not given, but we were able to infer from their constructive proof that
hidden units are required, over
hidden layers (for
. In comparison, we require less hidden units and a single hidden layer.
An interesting consequence of Theorem 3.3 is the following: The freezing of lower layers of a neural network, even in 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 single-hidden-layer case, we have shown that if the non-bias weights in the 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 a 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.
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 (Yehudai & Shamir, 2019).
The UAP is also studied in other contexts, most notably in relation to 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 bounded-width 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´ufar 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; cf. (Mhaskar et al., 2017).
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 be real numbers. For each
, define
by
. Then
are linearly independent if and only if
are distinct.
Proof. For each and each
, let
(resp.
) be the i-th derivative of
(resp. p), and let
be the coefficient of
in
. Recall that the Wronskian of
is defined to be the determinant of the matrix
. Since
are polynomial functions, it follows that
is a sequence of linearly independent functions if and only if its Wronskian is not the zero function (LeVeque, 1956, Thm. 4.7(a)). Clearly, if
for
, then det M(x) is identically zero. Thus, it suffices to show that if
are distinct, then the evaluation det M(1) of this Wronskian at x = 1 gives a non-zero value.
Now, the (i, j)-th entry of M(1) equals , so
, where
is an upper triangular matrix whose (i, j)-th entry equals
, and
is the transpose of a Vandermonde matrix, whose determinant is
Note that the k-th diagonal entry of is
, which is non-zero by assumption, so
. Thus, if
are distinct, then
.
Definition 5.2. Given , and any function
, let
denote the sequence of functions
, such that each
is defined by the map
. Also, define the set
is linearly independent}. Note that the value of m is irrelevant for defining
.
Remark 5.3. Given , consider the ring automorphism
induced by
for all
. For any
and scalars
R, note that
if and only if
, thus linear independence is preserved under
. Consequently, if the function g in Definition 5.2 is polynomial, then
for all
.
Corollary 5.4. Let m be arbitrary. If has all-non-zero coefficients, then
is a dense subset of
(in the Euclidean metric).
Proof. For all , let
, and note that
is dense in
. So by Theorem 5.1,
is also dense in
.
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 a generalization of the Vandermonde matrix as described in (D’Andrea & Tabera, 2009). (Other generalizations of the Vandermonde matrix exist in the literature.) First, define the sets
It is easy to show that , and that the set
of monomial functions forms a basis for
. Sort the n-tuples in
in colexicographic order, i.e.
if and only if
for the largest index i such that
. Let
denote all the
in in this order, i.e. each
is given by the map
. Given any sequence
of vectors in
, the generalized Vandermonde matrix associated to it is
Definition 5.5. Given any , we define the non-bias Vandermonde matrix of W to be the generalized Vandermonde matrix
associated to
. Theorem 5.6. Let m be arbitrary, let
, and suppose that p has all-non-zero coefficients. Also, suppose that
are fixed polynomial functions on the non-bias weights of the first layer. Define the following sets:
If there exists such that the non-bias Vandermonde matrix of W is non-singular, then
is dense in U (w.r.t. the Euclidean metric).
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 for proof details.
Corollary 5.7. Let m be arbitrary. If is a fixed polynomial function of degree d with all-non-zero coefficients, then
is a dense subset of
.
Proof. By Theorem 5.6, it suffices to show that there is some 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 in the first layer to satisfy
for some fixed constant
.
For the rest of this section, let be a divergent increasing sequence of positive real numbers, and let
be a sequence of closed intervals of R, such that
whenever
, and such that each interval
has length
. Let
be an integer, and suppose
. For each
, let
be the best polynomial approximant to
of degree d. Given r > 0 and any integer
, define the closed ball
.
Lemma 5.9. If , and
for some
, then for every
, there is a subsequence
of N, and a sequence
of real numbers, such that
, and
for all . (See Appendix B for proof details.)
Lemma 5.11. Let be integers, let
be fixed real numbers, and let
be a set
of N + 1 affinely independent points in
, parametrized by
, where each point
has (Cartesian) coordinates
for some fixed non-zero scalars
. Let
be the convex hull of
, i.e.
is an N-simplex, and for each
, let
be the height of
w.r.t. apex
. Let
and
. If
for some
, then there exists some
such that
.
Lemma 5.12. Let be integers, let
, and let
. Suppose
is a continuous open map such that
, and
for all
. Let
be a sequence where each
is a dense subspace of
. Then for every
, there exists some (sufficiently large)
, and some points
in
, such that for each point
, there are scalars
satisfying
, and
for all
.
Outline of strategy for proving Theorem 3.1. The first crucial insight is that , as a real vector space, has dimension
. Our strategy is to consider
hidden units. Every hidden unit represents a continuous function
determined by its weights W and the activation function
. If
can be well-approximated (on X) by linearly independent polynomial functions in
, then we can choose suitable linear combinations of these N functions to approximate all coordinate functions
(independent of how large m is). To approximate each
, we consider a suitable sequence
of degree d polynomial approximations to
, so that
is approximated by a sequence of degree d polynomial functions
. We shall also vary W concurrently with k, so that
increases together with k. By Corollary 5.7, the weights can always be chosen so that
are linearly independent.
The second crucial insight is that every function in can be identified geometrically as a point in Euclidean
-space. We shall choose the bias weights so that
correspond to points on a hyperplane, and we shall consider the barycentric coordinates of the projections of both
and the constant function onto this hyperplane, with respect to
. As the values of k and
increase, both projection points have barycentric coordinates that approach
, and their difference approaches 0; 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 , and for brevity, let
. Theorem 3.1 is trivially true when f is constant, so assume f is non-constant. Fix a point
, and define
by
for all
. Next, let
, and note that
, since X is compact. By replacing X with a closed tubular neighborhood of X if necessary, we may assume without loss of generality that
.
Define and
as before, with an additional condition that
for some
. Assume without loss of generality that there exists a sequence
of real numbers, such that
, and
for all . The validity of this assumption in the case
is given by Lemma 5.9. If instead
, then as
, the sequence
converges to some
. Hence, the assumption is also valid in this case, since for any
such that
, we can always choose
to satisfy
for all
, which then allows us to choose
that satisfies
.
By Lemma 5.10, we may further assume that for all
, where C > 0 and
are constants whose precise definitions we give later. Also, for any
, we can choose
that is arbitrarily close to
in the uniform metric, such that
is arbitrarily small. Since
by assumption, we may hence perturb
if necessary, and assume without loss of generality that every
is a polynomial of degree d with all-non-zero coefficients, such that
.
Each is well-defined, since
. Note also that
by definition, hence it follows from (3) that
. In particular,
is a divergent increasing sequence of positive real numbers.
Given any , let
denote the vector of coefficients with respect to the basis
(i.e. if
, then
), and let
be the truncation of
by removing the first coordinate. Note that
is the constant monomial, so this first coordinate
is the coefficient of the constant term. For convenience, let
(resp.
) be the i-th entry of
(resp.
).
For each , define functions
in C(X) by
and
respectively. By definition,
can be treated as a function of W, and note that
for any
. (Here,
denotes the total degree of
.) Since
only if i = 1, it then follows that
for all
.
For each , define the “shifted” function
by
. Next, let
, and suppose
. Note that in the definition of
, we do not impose any restrictions on the bias weights. Thus, given any such W, we could choose the bias weights of
to be
for all
. This implies that each
represents the map
, hence
. Consequently,
By Corollary 5.7 and Remark 5.3, is dense in
, so such a W exists (with its bias weights given as above). By the definition of
, we infer that
is linearly independent and hence spans
. Thus, for every
, there exist
, which are uniquely determined once k is fixed, such that
. Evaluating both sides of this equation at
, we then get
For each , define the hyperplane
. Recall that
is the constant monomial, so the first coordinate of each
equals
, which implies that
are N points on
. Let
. (This is non-zero, since f is non-constant.) Note that
and
(for all t) are points in
. So for any
, Lemma 5.12 implies that there exists some sufficiently large
such that we can choose some
, so that there are non-negative scalars
(for
,
) contained in the interval
that satisfy the following:
Note that and
, so we get
Since are unique (for fixed k), we infer that
for each
. Thus, for this sufficiently large k, it follows from
that
Let , let
be the convex hull of
, and for each j, let
be the height of
w.r.t. apex
. Let
. Since
for all i, and since
(i.e.
), it follows from Lemma 5.11 that there exists some
such that
. Using this particular
, we infer that there exists some constant
such that
for all sufficiently large k.
Note that is an upper bound of the normalized difference for each barycentric coordinate of the two points
and
(contained in
), which satisfies
Now, define . Thus, for sufficiently large k, it follows from (5), (6) and (7) that
For this sufficiently large k, define by
for each t. Using (4) and (8), it follows that
Finally, for all , let
for each
, and let
. This gives
. Therefore, the identity
implies
.
Notice that for all , we showed in (6) that there is a sufficiently large k such that
. A symmetric argument yields
. Thus, for all
, we can choose W so that all non-bias weights in
are contained in the interval
; this proves assertion (i) of the theorem.
Note also that we do not actually require to be arbitrarily small. Suppose instead that we choose
sufficiently large, so that the convex hull of
contains
and
(for all t). In this case, observe that our choice of k depends only on f (via
) and
(via the definition of
). The inequality (7) still holds for any
satisfying
for all j, t. Thus, our argument to show
holds verbatim, which proves assertion (ii).
Proof of Theorem 3.2. Fix some , and consider an arbitrary
. For each integer
, let
be the best polynomial approximant to
of degree d. By Theorem 2.2, we have
for all
, hence it follows from the definition of
that
Define . Note that
, and
(for all
). By Theorem 3.1, there exists some
satisfying
for all
, which implies
therefore . Conditions (i) and (ii) follow from Theorem 3.1. Finally, note that
(for fixed D), i.e.
, hence
.
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[W]) is a non-zero polynomial in terms of the weights W, hence is dense in
, or equivalently, its complement has Lebesgue measure zero.
Theorem 5.6 is rather general, and could potentially be used to prove analogs of the universal approximation theorem for other classes of neural networks, such as convolutional neural networks and recurrent neural networks. In particular, finding a single suitable set of weights (as a representative of the infinitely many possible sets of weights in the given class of 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 to 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 to eventually yield a 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 to 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?
This research is supported by the National Research Foundation, Singapore, under its NRFF program (NRFFAI1-2019-0005).
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=B1JrgWRW.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303–314, December 1989. doi: 10.1007/BF02551274. URL https://doi.org/10.1007/BF02551274.
Carlos D’Andrea and Luis Felipe Tabera. Tropicalization and irreducibility of generalized Vandermonde determinants. Proc. Amer. Math. Soc., 137(11):3647– 3656, 2009. ISSN 0002-9939. doi: 10.1090/S0002-9939-09-09951-1. URL https://doi-org.library.sutd.edu.sg:2443/10.1090/S0002-9939-09-09951-1.
Olivier Delalleau and Yoshua Bengio. Shallow vs. deep sum-product networks. In J. ShaweTaylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 24, pp. 666–674. Curran Associates, Inc., 2011. URL http://papers.nips.cc/paper/4350-shallow-vs-deep-sum-product-networks.pdf.
Ronald A. DeVore, Ralph Howard, and Charles Micchelli. Optimal nonlinear approximation. Manuscripta Math., 63(4):469–478, 1989. ISSN 0025-2611. doi: 10.1007/BF01171759. URL https://doi-org.library.sutd.edu.sg:2443/10.1007/BF01171759.
David Eisenbud. Commutative algebra, volume 150 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. ISBN 0-387-94268-8; 0-387-94269-6. doi: 10.1007/ 978-1-4612-5350-1. URL http://dx.doi.org/10.1007/978-1-4612-5350-1. With a view toward algebraic geometry.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward 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. 907– 940, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR. URL http://proceedings.mlr.press/v49/eldan16.html.
K. Funahashi. On the approximate realization of continuous mappings by neural networks. Neural Netw., 2(3):183–192, May 1989. ISSN 0893-6080. doi: 10.1016/0893-6080(89)90003-8. URL http://dx.doi.org/10.1016/0893-6080(89)90003-8.
Boris Hanin. Universal function approximation by deep neural nets with bounded width and relu activations. 08 2017. Preprint arXiv:1708.02691 [stat.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: 10.1016/0893-6080(89) 90020-8. URL http://dx.doi.org/10.1016/0893-6080(89)90020-8.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251 – 257, 1991. ISSN 0893-6080. doi: https://doi.org/10.1016/0893-6080(91)90009-T. URL http://www.sciencedirect.com/science/article/pii/089360809190009T.
M. I. Kadec. On the distribution of points of maximum deviation in the approximation of continuous functions by polynomials. Uspehi Mat. Nauk, 15(1 (91)):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.1090/trans2/026/09. URL https://doi-org.library.sutd.edu.sg:2443/10.1090/trans2/026/09.
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with a nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861 – 867, 1993. ISSN 0893-6080. doi: https://doi.org/10.1016/S0893-6080(05)80131-5. URL http://www.sciencedirect.com/science/article/pii/S0893608005801315.
William Judson LeVeque. Topics in number theory. Vols. 1 and 2. Addison-Wesley Publishing Co., Inc., Reading, Mass., 1956.
Shiyu Liang and R. Srikant. Why deep neural networks? CoRR, abs/1610.04161, 2016. URL http://arxiv.org/abs/1610.04161.
Henry W. Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work so well? Journal of Statistical Physics, 168(6):1223–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 Processing Systems 30, pp. 6231–6239. Curran Associates, Inc., 2017. URL http://papers.nips.cc/paper/7203-the-expressive-power-of-neural-networks-a-view-from-the-width.pdf.
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–103, 2000. ISSN 1019-7168. doi: 10.1023/A:1018993908478. URL https://doi-org.library.sutd.edu.sg:2443/10.1023/A:1018993908478.
Vitaly Maiorov and Allan Pinkus. Lower bounds for approximation by mlp neural networks. Neurocomputing, 25(1):81 – 91, 1999. ISSN 0925-2312. doi: https://doi.org/10.1016/S0925-2312(98) 00111-8. URL http://www.sciencedirect.com/science/article/pii/S0925231298001118.
H. N. Mhaskar. Neural networks for optimal approximation of smooth and analytic functions. Neural Computation, 8(1):164–177, Jan 1996. doi: 10.1162/neco.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/ocs/index.php/AAAI/AAAI17/paper/view/14849.
Guido Mont´ufar, 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://dl.acm.org/citation.cfm?id=2969033.2969153.
Allan Pinkus. Approximation theory of the mlp 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.1109/ALLERTON.2008.4797607.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS’07, pp. 1177–1184, USA, 2007. Curran Associates Inc. ISBN 978-1-60560-352-0. URL http://dl.acm.org/citation.cfm?id=2981562.2981710.
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 Advanced Mathematics. Cambridge University Press, Cambridge, 1999. ISBN 0-521-56069-1; 0-521-78987-7. doi: 10.1017/CBO9780511609589. URL https://doi-org.library.sutd.edu.sg:2443/10.1017/CBO9780511609589. With a foreword by GianCarlo Rota and appendix 1 by Sergey Fomin.
Yitong Sun, Anna Gilbert, and Ambuj Tewari. On the approximation properties of random ReLU features. Preprint arXiv:1810.04374v3 [stat.ML], 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://proceedings.mlr.press/v49/telgarsky16.html.
K. Wolsson. Linear dependence of a function set of m variables with vanishing generalized Wronskians. Linear Algebra Appl., 117:73–80, 1989. ISSN 0024-3795. doi: 10.1016/0024-3795(89) 90548-X. URL https://doi-org.library.sutd.edu.sg:2443/10.1016/0024-3795(89)90548-X.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103 – 114, 2017. ISSN 0893-6080. doi: https://doi.org/10.1016/j.neunet.2017.07.002. URL http://www.sciencedirect.com/science/article/pii/S0893608017301545.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. Preprint arXiv:1904.00687v2 [stat.ML], June 2019.
A GENERALIZED WRONSKIANS AND THE PROOF OF THEOREM 5.6
Let . The generalized Wronskian of
associated to
is defined as the determinant of the matrix . In general,
has
multiple generalized Wronskians, corresponding to multiple choices for .
A.1 PROOF OF THEOREM 5.6
For brevity, let and let
. Recall that
are all the
n-tuples in in the colexicographic order. For each
, write
,
define the differential operator , and let
be the coefficient of
the monomial in
. Consider an arbitrary
, and for each
, define
by the map
. Note that
by definition. Next, define the matrix , and note that
is
the generalized Wronskian of associated to
. In particular, this generalized
Wronskian is well-defined, since the definition of the colexicographic order implies that
for all possible k. Similar to the univariate case,
is linearly independent if
(and only if) its generalized Wronskian is not the zero function (Wolsson, 1989). Thus, to show that
, it suffices to show that the evaluation
of this generalized Wronskian at
gives a non-zero value, where
denotes the all-ones vector in
.
Observe that the (i, j)-th entry of equals
, hence we can check that
, where
is an N-by-N matrix whose (i, j)-th entry is given by
It follows from the definition of the colexicographic order that necessarily contains at least
one strictly negative entry whenever j < i, hence we infer that is upper triangular. The diagonal
entries of are
, and note that
for each
,
where denotes the product of the factorials of the entries of the n-tuple
. In particular,
, and
, which is the coefficient of the monomial
in p(x), is non-zero.
Thus, .
We have come to the crucial step of our proof. If we can show that ,
then , and hence we can infer that
. This
means thatcontains the subset
consisting of all W such that Q[W] is non-singular.
Note that det(Q[W]) is a polynomial in terms of the non-bias weights in as its variables,
so we could write this polynomial as r = r(W). Consequently, if we can find a single
such that Q[W] is non-singular, then r(W) is not identically zero on U, which then implies that
is dense in U (w.r.t. the Euclidean metric).
A.2 PROOF OF COROLLARY 5.7
Let . By Theorem 5.6, it suffices to show that there exists some
such that
the non-bias Vandermonde matrix of W is non-singular. Consider such that
. Recall that the monomials in
are arranged in colexicographic order, i.e.
Thus, there are fixed integers , such that the (i, j)-th entry of Q[W] is
. Such matrices are well-studied in algebraic combinatorics, and the determinant of Q[W] is
a Schur polynomial; see (Stanley, 1999). In particular, if we choose positive pairwise distinct values
for (for
), then Q[W] is non-singular, since a Schur polynomial can be expressed as
a (non-negative) sum of certain monomials; see (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 and let
be an integer. We shall use the same
definitions for and
as given immediately after Remark 5.8. Our goal
for this section is to prove Theorem B.1 below, so that we can infer Lemma 5.9 as a consequence
of Theorem B.1. Note that Theorem B.1 is an analog of the well-known Kadec’s theorem (Kadec,
1960) from approximation theory. To prove Theorem B.1, we shall essentially follow the proof of
Kadec’s theorem as given in (Kadec, 1963).
We begin with a crucial observation. For every best polynomial approximant to
of degree
d, it is known that there are (at least) d + 2 values
and some sign , such that
for all
;
see (Rivlin, 1981, Thm. 1.7). Define
Theorem B.1. If , then for any
, we have
.
Proof. For every , define the functions
and
.
Note that and
. Since
by assumption, it follows
from the definition of that
. By the definition of
, we have
. Consequently,
or equivalently, .
Since implies
, it follows that
(for each
), where
and
are the roots of the equation
.
If , then
by definition, so we could set
for all i,
i.e. there is nothing to prove in this case. Henceforth, assume , and consider
the polynomial function
It then follows from (Kadec, 1963, Lem. 2) that
where is an arbitrary real number satisfying
.
Since by assumption, the infinite product
the series
hence
the convergent series
Therefore, the assertion follows by letting .
Proof of Lemma 5.9. Fix . By Theorem B.1, we have lim inf
Thus, by the definition of lim inf, there exists a subsequence of N such that
for all (given any
). Since
is at least
for some
, we can use this particular
for all
. Since
by assumption, it then follows that
Now is continuous, so by the definition of
, there is some
such that
. From (10), we thus infer that
as desired.
C PROOFS OF REMAINING LEMMAS
C.1 PROOF OF LEMMA 5.10
Theorem 2.2 gives . Recall that any modulus of continuity
is subadditive (i.e.
for all x, y); see (Rivlin, 1981, Chap. 1). Thus
for fixed d, we have , which implies
.
C.2 PROOF OF LEMMA 5.11
Our proof of Lemma 5.11 is a straightforward application of both the Cayley–Menger determinant
formula and the Leibniz determinant formula. For each , let
, and
let be the convex hull of
. Let
(resp.
) denote the N-dimensional
(resp. -dimensional) volume of
(resp.
). Define the (N + 2)-by-(N + 2)
matrix as follows:
for all
for all
; and
.
The Cayley–Menger determinant formula gives . Analogously,
if we let be the square submatrix of
obtained by deleting the first row and column from
), then [
))]
=
det(
)). Now, V(∆(
)) =
), so
(11) Without loss of generality, assume that
. Also, for any integer
, let
be the set of all permutations on {0, . . . , k}, and let
be the subset of
consisting of all permutations that are not derangements. (Recall that
is called a derangement if
for all
.) The diagonal entries of
are all zeros, so by the Leibniz determinant formula, we get
where denotes the sign of the permutation
. Note that
for all
satisfying
. (Here,
refers to
-complexity.) Consequently, using the fact that
for all
, we get that
, where
C.3 PROOF OF LEMMA 5.12
Consider any open neighborhood U of . Since
is open and
, the image
must contain an open neighborhood of . Thus for any
, we can always choose N + 1 points
in
, such that the convex hull of
contains the point
. Since
for all
, and since
is continuous, it then follows from
definition that for every , we can choose N+1 points
in
, such that the convex
hull of contains
. Define
for
each , and note also that
. Thus, given a ball
of any desired radius, there
is some (sufficiently large) k such that the convex hull of contains
.
Now, since and
for all
, we infer that
none of the points are contained in the ball
. Consequently, as
,
we have , and therefore the barycentric coordinate vector
(w.r.t.
) of every
point in the fixed ball would converge to
(which is the barycentric coordinate vector
of the barycenter w.r.t. ); this proves our assertion.
D CONJECTURED OPTIMALITY OF UPPER BOUND THEOREM 3.2
It was conjectured by Mhaskar (1996) that there exists some smooth non-polynomial function ,
such that at least hidden units is required to uniformly approximate every function in the
class S of functions with bounded Sobolev norm. As evidence that this conjecture is true, a
heuristic argument was provided in (Mhaskar, 1996), which uses a result by DeVore 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 in Theorem 3.2 is optimal for general
continuous non-polynomial 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), it is known that the
minimum number N of hidden units required to uniformly approximate every function in S must
satisfy (Maiorov & Meir, 2000); cf. (Pinkus, 1999, Thm. 6.7). Hence there is
still a gap between the lower and upper bounds for N in these specific cases. It would be interesting
to find optimal bounds for these cases.