Universal Approximation with Deep Narrow Networks
Authors: Patrick Kidger
Terry Lyons
Venue:  (2020)
Keywords: deep learning
universal approximation
deep narrow networks

Abstract: The classical Universal Approximation Theorem certifies that the universal approximation property holds for the class of neural networks of arbitrary width. Here we consider the natural `dual' theorem for width-bounded networks of arbitrary depth. Precisely, let $n$ be the number of inputs neurons, $m$ be the number of output neurons, and let $\rho$ be any nonaffine continuous function, with a continuous nonzero derivative at some point. Then we show that the class of neural networks of arbitrary depth, width $n + m + 2$, and activation function $\rho$, exhibits the universal approximation property with respect to the uniform norm on compact subsets of $\mathbb{R}^n$. This covers every activation function possible to use in practice; in particular this includes polynomial activation functions, making this genuinely different to the classical case. We go on to consider extensions of this result. First we show an analogous result for a certain class of nowhere differentiable activation functions. Second we establish an analogous result for noncompact domains, by showing that deep narrow networks with the ReLU activation function exhibit the universal approximation property with respect to the $p$-norm on $\mathbb{R}^n$. Finally we show that width of only $n + m + 1$ suffices for `most' activation functions.

Under review as a conference paper at ICLR 2020
UNIVERSAL APPROXIMATION WITH DEEP NARROW NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
The classical Universal Approximation Theorem certifies that the universal ap- proximation property holds for the class of neural networks of arbitrary width. Here we consider the natural 'dual" theorem for width-bounded networks of arbi- trary depth. Precisely, let n be the number of inputs neurons, m be the number of output neurons, and let p be any nonaffine continuous function, with continuous nonzero derivative at some point. Then we show that the class of neural networks of arbitrary depth, width n n m + 2. and activation function p. exhibits the univer- sal approximation property with respect to the uniform norm on compact subsets of TR.". This covers every activation function possible to use in practice; in partie- ular this includes polynomial activation functions, making this genuinely different to the classical case. We go on to consider extensions show analogous result for certain class of nowhere differentiable activation functions. Second we establish an analogous result for noncompact domains, by showing that deep narrow networks with the ReLU activation function exhibit the universal approximation property with respect to the p-norm on R". Finally we show that width of only + suffices for "most' activation functions.
this result. First we
INTRODUCTION
The Universal Approximation Theorem (Cybenko 1989: Hornik 1991 Pinkus 1999) states that universal approximation holds for the class of neural networks with single hidden layer of arbitrary width, with any continuous nonpolynomial activation function:
Theorem 1.1. Let p: R T. be any continuous function. Let Ng. represent the class of neural networks with activation function p. with n neurons in the input layer, one neuron in the output layer, and one hidden layer with an arbitrary number neurons. Let K R." be compact. Then Nº is dense in (K)) if and only if p is nonpolynomial.
What if arbitrary width is replaced with arbitrary depth? Put more precisely, can networks of bounded width and arbitrary depth provide universal approximation? In some sense this poses question 'dual' to the problem answered by the classical Universal Approximation Theorem. We refer networks of this type as deep, narrow networks.
Furthermore we might ask how narrow the network may be, and what activation functions may be admitted. We provide a near-complete answer these various questions.
Universal approximation may be established with respect to more than one topology. Continuous activation functions beget networks representing continuous functions. Thus when working with respect to the uniform norm, it is natural to seek density in C(K; Rm)) for K C RR. When working with respect to the p-norm, it is natural to seek density in [PRRR: Rm) for p [1, (o). In this latter may hope to generalise to noncompact domains, functions in [ RT") must exhibit some sort of decay.
The primary motivation for this work stems from the work of Lu et al. (017)) who study this question in the special case of the popular ReLU activation function, and who establish density in L' (R"). The other notable result we aware of is the work of Hanin & Sellke (2017). who show another special case: they also consider the ReLU activation function, and establish density in C(K; Rm) for K C TR² compact.

---

Under review as a conference paper at ICLR 2020
This article demonstrates generalisations of these results, in particular to general activation fune- tions, without relying on the strong algebraic and analytic properties of the ReLU activation func- tion. This also improves certain results specific to the ReLU.
The rest the paper is laid out as follows. Section discusses existing work. Section provides brief summary of results; these are then presented in detail in Section 4. Section 5 is the conclusion. Several proofs are deferred to the appendices, due to length and technical content.
CONTEXT
Some positive results have been established showing that particular classes of networks are dense in certain spaces. Some negative results have also been established, showing that insufficiently wide networks will fail to be dense.
Hanin & Sellke (2017) have shown that deep narrow networks with the ReLU activation function exhibit the universal upproximation property in ((K:R)) for K IR" compact.
Lu et al. 20177) have shown that deep narrow networks with the ReLU activation function exhibit the universal approximation property in I (R*), whilst Lin & Jegelka (2018) have shown that particular description of residual networks, with the ReLU activation function, also exhibit the uni-
versal approximation property this space. We are not aware of any results for the general case of LP LRR RT) for p E [1, o.).
We do not know of any positive results applying to activation functions other than the ReI.U.
Regarding widths insufficient for a class of deep narrow networks to exhibit the universal approx- imation property, consider the case network with n input neurons and a single output neuron. For certain activation functions, (Johnson (2019) shows that width is insufficient give density in C(K). For the ReLU activation function, Lu et al. 2017)) show that width n is insufficient to give density in L' (R"), and that width 1 is insufficient in L' ([-1, [[=1, For the ReLU activation function, Hanin Sellke (2017) shows that width n is insufficient to give density in C(K), J and that in fact that this the greatest possible width not achieving universal approximation in this context.
The precise minimum width for activation functions other than ReLU, or for multiple output neu- rons, remains unknown.
Everything discussed so far is in the most general case of approximating functions on Euclidean space: in the language of machine learning, they are regression tasks. There has been some lated work in the special case of classification tasks, for example [eise et al. (2018); Szymanski & McCane (2012); Rojas (2003); Nguyen et al. (2018). There has also been some related work in the special case of certain finite domains; Le Roux & Bengio (2010) show that networks with sigmoid activation function and width n can approximate any distribution on {0, 1)" See also Sutskever & Hinton
(2008). Montúfar 2014) considers the analogous scenario for distributions on
{0, 10.......9
SUMMARY OF RESULTS
Definition 3.1. Let p: R I and n, m, k E N. Then let AVV M.,. represent the class of functions R" + R described by neural networks with neurons in the input layer, neurons in the output layer, neurons in each hidden layer, and an arbitrary number of hidden layers, such that every neuron in every hidden layer has activation function p. and every neuron in the output layer has the identity activation function.
Our central result is the following theorem.
Theorem 3.2. Let p: + R be any continuous function which is continuously differentiable at at least one point, with nonzero derivative at that point. Let K C RR" be compact. Then NN is dense in (K;R")).
The technical condition is very weak; in particular it is satisfied by every piecewise-C C function not identically zero. Thus any activation function that one might practically imagine using on a computer must satisfy this property.
2

---

Under review as a conference paper at ICLR 2020
Theorem 3.2 is proved by handling particular classes of activation functions special cases. First we have the result for nonpolynomial activation functions, for which the width can be made slightly smaller.
Theorem 4.4. Let R + I. be any continuous nonpolynomial fanction which is continuously differentiable at at leust one point, with nonzero derivative that point. Let K R be compact. Then NNP, m.m.am+11 is dense in C(;:
We observe a corollary for noncompact domains, which generalises Lu et al. 2011 Theorem 1) to multiple output neurons, narrower width, and IP for p 2 instead just p
Corollary 4.6. Let p be the ReLU activation function. Let p E [1, Then ANP m.mm+ dense in L (IR"; ).
Moving on to polynomial activation functions, the smaller width of + m also suffices for large class of polynomials.
Theorem 4.8. Let p: IR + R be any polynomial for which there exists point a E R such that p((a) = 0 and (a) & O. Let K C R" be compact. Then NN n.m.n4m41 is dense in C(K; R").
The simplest example of such a p is x²2 Note that the classical arbitrary-width case it is both necessary and sufficient that the activation function be nonpolynomial. Here, however, the same restriction does not hold. Polynomial activation functions are reasonable choice in this context.
The technical restrictions the polynomial may be lifted by allowing the full + m + 2 neurons per hidden layer.
Theorem 4.10. Let p: R R be any nonaffine polynomial. Let S R be compact. Then NNP tmm is dense in CR::
is clear that Theorems 4.4 and 4.10 together imply Theorem 3.2
Finally observe that even pathological cases not satisfying the technical condition of Theorem 3.2 may exhibit the universal approximation property.
Proposition 4.13. Let w: R + be any bounded continuous nowhere differentiable function.
p(x) = sin(x) + w(x)e=z which will also be nowhere differentiable. Let K C IR be compact. Then NNP n,m.n+m+1 dense in C(KK
Whilst not of direct practical application, this result exemplifies that little necessarily needs to be assumed about an activation function to understand the corresponding class of neural networks.
Remark 3.3. Every proof in this article is constructive, and can in principle be traced so as to deter- mine how depth changes with approximation error. We have instead chosen focus on quantifying the width necessary for universal approximation. In fact there are places in our arguments where we have used deeper network over shallower one, when the deeper network is more easily explained.
Remark 3.4. An understanding of universal approximation in deep narrow networks is applicable to an understanding of bottlenecks, when information must be discarded due to space constraints, for example in autoencoders (Bengio al. (006). This article demonstrates that certain narrow networks will not constitute a bottleneck; a converse example is Johnson (2019), who demonstrates that networks of insufficient width are forced maintain certain topological invariants.
UNIVERSAL APPROXIMATION
4.1 PRELIMINARIES
Remark 4.1. A neuron is usually defined as an activation function composed with an affine function. For ease, we shall extend the definition of a neuron to allow it to represent a function of the form t po σ, where v and é are affine functions, and p is the activation function. This does not increase the representational power of the network, as the new affine functions may be absorbed into the affine parts of the next layer, but will make the neural representation of many functions easier to present. We refer to these as enhanced neurons. is similarly allowable to take affine combinations of multiple enhanced neurons; will use this fact as well.
3

---

Under review as a conference paper at ICLR 2020
One of the key ideas behind our constructions is that most reasonable activation functions can be taken to approximate the identity function. Indeed, this is essentially the notion that differentiability captures: that a function is locally affine. This makes it possible to treat neurons which information may be stored and preserved through the layers. This allows for preserving the input values between layers, which is crucial to performing computations in memory- memory-bounded regime. Thus our constructions have strong overtones of space-limited algorithm design in tradi- tional computer science settings.
'registers', in
Lemma 4.2. Let p: R - RR be any continuous function which is continuously differentiable at at least one point, with nonzero derivative at that point. Let L S be compact. Then a single enhanced neuron with activation function may uniformly approximate the identity function v: IR + R. on L, with arbitrarily small error.
Proof. By assumption, as p is continuously differentiable, there exists (a, b] S R with o b, on some neighbourhood of which p is differentiable, and a E (a, b) at which pf is continuous, and for which p' (a) is nonzero.
For RR {0}, let (x) = hæ + a, and let
(x) I p(a)
(p)(aa)
Then
th oo Φn of the form that an enhanced neuron can represent. Then for all E [a, 6). by the Mean Value Theorem there exists Eu between u and a such that
p(u) = p(a) + (u a))
and hence
(x(x) (whn o oo Φn)(z) th (p(a) + (Enz+a)
xpp (Ehorta))
((aa)
for h sufficiently small that o). S [a, b).
Now let p' have modulus of continuity w on [a, b). Let R + R represent the identity function. Then for all E L,
p' (Ehota)) d(aa)
(xx(x) - ((x)))((x)1-- x
p'(a)
x (a)) w(xx),
and 4n + & uniformly over L.
Notation. Throughout the rest of this paper 4, will be used to denote such an approximation to the identity function, where 4s + uniformly as h + 0.
An enhnaced neuron may be described performing (for example) the computation - en (4x++3). This is possible as the affine transformation z + 4r and the affine transformation Φn (from the description of (x) may be combined together into single affine transformation.
4.2 NONPOLYNOMIAL ACTIVATION FUNCTIONS
We consider the 'Register Model', which represents a simplification of a neural network.
Proposition 4.3 (Register Model), Let p: R + R. be any continuous nonpolynomial function. Let IP mmmmxt+m11 represent the class of neural networks with n neurons in the input layer, m neurons in the output layer, n + m + neurons in each hidden layer, an arbitrary number of hidden layers, and for which n m of the neurons in each hidden layer have the identity activation function, and one neuron in each hidden layer has activation function p. Let K C B." be compact. Then IP m.m.n
dense in C (K; m)
4

---

Under review as a conference paper at ICLR 2020
Ej=1 0j
M-1 Σ j=l Oj
201
202
Zn
оM
a
21
2/2
In
03
03(#))...)
01 02
21
2/2
En
02 = 02(1),...,
01
21 22
In σ1 01 01
21
22
Zn
Figure I: simple example of how to prove the Register Model. The values P are inputs the network, and the value 2}=1 is the output. Each cell represents one neuron. Each æ; is of the form 4/s e p Pi. where t and Φi are affine functions and p is the activation function.
See Appendix for the proof.
A simplified depiction of the proof of the Register Model is shown in Figure | for the special case of It uses n neurons in each layer registers preserve the input values. A single neuron in each layer performs a computation based off of the input values, which were preserved in the previous layer. The remaining neuron in each layer also acts register, gradually summing up the results of the computation neurons. The computation neurons may be shown to exist by the classical Universal Approximation Theorem.
The Register Model is similar to Hanin & Sellke (2017), who have related construction specific to the ReLU. The idea of the Register Model may also be thought of thematically similar to residual networks, in Lin & Jegelka (2018): in both cases the network is almost applying the identity transformation at each layer, with only a small amount of nonlinearity.
Theorem 4.4. Let R I be any continuous nonpolynomial function which is continuously differentiable at at least one point, with nonzero derivative at that point. Let K C R be compact. Then NN m.m.a++111 is dense in C(K:R")
Proof. Let C(K;I")) and 0. Set up neural network in the Register Model (Proposition 4.3
approximating f to within e/2. Every neuron requiring an identity activation function in the Register Model will instead approximate the identity, in the manner of Lemma 4.2
Uniform continuity preserves uniform convergence, compactness is preserved by continuous func- tions, and composition of two uniformly convergent sequences of functions with uniformly contin- uous limits is again uniformly convergent. So as neural network is layer-by-laye composition of functions then the new model can be taken within e/2 of the Register Model, with respect ||- l in K, by taking h sufficiently small.
Remark 4.5, This of course implics approximation (P(KRR") for E [1, oo). However, when p is the ReLU activation function, then the next corollary shows that in fact the result may be generalised to unbounded domains.
Corollary 4.6. Let be the ReLU activation functtio.. Let p E [o). Then NNo dense in L ".).
m+m.4++41 is
See Appendix for the proof.
Given some f E TP(R"; RR", the essential idea of the proof is to choose compact set K C T on which places most of its mass, and find neural approximation to f on K in the manner of Theorem 4.4 Once this is done, cut-off function is applied outside the set, that the network takes the value zero in _ K. The interesting bit finding a neural representation of such cut-off behaviour.
In particular the 'obvious' thing to do multiply by a cut-off function does not appear to have suitable neural representation, merely approximating the multiplication operation is not neces- sarily enough on an unbounded domain. Instead the strategy to take a maximum and a minimum with suitable cut-off functions.
5

---

Under review as a conference paper at ICLR 2020
4.3 POLYNOMIAL ACTIVATION FUNCTIONS
For the classical Universal Approximation Theorem, it was necessary that the activation function be nonpolynomial. However that turns out be unnecessary here; deep narrow networks different to shallow wide networks, and polynomial activations functions are reasonable choices.
We begin with the simplest possible nonaffine polynomial, namely p(z) x².
Proposition 4.7 (Square Model). Let p(x) = x². Let K S I2" be compact. Then NN a.m.nm++1 is dense in (K;
See Appendix Mone--Wiiesstrae theorem, reducing the problem to the approximation of arbitrary polynomials.
C for the proof. As might be expected, density is established with the help of the
We remark that it is actually straightforward to find construction showing that AN n.m, n.m.n+442 is dense in C(K; RT) when p(z) x², note the increased width. This is because the square activation function can be used to perform multiplication, via ay = ((x + y)² - (x - y) 2)) 1/4, and this makes it easy to construct arbitrary polynomials. In fact this is what is done in the proof of Proposition 1oopositionn4.]foo f.r finding m - of the m outputs, when there is still 'spare' neuron in each layer. It is computing the final output that actually requires the bulk of the work. The key to this argument a width-efficient approximation to division.
It is a consequence of Proposition 4.7 that any (polynomial) activation function which can approxi- mate the square activation function, in suitable manner, is also capable of universal approximation.
Theorem 4.8. Let p: R + IR be any polynomial for which there exists a point a E R such that p((a) 00 and p" (a) & Let K R.n be compuct. Then NN mmm is dense in C(K; R
Proof. Leth E R \ (0). Define Ph: R + by
(x) plax + hX) - p(a)
122 (2x)2
Then, taking a Taylor explansion around a, pr p(() + happ' + h²222p" (a))2 0(h'=))))))))---)))))))))))))))) p(a)
h²)
x²2 + (1r2)).
Let s(x) = _22 Then Ph. + uniformly over any compact set as h +
Now set up network as in the Square Model (Proposition 4.7) with every neuron using the square activation function. Call this network N. Create a network N₁, by copying N and giving every neuron in the network the activation function Pk instead.
Uniform continuity preserves uniform convergence, compactness is preserved by continuous func- tions, and composition of two uniformly convergent sequences of functions with uniformly tinuous limits is again uniformly convergent. So as a neural network a sayer-by-layee composition of functions, then the difference between N and NA. with respect to ||- lla on K, may be taken arbitrarily small by taking h arbitrarily small.
Furthermore note that Ph is just P pre- and post-composed with affine functions. (Note that there is only one term in the definition of (x( which depends on x.) This means that any network which may be represented with activation function pn may be precisely represented with activation function p. by combining the affine transformations involved.
Remark 4.9. That is polynomial is never really used the proof of Theorem 4.8 Only a certain amount of differentiability is required, and all such nonpolynomial functions are already covered by Theorem as nonzero second derivative at a implies a nonzero first derivative somewhere close to a. Nonetheless in principle this provides another possible construction by which certain networks may be shown to exhibit universal approximation.
Note that the converse strategy (applying nonpolynomial techniques to the polynomial case) fails. This is because the Register Model requires nonpolynomial activation functions due to its depen- dence the classical Universal Approximation Theorem.

---

Under review as a conference paper at ICLR 2020
(1)))²
(2(n)
O (7))
Expand
01,n+m+1 ((t))
02,++++1 = (((22n+m)
01,2 =((x1,1)
02,2
(Ax2,1)
0m+++1122 +0+++++1111)
01,1 = (1 (n)
0221
(2(11)
0m44++1,11 4n+m (1)
Figure 2: A layer with square activation functions is equivalent to multiple layers with only single square activation function in each layer. The other neurons use the identity activation function, denoted
Theorem 4.10. Let p: I Th be any nonaffine polynomial. Let K C RD be compact. Then N tmm22 is dense in C(;;
Proof. Fix a IR such that p (a) + 0, which exists p is nonaffine. Now let h (0, oo). Define Th: + by
(x)) = p(a + hx) 2p(a) + p(ac - hx)
h22 h²pp (a)
Then Taylor expanding p(a= + ha)) and p(a hr) around a,
(x) p(a) + hap' (a) + (aa)22(2)
2p(a) h²p"(a))
(a)
p(a) (a)
h2
=x² + O(ha)).
Observe that σn needs precisely two operations of p (affine transformations of) x, and may be computed by two enhanced neurons with activation function p. Thus the operation of a single enhanced neuron with square activation function may be approximated by enhanced neurons with activation function p.
Let N be network as the Square Model (Proposition 4.7 with every neuron using the square activation function. Let é be any hidden layer of N; it contains n++ m++1 neurons. Let 7) be a vector of the values of the neurons of previous layer. Let di the affine part of the ith neuron that & computes Φ1 (1)².... ..... @n+m+1 (1)) Then this may equivalently be calculated with + m + layers + m + neurons each, with n + m identity function, and one neuron using the square activation function. The first of these new layers applics the di, and the ith layer squares the value of the ith neuron. See Figure 2
so
neurons each these new layers using the
Apply this procedure to every layer of N: call the resulting network Ñ. It will compute exactly the same function N, and will have + + 1 times as many layers, but will only single squaring operation in each layer.
Create copy of Ñ, call it Ng. Replace its identity activation functions with approximations in the manner Lemma 4.2 using activation function p. Replace its square activation functions (one in each layer) by approximations in the manner described above with a this requires an extra neuron in each hidden layer, that the network is now of width function throughout.
+ 2. Thus N₂, uses the activation
Uniform continuity preserves uniform convergence, compactness is preserved by continuous func- tions, and a composition of two uniformly convergent sequences of functions with uniformly con- tinuous limits is again uniformly convergent. So a neural network is layer-by-layer composition

---

Under review as a conference paper at ICLR 2020
of functions, then the difference between Nr, and N, with respect to || on K, may be taken arbitrarily small by taking arbitrarily small.
possible to construct shallower networks analogous to N. The proof Propo- sition 4.7 in Appendix [ uses most of the network's neurons to approximate the identity anyway; only a few in each layer are used to square valued that is desired to be squared. These are the only neurons that actually require the procedure used in Figure and the proof of Theorem 4.10
Remark 4.11.
4.4 NONDIFFERENTIABLE ACTIVATION FUNCTIONS
Although not of direct practical application, results for nondifferentiable activation functions demon- strate how certain pathological cases are still capable of being handled.
Lemma 4.12. Let w: + be any bounded continuous nowhere differentiable function. Let
p(z) sin(x) + w(x)e==. Let L S R be compact. Then a single enhanced neuron with activation function may uniformly approximate the identity function L: - R on L, with arbitrarily small error.
Proof. For h E (R and A E 2xN, let (x) ha + and let vxx)) x/h. Let
4r.4 = tn o $h.A,
which is of the form that an enhanced neuron can represent. Then jointly taking h small enough and A large enough it is clear that 4 may be taken uniformly close to on L.
Proposition 4.13. Let w: R + be any bounded continuous nowhere differentiable function. Let p(x) sin(x) + w(x)e=, which will also be nowhere differentiable. Let K C IR" be compact. Then NN n.m.1+++1 dense in ).:
Proof. As the proof of Theorem 4.4. except substituting Lemma 4.12 for Lemma 4.2
This manner of proof may be extended other nondifferentiable activation functions well.
CONCLUSION
There is large literature on theoretical properties of neural networks, but much it deals only with the ReLU However how to select an activation function remains poorly understood topic, and many other options have been proposed: leaky ReL.U, PReLU, RRelu, ELU, SELU and other more exotic activation functions well
Our central contribution is to provide results for universal approximation using general activation functions (Theorems 3.2 4.8 and 1.). In contrast to previous work, these results do not rely on the nice properties the ReLU, and in particular do not rely on its explicit description. The techniques we nondifferentiable activation functions (Proposition 4.13).
straightforward, and robust enough to handle even the pathological case of
We also consider approximation in I.P norm (Remark 4.5). and generalise previous work to smaller widths, multiple output neurons, and p > in place of p = (Corollary44.6)
In contrast much previous work, every result show also handles the general case of multiple output neurons.
ACKNOWLEDGEMENTS
(Redacted from anonymised submission)
'See for example Hanin & Sellke 2017)
Petersen Voigtlaender 2018): Gühring Daubechies al.
2019: Arora et (2018).
'See Maas et al. (2013 He et al. 2015
: Xu al.
2015
Clevert al. 2016 Klambauer et al.
2017)
Molina al. (2019)
Krizhevsky 2012 respectively.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding Deep Neural Networks with Rec- tified Linear Units. International Conference on Learning Representations, 2018.
H.-P. Beise, S. D. Da Cruz, and U. Schröder. On decision regions of narrow deep neural networks. CoRR, arXiv: 011.7.11944 2018.
Y. Bengio, Lamblin, D. Popovici, and H. Larochelle. Greedy layer-wise training of deep networks. In Proceedings of the 19th International Conference on Neural Information Processing Systems, NIPS'06, 06, pp. 153-160, Cambridge, MA, USA, 2006. MIT Press.
D.-. Clevert, Unterthiner, and S. Hochreiter. Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs). In International Conference on Learning Representations, 2016.
G. Cybenko. Approximation by superpositions of sigmoidal function. Math. Control Signals Syst., 2(4):303-314, 1989.
I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova. Nonlinear Approximation and (Deep) ReLU Networks, arXiv: 1905.02199 2019.
Gühring, G. Kutyniok, and P. Petersen. Error bounds for approximations with deep ReLU neural networks in W*P norms. Proceedings of the AMS. In press.
B. Hanin and M. Sellke. Approximating Continuous Functions by ReLU Nets of Minimal Width. arXiv: 1700.1 1278, 2017.
K. He, X. Zhang, S. Ren, and J. Sun. Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification. In Proceedings of the 2015 IEEE International Confer- ence Computer Vision (ICCV), ICCV "15, pp. 1026-1034, Washington, DC, USA, 2015. IEEE Computer Society.
K. Hornik. Approximation capabilities of multilayer feedforward networks. Neural Netw., 4(2): 251-257, 1991.
Johnson. Deep, Skinny Neural Networks are not Universal Approximators. In International Conference on Learning Representations, 2019.
G. Klambauer, T. Unterthiner, A. Mayr, and S. Hochreiter. Self-normalizing neural networks. In Advances in Neural Information Processing Systems 30, pp. 971-98911 Curran Associates, Inc., 2017.
A. Krizhevsky. Convolutional Deep Belief Networks on CIFAR-10. 2012.
N. Le Roux and Y. Bengio. Deep Belief Networks are Compact Universal Approximators, Neural Comput., 22(8):2192 2207,2207200 2010.
H. Lin and Jegelka. ResNet with one-neuron hidden layers is a Universal Approximator. In Advances in Neural Information Processing Systems 31, pp. 6169-6178. Curran Associates, Inc., 2018.
Z. Lu, H. Pu, F. Wang, Z. Hu, and L. Wang. The Expressive Power of Neural Networks: A View from the Width. In Advances Neural Information Processing Systems 30, pp. 6231-6239. Curran Associates, Inc., 2017.
A. Maas, A. Hannun, and A. Ng. Rectifier Nonlinearities Improve Neural Network Acoustic Models. In International Conference on Learning Representations, 2013.
A. Molina, P. Schramowski, and K. Kersting. Padé Activation Units: End-to-end Learning of Flexi- ble Activation Functions Deep Networks. arXiv:1907.0677. 2019.
G. Montúfar. Universal Approximation Depth and Errors of Narrow Belief Networks with Dis- crete Units. Neural Compur., 1377))1886110000 2014. ISSN 0899-7667.

---

Under review as a conference paper at ICLR 2020
Q. Nguyen, M. C. Mukkamala, and M. Hein. Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions. Proceedings of the 35th International Conference on Machine Learning. PMLR 80, Stockholm, Sweden, 2018.
Petersen and F. Voigtlaender. Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Netw, 108:296-330, 2018.
A. Pinkus. Approximation theory of the MLP model in neural networks. Acta Numer, 8:143-195, 1999.
R. Rojas. Networks of width one are universal classifiers. In Proceedings of the International Joint Conference Neural Networks, volume 4, pp. 3124-3127, 2003.
I. Sutskever and G. E. Hinton. Deep, Narrow Sigmoid Belief Networks Are Universal Approxi- mators. Neural Comput., 20(1 20(11):2629-2633 2008. ISSN 0899-7667. doi: 10.1162/neco.2008 12-07-661.
Szymanski and B. McCane. Deep, super-narrow neural network universal classifier. In The 2012 International Joint Conference on Neural Networks (IJCNN) 1-8, 2012.
B. Xu, N. Wang, T. Chen, and M. Li. Empirical Evaluation of Rectified Activations in Convolutional Network. arXiv:1505.00853 2015.
10

---

Under review as a conference paper at ICLR 2020
A PROOF OF THE REGISTER MODEL (PROPOSITION 4.3
First, we recall the classical Universal Approximation Theorem Pinkus 1999):
Theorem 1.1. Let p: R + IR be any continuous function. Let N represent the class of neural networks with activation function p. with n. neurons in the input layer, one neuron in the output layer, and one hidden layer with an arbitrary number of neurons. Let K C RR" be compact. Then Ng is dense in (() if and only if p is nonpolynomial.
The Register Model is created by suitably reorganising the neurons from a collection of such shallow networks.
Proposition 4.3 (Register Model), Let pt R + R be any continuous nonpolynomial function. Let To m.. represent the class of neural networks with n neurons in the input layer: neurons in the outpur layer, n + m++ + neurons in each hidden layer, an arbitrary number of hidden layers, and for which m. of the neurons in each hidden layer have the identity activation function, and one neuron each hidden layer has activation centvaatiofuunttiio function p. Let K C TR. be compact. Then IP m.m.n+++1
dense in C(;
Proof. Fix f E C(K;R"), (J Fix 0. By Theorem 1.1 there exist single- hidden-layer neural networks :1.-...9m E EN with activation function approximating f1.-..,Ja respectively. Each approximation to within error e with respect - on K. Let each gi have 3 hidden neurons. Let Ji represent the operation of its jth hidden neuron, for j E {I, J. J. In keeping with the idea of enhanced neurons, let each oi include the affine function that comes after it in the output layer of so that = Σラ= Ozj. Let M Ei=1 8,
We seek to construct neural network N E T -mm Given input (fI,..., E R", it will output (Gi,..., Gm) E R" such that G2 (Z In) for each i. That is, it will compute all of the shallow networks g1..... 9m. Thus it will approximate f to within error e with respect to -I- Il on K.
The construction of N is mostly easily expressed pictorially: see Figure In each cell, representing neuron, we define its value function of the values of the neurons in the previous layer. In every layer, all but one of the neurons uses the identity activation function :: + I, whilst one neuron in each layer performs computation of the form oij-
The construction can be summed up as follows.
Each layer has and a group of m neurons.
+ neurons, arranged into group of n neurons, group of single neuron,
The first neurons in each layer simply record the input (æ) (æ1..... J,,), by applying identity activation function. We refer to these as the 'in-register neurons'
Next consider 01....-9u. which all shallow networks. The neurons in the hidden layers of gI..... 9m are arranged 'vertically' in our deep network, one in each layer. This is the neuron in each layer that uses the activation function p. We refer to these as the 'computation neurons". Each computation neuron performs its computation based off of the inputs preserved in the in-register neurons.
The final group of m neurons also use the identity activation function; their affine parts gradually sum up the results of the computation neurons. We refer these the 'out-register neurons'. The ith out-register neuron in each layer will sum up the results of the computation neurons computing oij for all E (1.....3.}
Finally, the neurons in the output layer of the network are connected to the out-register neurons of the final hidden layer. As each of the neurons in the output layer has, as usual, the identity activation function, they will now have computed the desired results.
11

---

Under review as a conference paper at ICLR 2020
Figure The thick lines delimit groups of layers; the ith group computes di,1.... Gis. The inputs to the network are 2i, #1,.... Tn. depicted at the bottom. The
G Sm 5m. M
4 M-1 TM-1)
Sm 1(Cm, + TM--))
0
Sm, 0
Gm. 0
Sm.th =
Cm. +i +
Goally 1a
Gouuh +2
Co
Cn,
Cn.
Tay +09+00-111
4 12)
(2,31 = ((7
Ga Co M
1((a,Mr9)
6a,/1 =0
Ca. = 0
Ca.2 = 0
Ca.1 =
ca.4
C2.M
12
C2,8 +
outputs from the network are G1 1. Gm. depicted the top. The identity activation function IR - R is demoted
((C1. 1 ())=1)
G1 S1.M
((G)M-1)
G1M--1
((G1,M-9)
((C.0011)
(G1.9 +.y))
$1 161. + mg)
6,3 = dC1, (2)
S12 =
611==
G.
02.82 (1.2)) +22 190 Th. A
+2143 = 02.3(11.8 42.. (7.,8) +2)
1P142 = d2.a(11.3 41w. (1.81+1)
73, 01.01 (11.3) -1... 1m.8 -1
mm. Am (2) AM -1. 11:.---....... (0.3--1)
0m,2m 11n-pmm1(1aa (11.3 M 2 Ph.M-
r0 = (2.1 .... (
Ta 1. 1....--77m. (h..))
7s = 01..a1.......................... .m.2)
=1 (m..1)
7Wss 1o....
TM-1
dhtea ( +-22-1
Tm,M 0
Thu M-1 = 10 M-2)
7a. = 4(20,00
7h..9 +- =
d(7m, +11)
7r.9 =
A(Tm.99-1 -1)
7w.4 A(Tn.a)
((Tmw 2)
Tn. =
Tr.3
7e.1 ((2,,)
d'22,8 +
72, = 0
2g PP. = M22)
72,8 =
177.09 +2)
72.8 +2. =
177 +11
72 00.81. +-1 = (
92.8 A(72,4111 -1)
((2.5)
79.2 = d/2.
72.01 1:0g
79.4
72.1
7t.M = 0
21,M1 = ((11M-2)
71,0 =
71.01+2 =
< <0.,0 +1)
24.4, ((LAA-1)
74.9
21.4 ((ma))
21.8
(mm)) .)
71.3 = ((
71.1 =
((m)
71.93
12

---

Under review as a conference paper at ICLR 2020
B PROOF OF COROLLARY 4.6
Lemma B.1. Let a, b, c. d E R be such that a < < c d. Let Ua.b...:: R + R be the unique continuous piecewise affine function which is one on [b, c] and zero on (-oo, a) U 00). Then two layers of two enhanced neurons each, with ReLU activation function, may exactly represent the function U U.b.
Proof. Let IR be the imput. Let m1 1/(b - a). Let m2 1/(d c).. Let mı 72 represent the first neuron in each layer, and S1 S2 represent the second neuron in each layer. We assign them values as follows.
V1 max (0, m1 m1 a)}:
C1 max (0, m2( -
1/2 (0, 1
C ma (i).
Then a = 1/2 (This final affine transformation is allowed, in keeping with the notion
of enhanced neurons.)
Lemma B.2. One layer of two enhanced neurons, with ReLU activation function, may exactly rep- resent the function (z. v) + min x. y} [0, oc)?
Proof. Let the first neuron compute n max(0, - y}. Let the second neuron compute ma z). Then (i, y} = 77.
Corollary 4.6. Let p be the ReLU activation function. Let p E (0)) Then AN dense in L LPR"; ).
Proof. Let f E LP(R"; R") and O. For simplicity assume that 1.th is endowed with the l| lloe norm; other norms are of course equivalent. Let f (fr....,Ff) E Co 12TT be such that
|| - < e/3.
(B.1)
Let
C = sup max Já(x:) +
(B.2)
zER
and
inf min fe(x)) zek
(B.3)
Pick a1, b,, .i....,a an 6n R such that J defined by
J= J= bj] ... x Jan, bn]
is such that supp f C J. Furthermore, for 5 > 0 that we shall fix in moment, let
A 0; B. = b; + 5,
and let K be defined by Fix 5 small enough that
K = [1,, x ... x [An, Bn).
K J/ max (IC), |c])
(B.4)
Let (g), ..., gm) E N N.N mm be such that
sup mek
f(x) g(xo) < min
8 3/
1
(B.5)
13

---

Under review as a conference paper at ICLR 2020
which exists by Theorem 4.4 Note that g is defined on all of R"; it simply happens to be close to on K. In particular will takes values close zero on K \ J, and may take arbitrary values in Rn K. By equations B.2 (B.3) (B.5), it is the case that
C sup max (z)) øeK
< inf min (x). #EK i
(B.6)
Now consider the network describing gi it will be modified slightly. The goal is to create network which takes value on J, zero in R" K, and moves between these values in the interface region
K' K'J. Such a network will provide suitable approximation to f. This is done by first constructing function which approximately the indicator function for J. with support in K; call such a function U. The idea then is construct neural representation of G2 defined by
G; min (max cU), CU).
Provided |K] J/ is small enough then G (G1. ..... Gm) will be the desired approximation; this is proved this below.
We move presenting the neural representation of this construction.
First we observe that because the activation function is the ReLU, then the identity approximations used in the proof of Theorem[4.4]]
in fact exactly represent the identity function some compact set: x + max + N N' is exactly the identity function, for suitably large N, and is of the form that enhanced neuron may represent. This observation isn't strictly necessary for the proof, but it does simplify the presentation somewhat, as the values preserved in the in-register neurons of g are now exactly the inputs x (Z1...., I.)) for x E K. For sufficiently negative Iı, outside of K, they will take the value -N instead, but by insisting that is N sufficiently large that
-N < A for all i, then this will not be an issue for the proof.
(B.7)
So take the network representing g. and remove the output layer. (If the output layer is performing any affine transformations then treat them as being part of the final hidden layer, in the manner of enhanced neurons. Thus the output layer that is being removed is just applying the identity functionn to the out-register neurons.) Some more hidden layers will be placed on top, and then new output layer will be placed on top. In the following description, all neurons not otherwise specified will be performing the identity function, preceding layer. As all functions involved are continuous and is compact, and compactness is preserved by continuous functions, and continuous functions are bounded on compact sets, then this is possible for all x E K by taking N large enough.
to preserve the values of the corresponding neurons in the
The first task is to modify the value stored in the in-register neurons corresponding to ø1- At present stores the value 21; by using this in-register neuron and the computation neuron in two extra layers, its value may be replaced with U ,h. B, (I1), via Lemma B.1 Place another layers on top, and use them to replace the value of 22 in the second in-register neuron with U UAg.0z,2,,B, (I2), and so on. The in-register neurons now store the values (U (UA1.e1.b..B (z1),..., U Unnambd... (zn)).
Once this is complete, place another layer on top and use the first two in-register neurons compute the minimum of their values, in the manner of Lemma B.2 thus computing min(UA, Aa,,,,,,,,,,,. ,, B, (I1), ), U2y,oy,b, ba, (I2)}. Place another layer on top and use another two in- register neurons compute the minimum of this value and the value presently stored in the third in-register neuron, that is UA bs, Bs (I3). so that
min(UA,, dn B, (a1), UA (x2), ( B,,
has now been computed. Continue to repeat this process until the in-register neurons have com- puted
U min UA
iE [)
It doesn't matter which of the in-register neurons records the value of U.
14

---

Under review as a conference paper at ICLR 2020
Observe how U represents approximation to the indicator function for J, with support in K, evaluated at (I1,..., Tx).
This is highly destructive set of operations: the network no longer remembers the values of its inputs. Thankfully, no longer needs them. Note how the small foible regarding how an in-register neuron would only record -N instead of Ts, for 24 - N, is not issue. This is because of equation (B.7). which implies that U A,,ar,,,,B (T:) = 0 = U UA,ar, (-N), thus leaving the value of U unaffected.
The out-register neurons presently store the values 91...., 9m. where 9i = add another layer. Let the value of its out-register neurons be 01,-.. On, where
Now
0: 00 9: c./).
Add one more hidden layer. Let the value of its out-register neurons be Ai...., Ams where
A = max - 0, + (C - c.
Finally place the output layer on top. Let the value of neurons be Gi,..., Gms where
G3 - CU.
Then in fact
G, = min cU CU}
(B.8)
as desired.
All that remains to show is that G = (G1.... Gm) of this form is indeed suitable approximation. First, as G and g coincide in J, and by equation [35
1/8
(,, G(w)) dx
<
|
// sup
f(x) G(z)
|//4/P
sup
f(x)) g(x))
(B.9)
Secondly, by equations (B.2).
(B.3..
B.6
B.8)
and then equation (B.4)
1/p
(m)
G(o)| G(o) dx
K
1/p sup
f(x) G(a)
kE J
K
|| 1/p 2 max (1C), |cl
(B.10)
3
Thirdly,
1/8
(ErA (f(x)-
dr =0,
(B.11)
as both and G have support K.
So by equations B
B.9
B. 1.10
and B.I.).
|f GI, <
F
+ (Lf
f(x) - G(x) dx
1/p
p
E
+
3
3
E.
15

---

Under review as a conference paper at ICLR 2020
C PROOF OF THE SQUARE MODEL (PROPOSITION 4.7)
Lemma C.1. One layer of two enhanced neurons, with square activation function, may exactly represent the multiplication function (2,y) + xy on I2?
Proof. Let the first neuron compute (x+ Let the second neuron compute Ç (= (xr (xz-y) u)² /4.
Then zy Ç.
Lemma C.2. Fix L S. IR2 compact. Three layers of two enhanced neurons each, with square activation function, may uniformly approximate (I, y) + (x², y( + 1)) arbitrarily well on L.
Proof. Let h E R {0}. Let hh 72, 7s represent the first neuron in each layer; let Çi, S2, Ca represent the second neuron in each layer. Let 4 represent approximation to the identity in the manner of Lemma 4.2 Using 's' as an informal notation to represent 'equal to up to the use of on in place c', just help keep track of why we performing these operations, assign values to Th T2. 773 and S1, S2. S3 as follows:
1/2 4 (x)
2 = (a + sy + +1²
= x² + +ssry + s²1²² + 2x + 2sy + 1,
2 x,
(m)
22 = un(Si - 2m 1]
~ x²
~ x² + 2sry + 2²2 + 2sy,
13 1/ (12)
C3 in (Ce 1122 /28)
2 x²
= ry + y + sy" 12.
And so i7s may be taken arbitrarily close to x² and {3 may be taken arbitrarily close to y(x++) with respect to || oc on L, by first taking s arbitrarily small, and then taking h arbitrarily small. N
Proposition C.3. Fix L S (0,2) compact. Then multiple layers of two enhanced neurons each, with square activation function, may uniformly approximate x + 1/x arbitrarily well on L.
(Unlike Lemma
C.2 the number of layers necessary will depend on the quality of approximation.
Proof. First note that
II + 2²')
1
1-x
t=0
as 0o, uniformly over compact subsets of (-1, 1). Thus,
(2 x) II + (1- 2) = II (1 + (1 - (1-))))) 1
1=1
==
uniformly over L.
This has the following neural approximation: let =1- and (i = (2 x)) be the neurons in
the first layer, where 4n is some approximation of the identity as in Lemma 4.2 Let Ką, represent an approximation to (xx y) + (z² y(r + 1)) in the manner of Lemma C.2 with error made arbitrarily ,.....,..
small as h + O. Now for i E [1, 7, 10...., 3n - 2}. recursively define (π++3, Gi+a) = (1): Ct), where we increase the index by three to represent the fact that three layers are used to perform this operation. So up to approximation, 7/43 s (n:)², and Gi+3 R (1)): + 1).
So Can+1 - (2 x:) (1 (1 )) uniformly by taking first n large enough and then h small enough.
I. h + 0. Thus the result is obtained
Remark C.4. Our approach to Proposition the reciprocal function, and then represent that with network of multiple layers of two neurons each. is fortunate, then, that this polynomial happens to be of a form that may be represented by such network, as is not clear that this should necessarily be the case for all polynomials. Even
C is to find a suitable polynomial approximation of
16

---

a.m.nt++1 is Under review as a conference paper at ICLR 2020
if Proposition 4.7 were already known, it requires a network of width three to represent arbitrary polynomials R + R. whereas Proposition C.3 uses a network of only width two. It remains unclear
whether arbitrary-deple network of width two, with square activation function, is capable of universal approximation in C(K).
Proposition 4.7 (Square Model). Let p(x) = x². Let K S R" be compact. Then NN dense in I.))
Proof. Fix f E C(K;R")) Let f = (Ji...., fm). Fix & > 0. By precomposing with an affine function which may be absorbed into the first layer of the network assume without loss of generality that
K S (1,2)*
(C.1)
By the Weierstsssss theorem there exist polynomials 91....,9m Im in 21, In approximating f to within s/3 with respect to || Il
We will construct network that evaluates arbitrarily good approximations to 91..... In- There are a total of n + m + 1 neurons in each layer; group them as the proof of the Register Model (Proposition 4.3 see Appendix A so that in each layer there is group of n neurons that refer to as 'in-register neurons', a single neuron that we refer to as the "computation neuron', and a group of m neurons that we refer to the 'out-register neurons'.
As before, every in-register neuron will simply apply an approximate identity function to the corre- sponding in-register neuron in the previous layer, so that they preserve the inputs to the network, up to an arbitrarily good approximation of the identity. (For now, at least later, when constructing the approximation to gl, which will be the final approximation that is handled, then these neurons will be repurposed to perform that computation.) For the sake of sanity of notation, we shall suppress this detail in our notation, and refer our neurons in later layers as having e.g. 'x1' as an input to them to them; in practice this means some arbitrarily good approximation to ø1. The out-register neurons will eventually store the desired outputs of the network; thus there is an out-register neuron in each layer 'corresponding" to each of the 9:-
Now suppose m > 1; if m then this paragraph and the next three paragraphs may simply be skipped. is easy to build network approximating 92,..-9m. as there is at least one "extra" neuron per layer that is available to use: the out-register neuron corresponding to 91- The strategy as follows. Let 92 = Ey= ōj. where each 6, is a monomial. Using the computation neuron and the "extra' out-register neuron in each layer, perform successive multiplications in the manner of Lemma C.I. to compute the value of ôj. For example, if 81 of 2f22 then this chain of multiplicatiios is tn (T1 (I243)). The computation neuron and the 'extra' out-register neuron in the first layer compute the multiplication a 22433, these neurons in the second layer compute the multiplication , o, and these neurons in the third layer compute x B. This value is then stored in the out-register neuron corresponding to g2 - by using the alfine part of the operation of this neuron and kept through the layers via approximate identity functions, as per Lemma 4.2
This process is then repeated for 82. The result is then added on via the affine part of the opera- tion of the out-register neuron corresponding to g2 to the value stored in the out-register neuron corresponding to 92- Repeat for all j until all of the 5, have been computed and the out-register neuron stores an approximation to 82. This is only an approximation in that it requires the use of approximate identity functions; other than that it is exact. As such, by taking sufficiently good approximations of the identity function, this will be uniform approximation to 92 over K.
Now repeat this whole process for g3... 9m.
For the rest of the layers of the network, the out-register neurons corresponding to 92,... Fm will now simply apply approximate identity functions to maintain their values: these will eventually form the outputs of the network. Let these computed values be denoted .2.....9w.. (With the 'hat' notation becuse of the fact that these are not the values .2......m.. due to the approximate identity functions in between.)
The difficult bit is computing an approximation to 91, as it must be done without the 'extra' neuron in each layer. In total, then, in each layer, there are n 2 neurons available: the in-register neurons (which have so far been storing the inputs Z,, I,,). the computation neuron, and the out-register neuron corresponding gl.
17

---

Under review as a conference paper at ICLR 2020
Written in terms of monomials, let 91
=E== 7/-- Then 91 may be written as
Ø1 71 (1 Note that this description is defined over K, as K is bounded away from the origin. In particular, let 7/- = I
72 71
73 (..
1+
7M-1 1
TM
72
7M-2
7M-1
LK Bs.k
for 0j.A E No- Substituting this in,
82.k
0g.k
fL.k Tk
1
Ik==1
1
1==1
Il
Bark Ty
))
14
k==
1
Ba 8a--1. 2
2
Now let sup K be defined by
sup = (2p ........,))) ( E K},
so that 1 < sup K < 2. Let r be an approximation to + z in the manner of Proposition C.3 with the L of that proposition given by
L =
[(sup K)- a, sup K + a| S (0,
(C.2)
where is taken small enough that the inclusion holds.
Let 7 denote composed a times. By taking r to be a suitably good approximation, we may ensure that 91 defined by
91
2M - (xx) 00,
1
2M -M 01.
01.
2M (xx)) ( 02,4
k=
+
2M -5 (orx) 02.0
y 2M -oM--6 1 (xxn ) 02.k
A=11
+
3
(xx)
Osr 0Mr-24
2 (xxx Oxe
1=1
k=1
1))
1+
((xx))
Ox
II x
Oar.k
Lkml
is an approximation to 91 K, to within e/3, with respect to || Ilag. This possible by equations and (C.2); in particular the approximation should be sufficiently precise that
2M ([sup sup K]) C L. which is why a 0 is needed: note how 22, and thus r1, , 2M- approximately the identity function on L.
This description of ği is now amenable representation with neural network. The key fact about this description of Øi is that, working from the most nested set of brackets outwards, the value of Øi may be computed by performing a single chain of multiplications and additions, and occasionally taking the reciprocal of all of the input values.
So let the computation neuron and the out-register neuron corresponding 91 perform the multipli- cations,
to compute I[ 2x &ar. the out-register neuron.
in the manner of Lemma C.1 Store this value in
18

---

Under review as a conference paper at ICLR 2020
Now the computation neurons and the in-register neurons corresponding xı (across multiple layers) to compute r(x1), in the manner of Proposition C.3 eventually the in-register neuron is now storing r(z1) = 1/21. Repeat for the other in-register neurons, that they are collectively storing ((xn)
Now the computation neuron and the out-register neuron may start multipying r(x1), ..... r (I)) on to I PM.. (which is the value presently stored the out-register neuron) the appropriate number to times to compute [ 1.
"k 0xr.) by Lemma C.I Store this value in the out-register neuron. Then add one (using the affine part of layer). The out-register neuron has now computed the expression in the innermost bracket in the description of g1-
((r
[
The general pattern is clear: apply to all of the in-register neurons again compute (ata), multiply them on to the value in the out-register neuron, and so on. Eventually the out-register neuron corresponding to gi will have computed the value J1. Actually, will have computed an approximation Ø1 to this value, because of the identity approximations involved.
By taking all of the (many) identity approximations throughout the network to be suitably precise, the values of and タ1 may be taken within e/3 of each other, and the values of 92..... 9m and
92....: Im may be taken within 28/ of each other, in each case with respect to || Il on K.
Thus ( Im approximates f with total error no more than e, and the proof is complete.
19


Reviews:
[{"review_id": "rygbXnIaKr", "reviewer": "AnonReviewer2", "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": "This paper proves universal approximation theorems for fully connected networks with fixed width and unbounded depth. Unlike recent results focusing on ReLU networks approximating scalar valued target functions, this paper provides universal approximation theorems for a wide range of activation functions and vector valued target functions. \n\nThis paper provides a number of universal approximation theorems on different activation functions, but the central result can be stated as follows: \nGiven input dimension n and output dimension m and activation \\rho, assume \\rho is a continuous function and there exists \\alpha \\in R such that \\rho is continuously differentiable at \\alpha and the derivative \\rho’ is nonzero at \\alpha. Then, a fully connected network with layer width n+m+2 and unbounded depth can approximate any continuous function on a compact domain to arbitrary sup-norm accuracy.\n\nI would like to vote for acceptance of this paper because the authors develop nontrivial techniques that extend existing universal approximation results on width-bounded ReLU networks to essentially “all” other activation functions. I think this paper is well-written and well-organized; it gives a good overview of the existing results that contextualizes this paper well, briefly summarizes the main results, and then reveals the details of construction. I haven’t checked the full details of the proofs in the appendix, but as far as I can tell they look correct.\n\nWhile I think that Section 4 reveals the proof techniques reasonably well, I believe that proofs of Propositions 4.3 and 4.7 should be covered/sketched in greater detail in the main text. For example, Theorem 4.4 builds upon Proposition 4.3 by approximating identity function locally using \\rho. The main text only reveals approximation of identity function by \\rho and defers the whole proof of Proposition 4.3 to the appendix. I think adding proof sketches for the propositions will be more helpful to the readers, and to this end, cutting down some text in the recurring paragraph “uniform continuity preserves uniform convergence…” should be helpful.\n\nAccording to Remark 4.9, it seems that the proof strategy for polynomials can also be applied to nonpolynomials. This motivates a natural question: why can’t you apply the proof strategy for nonpolynomials to polynomials? I believe you can’t because Proposition 4.3 relies on the existing universal approximation results which requires \\rho to be nonpolynomial (which is not mentioned in the main text). In my opinion, adding some comments on “why nonpoly techniques can’t be applied to poly activations” would help readers better understand the proof techniques.\n\nAnother question just out of curiosity: can you prove tightness of your construction, e.g., show that a square model with width n+m is NOT a universal approximator?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByevCWg15H", "reviewer": "AnonReviewer1", "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 complement of the fundamental Universal approximation theorem variants\n    - Based of the Register model, that the authors seem to have developed themselves from the scratch, elegant, although non-obvious\n    - Proof is straightforward, although the pictural description can be enhanced. In reality the width neurons are unfolded horizontally in the n+m+1 layer\n    - As of now, single-point continuous function does not seem to have been proven to be sufficient to build universal single-layer approximator networks in the 1999 paper. \nIt is unclear how the authors prove that part of their theorems.\n    - The third part of the paper relies on Stone-Weierstrass theorem and a manipulations around the concept of \"enhanced neurons\", carefully constrcutred to fit in the n+m+1 and n+m+2 budgets\n    - However, the proof of relaxing the Polynomial functional constraint in Theorem 4.8 is not entirely clear. While it seems to be a two-staged proof (convergence for non-linear function x^2, then convergence of a class of polynomial functions to x^2), it is unclear how the $\\rho_h$ neurons can be assembled with the registry neuron budget from the initial polynomial function.\n    - Although inspired by prior work, the author's contribution is novel, original and important.\n   \nOverall, I find this paper highly useful, elegant and, to the extent of my knowledge and understanding, properly proved. My main suggestions to the authors are with regards to the clarification of the proof of the Theorem 4.8.  after which I could increase my score.\n\nAcknowledging the rebuttal: thank you for your clarification and for updating the paper accordingly.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgOTq9EcS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Summary: The paper presents approximation power results for deep, but narrow networks with various activation functions. In particular, the authors target the minimum width possible, s.t. the class of networks considered remain universal approximators. The authors consider ReLU activation functions, polynomial activations, as well as some non-differentiable activations. \n\nEvaluation: I'm personally not very closely involved with some of the recent developments on representational power of narrow, deep networks, but it seems to me this paper follows mathematically similar intuitions to prior works (e.g. \"memorize\" the input / prior computations; another way to visually represent these proofs is to \"rotate 90 degrees\" the usual shallow network approximation -- the authors call this a \"register\" model. They cite the paper by Lu et al '17 which essentially uses this proof technique).  \n\nWhile there are some technically interesting parts (e.g. the polynomial activation part has some trickiness in maintaining the width at n+m+1), I don't think will be very interesting to the ICLR community at large, and I think it is fairly incremental. \n\nThe writing is by and large clear, though Appendix C is a little wordy and hand-wavy. \n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article studies universal approximation with deep narrow networks, targeting the minimum width. The central contribution is described as providing results for general activation functions. The technique is described as straightforward, but robust enough to handle a variety of activation functions. The reviewers found the method elegant. The most positive position was that the article develops non trivial techniques that extend existing universal approximation results for deep narrow networks to essentially all activation functions. However, the reviewers also expressed reservations mentioning that the results could be on the incremental side, with derivations similar to previous works, and possibly of limited interest. In all, the article makes a reasonable theoretical contribution to the analysis of deep narrow neural networks. Although this is a reasonably good article, it is not good enough, given the very high acceptance bar for this year's ICLR. 

Decision: Reject