Do ReLU Networks Have An Edge When Approximating Compactly-Supported Functions?
Authors: Anastasis Kratsios
Behnoosh Zamanlooy
Venue: Accepted by TMLR ()

Abstract: We study the problem of approximating compactly-supported integrable functions while implementing their support set using feedforward neural networks.  Our first main result transcribes this ``structured'' approximation problem into a universality problem.  We do this by constructing a refinement of the usual topology on the space $L^1_{\operatorname{loc}}(\mathbb{R}^d,\mathbb{R}^D)$ of locally-integrable functions in which compactly-supported functions can only be approximated in $L^1$-norm by functions with matching discretized support.  We establish the universality of ReLU feedforward networks with bilinear pooling layers in this refined topology.  Consequentially, we find that ReLU feedforward networks with bilinear pooling can approximate compactly supported functions while implementing their discretized support.  We derive a quantitative uniform version of our universal approximation theorem on the dense subclass of compactly-supported Lipschitz functions.  This quantitative result expresses the depth, width, and the number of bilinear pooling layers required to construct this ReLU network via the target function's regularity, the metric capacity and diameter of its essential support, and the dimensions of the inputs and output spaces.  Conversely, we show that polynomial regressors and analytic feedforward networks are not universal in this space.

Published Transactions on Machine Learning Research (08/2022)
Do ReLU Networks Have An Edge When Approximating Compactly-Supported Functions?
Anastasis Kratsios
krutsioa @ momaster.ea
Department of Mathematics
McMaster University
1280 Main Street West, Hamilton, Ontario, 4K1, Canada
Behnoosh Zamanlooy
zamanlob @ momaster.ca
Department of Computing and Software
McMaster University
1280 Main Street West, Hamilton, Ontario, 18S 4K1, Canada
Reviewed on OpenReview:
Abstract
We study the problem of approximating compactly-supported integrable functions while imple- menting their support set using feedforward neural networks. Our first main result transcribes this "structured" approximation problem into universality problem. We do this by constructing a re- finement of the usual topology on the space L,c (IR., _2D) of locally-interrabl functions in which functions can only be approximated in L -norm by functions with matching discretized support. We establish the universality of ReLU feedforward networks with bilinear pooling layers in this refined topology. Consequentially, we find that ReI.U feedforward networks with bilinear pooling can approximate compactly supported functions while implementing their discretized support. We derive quantitative uniform version of universal approximation theorem on the dense subclass of compactly-supported Lipschitz functions. This quantitative result expresses the depth, width, and the number of bilinear pooling layers required to construct this ReLU network via the target function's 's regularity, the metric capacity and diameter of its essential support, and the dimensions the inputs and output spaces. Conversely, we show that polynomial regressors and analytic feedforward networks are not universal this space.
Introduction
The variety of available deep learning architectures used in practice and studied in the literature can make it difficult to identify which model is best for given learning task. In this paper, consider the problem of approximating essentially compactly-supported supported (Lebesgue) integrable function f Hdd IR using a the rudimentary feedforward architecture. The typical example of such map is the distance function to the complement of compact subset of K C Rdd defined by
x x++ (x)) = inf
||=- ZER
where K is non-empty. These maps common in computer vision Di Gesu & Starovoitov (1999), in computational physics Tsai (2002), and they are used for partitioning latent metric subspaces of R& (see Cobzaş et al. (2019)).
integrable function contains more structure than an arbitrary locally- integrable function; namely, its essential support set, it is natural to ask if we can approximate such function to arbitrary precision while simultaneously exactly implementing its support up discretization of the input space ddd. Even if only focus on the class of feedforward networks from d to RD it can be unclear which activation function produces feedforward networks which are compatible with this objective.
Since an essentially compactly-supporee

---

Published Transactions on Machine Learning Research (08/2022)
We can immediately rule-out networks built using any combined number of analytic activation functions, by virtue of their analyticity. Examples include the sigmoid activation function, the Swish activation function of Ramachandran et al. (2018), the GeLU activation of Hendrycks & Gimpel (2016), the Softplus non-linearity Glorot et al. (2011), the sin function used in SIREN networks Sitzmann et al. (2020), tanh, Hermite polynomial activation functions used in Ma & Khorasani (2005), and several others examples. Since, the composition of analytic functions is again an analytic function then every such neural network must be analytic. The trouble is that no analytic function can simultaneously be conpactly-supporte and non-zero. Therefore. no feedforward architecture using only analytic activation functions can approximate a conpactly-supported function in while exactly implementing its support (up to a discretization of the input space IR
We therefore turn our attention to other most common class of activation functions; namely, (non-affine) piecewise linear activation functions such as the ReLU nonlinearity of Fukushima (1969), the PReLU activation function of He et al. (2015), or the leaky ReLU function of Maas et al. (2013). Since this class of activation functions is not analytic, it is at-least possible for neural networks with piecewise linear class to approximate essentially-compar supported integrable functions in the aforementioned sense. Since every neural network with a piecewise linear activation function can be implemented by a deep ReLU network (see (Yarotsky, 2017b, Proposition 1)) and since the ReLU activation function, defined by (x) = max [0,x}, vanishes on a large part of its input space then, is plausible that such neural networks can approximate a function while themselves having compact support. Thus, feedforward neural neural networks with (non-affine) piecewise linear activation functions seem be viable candidate for solving this approximation-theorede problem.
at.
In this paper, we demonstrate that deep feedforward networks with (non-affine) piecewise linear activation functions can approximate any essentially crnpactly-supporte (Lehesgue) integrable function f : Rd - RD while simultane- ously exactly implementing its support up to discretization of Rd provided that the feedforward model can also leverage bilinear pooling layers. We denote this set of functions by Ne Pool
To answer this question we construct a topology to TR. formalizing the mode of approximation for essentially compactly-supporter integrable functions outlined thus far. Furthermore, we wish that our universal approximation theorem implies the classical notion of Lluuiveersll approximation derived in (Hornik et al., 1989; Yarotsky. 2018; Gühring et al., 2020; Lu et al., 2021; Shen et al., 2022; Opschoor et al., 2022); therefore, our topology is constructed as a refinement of the usual metric topology on L/oc (Idd, RR) as well as the familiar norm topology on the subset L (Idd PP)) (globally) Lebesgue-integraabe functions. Our first main result confirms that is well-defined and that it encodes the aforementioned behaviour of models approximating compactly supported functions.
the set of locally-integrabbe functions L (R4, RP) from Rd
lebesgue-Integrabee Functions in T). There is a strict refinement T of the topology on LR. IRP) which refines the metric topology on L (IR RR.), whose restriction to L (Rá, RR))
Theorem 1 (Approximation of Essentially Compactly-Suppontt
) is also a strict refinement of the L -norm topology, and satisfies:
(i) Approximation of Compactly Supported Functions is Only Possible with Compactly Supported Models: For every n E N4 and every I f L- (IRd ,RP) which is essentially supported on [-n,n]d d a sequence {fr texx in Lo (Rd R2D) converges to with respect only if there is an N e N4 with N n such that all but a finite number of fe are in [NN,N] and lim IIfx fll =0
k100
(i) Simultaneous Discretized Support Implementation and L. I -Appoxximation Imply t-universality: subset F of Li IRD) is dense for if. for every f Lipioe RDD) which is essentially compactly supported, there is sequence {fn
)00 in F satisfying
lim - 1 flu = and ess-supp ess-supp((h) C [-ny 1anlnn--,,n- + 1jd: n"
where ny min(n EN_ S(s-suup(()C(Inn. ciin///neeessssu
(iii Non Implementabiliity Restrictions: For every f NN the set {f) it not open in t.
We call the topology constructed in the proof of Theorem 1 the compactly-supporte L -topology -tpolooy..
2

---

Published Transactions on Machine Learning Research (08/2022)
The Qualitative Effect Encoded by the -Topoooo t Convergence to a compactly supported Lipschitz function (such as f) in the csL -toplooyy t requires simultancous approximation of f's value and correct implementation of its support, instead of only requiring that f's values are approximated in the topologies L. (R², .RP) and on 10c (R. ).).
Figure 1: Approximation of compactly supported Lipschitz function by ReLU network with bilinear pooling
The two-dimensional example is illustrated by Figure 1, which shows the target function f: Rd del R + R (illustrated
in red), an approximation of it by ReLU network f with bilinear pooling (illustrated in blue), and discretization given by suitable of compact subsets { of IRd covering I2 up to a set of Lebesgue measure O. The target function's 's value and the network's 's output are represented by the vividness (alpha) of the each respective color. We see that ReLU network f with bilinear pooling is simultancously close to the target function f's value and that identifies the correct number of compacts subsets {K,,K, K3) containing target function f is supported (possibly with one extra set; in this case K2). Moreover, somewhat surprisingly, we will see that this approximation guarantee is independently of our discretization of Rdd (i.e. our choice of suitable compact subsets (K,) of IRd).
This illustration is formalized by the following strengthened universal approximation theorem which shows that NN is universal in the topology T on L.o RR.). Rigorously, we call function a C(R) is said to be non-affine and piecewise linear if IR can be covered by sequence of intervals on which o is affine and there is at-least one point at which a is not differentiable. Let Opw-Lán be a non-affine piecewise linear activation function and let NNReLU+Poo Pool denote the set of deep feedforward networks mapping Rd to RDD with bilinear pooling layer, defined by Pool(x]....,,x.) (x) -2x 1 at their output.
Theorem 2 (Universal Approximation Theorem + Support Implementation for Compactly Supported Functions). Let (d) E N4, and let be the topology on L)oc (IR RP) from Theorem 1. If Opw-Lin E C(R) is piecewise linear with at-least pieces then NN +Pool is dense in L (Rd,, ,RD) with respect to t.
This qualitative universal approximation theorem confirms that (non-affine) piecewise linear neural networks can approximate essentially-coompatly supported Lebesgue integrable functions between Euclidean spaces while exactly implementing their discretized support. However, the result does not describe the complexity of the neural networks model. Therefore, we also derive a quantitative version of Theorem 2 specialized for the dense class of compactly-supported Lipschitz functions mapping Rd to R.. where density meant with respect the topology
Quantitative Approximation in the CSL CSL.--Toooloyy 7
Once is constructed, the crux of our analysis when proving Theorem 2 reduces to obtaining quantitative "structured" universal approximation result shows that given any compactly supported Lipschitz function f: Rdd + D we identify a neural network f NeRRLU Pool which can approximate f's value while also implementing its discretized support.
A rigorous statement of our result requires some terminology. Denote the d-dimensional Lebesgue measure by μ. The essential support of a f (Rd. is defined by ess-supp(f) d Rd U RR:: U open and [[/]((x) = 0 f.a.e. xEU. We say that an f ( RRP) is essentially compactly supported if ess-supp(f) is contained in a closed and bounded subset of Rd. The regularity of a Lipschitz
3

---

Published Transactions on Machine Learning Research (08/2022)
function f: Rd + RD (i.e. function with at-most linear growth) is quantified by its Lipschitz constant Lip(f) # we pazz its size (X) def
||4- The "complexity" of subset X S R is quantified both in terms of sup m ||x] -xel and its "fractal dimension" as quantified by its metric capacity defined by
(
(X) del sup {n M (3x e eX), (3r 0) L B2 (x5,) r2)
where Li denotes the union of disjoint subsets of IR and where (2 r) dei {u R || | r). We mention that, for a compact Riemannian manifold, the log- capacity is always multiple of the manifold's topological dimension and the log--mas metric capacity of a a d-dimensional cube in R is proportional to d; (see (Acciaio et al., 2022, 2.1.3) for further details). We denote the set of polynomial functions from Re to RDD by IR. [x1,-..,,''' D).
Figure The Cubic-Annuli Discretization Rd (Definition
Unlike classical quantitative universal approximation theorems, this next result describes the width, depth, and number of bi-linear pooling layers required for neural network in NeReLUU+Pol to approximate compactly sup- ported Lipschitz functions while simultaneously exactly implementing its support; up to the following standardized ||x| ~0 S n + []} p= illustrated in Figure 2.
discretization of the input space {K, {x Rd
Let mention that, using using category-theoretie argument, show that the CsL csL--topology independent of any discretization of Rd used construct it. Consequentially, all universality arguments and statements, such Theorem 2, can without loss of generality be formulated using the standardized discretization illustrated in Figure 2.
Theorem 3 (Support Implementation and Uniform Approximation of ReLU Networks with Pooling).
Let : Idd + RD be Lipschitz and compactly-supporti and log, (d) N For every "width parameter" N N.
and every sequence {En] in (0, oo) converging to 0, there is a sequence (w) [m) in ReLUtUtPoo satisfying:
(i) Quantitative Worst-Case Approximation: for each N+, max max e ([(())- ((i))-fin)(es SEn. En.
(i) Convergence in CSL CSL--Topology (Pool fin) ) converges to f in the csL -topolog
(ii) Support Implementation: (f 2 +ng 2/2-den + ne/ where ny is defined
nf min E N+, c ()),
Moreover, each (()) is specified by:
(iv) Width: f(m) has Width C3 + C4 max [ 1},
(v) Depth: fo) has Depth Nlogg(N (Iog:ccap(ess-uupp diam(ess-supp()))ipppp 'c +C,
4/2
(vi) Number of Bilinearr Pooling Layers: ((0) uses logz(d) + bilinear pooling layers.

---

Published Transactions on Machine Learning Research (08/2022)
where the dimensional constants are G c24 + 3d, = +2d +2, C3 max - -xx
C dh d(D+ 1)++1)+34+3 and where > O is an absolute constant independent of d, D, and f.
In addition to the main contribution of Theorem 3, there several additional points of technical novelty in Theorem 3. The first such point is that the network complexity depends on the metric capacity of the target function's ss essential support. Omitting constants, the depth of the ReLU networks f(n) with pooling in Theorem 3 encodes three of the target function f's structural attributes. The first is the desired approximation quality, with more depth translating to better approximation capacity, and the second is the target function's 's regularity; both these factors are present in most available quantitative approximation theorems (Yarotsky, 2017b; Gühring et al., 2020; Jiao et al., 2021; Lu et al., 2021; Shen al., 2022; Opschoor et al., 2022).
E d/2
Dfpth(f (n)
Lip
(oog:(cap(ess-supp()) diam(css-suppll
N log (N + 2)1/2 Approximation Quality
Target's Regularity
Complexity: Target's Essential Support
Part of the novelty of Theorem is that identifies a third quantity impacting the approximation quality of a ReLU network with pooling, namely, the complexity of the target function's 's support. This third factor can be decomposed into two parts, the diameter of the target function's 's essential support, which other approximation theorems have also considered Siegel & Xu (2020); Kratsios & Papon (2022), but what is most interesting here is the effect of the fractal dimension (via the metric capacity; see Bruè et al. (2021) for details) of the target function's essential support. In particular, the result shows that functions essentially supported on oow-dimesiional sets (e.g. low-dimensional latent manifolds) must be simpler to approximate than those with unbounded support (e.g. locally functions supported on Rd. Theorem 2 and variant of (Shen et al., 2022, Theorem 1.1) and of the main result of Yarotsky (2017b) where the approximation has controlled support made to match that of the target function. To the best of the authors' knowledge, the result is also the only quantitative universal approximation which encodes the target function f's complexity in terms of its Lipschitz regularity, well as, the size and dimension of its essential support. We note that, since one can show that t is not a metric topology, therefore, a quantitative counterpart of Theorem 2 does not exist for arbitrary f E L.c (Rd _12) for the csL -topoloy T.
An additional point of technical novelty in Theorem 3 appears through new tools to the deep learning literature used in the result's derivation. Namely, we introduce the non-affine random projections of Ohta (2009); Bruè al. (2021) to encode this dependence into the approximation using contemporary Lipschitz-extension arguments when deriving the universal approximation theorem. We note that, these random projections are distinct mathematical objects from the linear random projections of Johnson & Lindenstrauss (1984) and, as shown in Ambrosio & Puglisi (2020), these random projections are closely related to the random partitions of unity introduced by Lee & Naor (2005).
A Sanity Check:
Comparison Between Networks in NNRel.U+ Pool and Analytic Models
We round off our discussion by verifying our intuition about analytic model classes is indeed reflected by the topology csL.' -topoloyy r. For illustrative purposes, we first consider the classical polynomial regressors, whose universal approximation capabilities in more classical topologies are guaranteed by the classical Stone-Weierstrass theorem and its numerous contemporary variants Prolla (1994), Timofte et al. (2018), or of Galindo & Sanchis (2004)).
Proposition 1 Seetnnmmial-Reeeessoone Are Not Universal L (IRd, RRP) for T). The set [[v,,.....X4 D] is not dense in Lec (Rd IRP) for the CSL -topoloyy
We return to our motivational example, by confirming that the class of deep feedforward networks which can leverage any number of analytic functions and which also have access to bilinear pooling are not dense in L IR²) for t. Denote this class of neural networks by Pool which reflects the notation for the set (*(R) of real-valued analytic functions on IR.
Proposition 2 (Analytic Feedforward Networks Are Not Universal L) (Rd RDD) for t). The set NN Pool is not dense in L (Rd, RR) with respect to the CSL -topology t t.
5

---

Published Transactions on Machine Learning Research (08/2022)
1.1 Connection to Other Deep Learning Literature
Our results are perhaps most closely related Park al. (2021) which demonstrates, to the best of our knowledge, the only other qualitative gap the deep learning theory. Namely, therein, the authors identify a minimum width under which all networks become too narrow approximate any integrable function; equivalently, the set of "very narrow" deep feedforward networks is qualitatively less expressive than the set of "arbitrary deep feedforward networks". Just as our main results are qualitative, the results of Park et al. (2021) can be contrasted against the main result of Shen et al. (2022) which quantifies the exact impacts of depth and width on approximation error of deep feedforward networks.
Our results also add to the recent scrutiny given deep feedforward networks deploying several activation functions (Jiao et al., 2021; Yarotsky & Zhevnerchuk, 2020; Beknazaryan, 2021; Yarotsky, 2021; Acciaio et al., 2022). The connection to this branch of deep learning theory happens on two distinct fronts. First NN is clearly family of deep feedforward networks simultancously utilizing several activation functions. However, more interesting, is the second connection between networks in NNReLU*+Pon Pool and the approximation theory of deep feedforward networks with generalized ReLU activation function Rx).U,(x) = max (x, where E IR is a trainable parameter. This is because, Pool can be implemented by feedforward network with ReLUp activation function, since + + ReLU22-x) (where x E IR) and (Kidger & Lyons, 2020, Lemma 4.3) shows that the multiplication map R22 3 (2) + X1lt can be exactly implemented by neural network with one hidden layer and with activation function x x x Therefore, any f Rel.eLUtPool there are fi E M representing via
x = ReLUU(X))
f= f
We note that networks with activation function (ReLU,)reR have recently rigorous study in Gribonval Rémi et al. (2021) and are related to the the constructive approximation theory of splines where ReLU, are known as truncated powers (see (DeVore & Lorentz, 1993, Chapter 5, Equation (1.1))). We also mention that Theorem is related to recent deep learning research considering the approximation of function probability measure's support. The former case is considered by Kratsios & Zamanlooy (2022), where the authors consider exotic neural network architecture specialized in the approximation of piecewise continuous functions in a certain sense. In the latter case, Puthawala et al. (2022) use GAN-like architecture to approximate probability distributions supported on low-dimensional manifold by approximating their manifold and the density thereon using a specific neural network architecture. contrast, our results compare the approximation capabilities of feedforward networks built using different activation functions.
Organization of Paper
This paper is organized as follows. Section 2 reviews the necessary deep learning terminology, measure theoretic, and topological background needed in the formulation of main result. Section 4 derives the main results, with the understanding that all technical lemmata and their proofs are relegated to the paper's appendix. Section 5 then discusses some of the implications our results and possible future directions of this type of analysis.
2 Preliminaries
We use N4 to denote the set of positive integers, fix d, E N4. and let ||- denote Euclidean distance on IR.. To simplify the analysis, we emphasize that d will always be assumed to be a power of i.e. d = =2" where d' E N4.
2.1 Deep Feedforward Networks
Originally introduced by McCulloch & Pitts (1943) as a prototypical model for artificial neural computation, deep feedforward networks have since lead to computational breakthroughs across various areas from biomedical imaging Ronneberger al. (2015) quantitative finance Buehler al. (2019); Jaimungal (2022). Though deep learning tools has become pedestrian in most contemporary scientific computational endeavors, the mathematical foundations of deep learning are still in their early stages.

---

Published Transactions on Machine Learning Research (08/2022)
Therefore, in this paper, we study the approximation-thewn properties of what is arguably the most basic deep learning model; namely, the feedforward (neural) network. These are models which iteratively process inputs in R by repeatedly applying affine transformations (as in linear regression) and simple component-we wise non-linearity called activation functions, until output in RD is eventually produced.
Our discussion naturally begins with the formal definition of the class of deep feedforward neural networks defined by (non-empty) familyy of (continuous) activation functions functions Σ _ C(R). In the case where Σ = {o) is singleton, one recovers the classical definition of a feedforward network studied in Cybenko (1989); Hornik et al. (1989); Leshno et al. (1993); Yarotsky (2017b); Kidger & Lyons (2020) and when Σ (or and the map (r.x) + (x(x) is Lebesgue a.e. differentiable then one obtains so-called trainable activation activation,functions as considered in Cheridito et al. (2021a); Kratsios al. (2022); Acciaio et al. (2022) of which the PReL.U,(x) dnf max [x,,x] activation function of He et al. (2015) is prototypical. More broadly, neural networks build using families of activation functions Σ exhibiting sub-exponential approximation rates have also recently become increasingly well-studied; e.g. Yarotsky & Zhevnerchuk (2020); Jiao et al. (2021); Yarotsky (2021); Beknazaryan (2021).
Consider the bilinear pooling layer, from computer vision (Lin et al., 2015; Kim et al., 2016; Fang et al., 2019), given for any even n E N. and x E R" as
Pool(x) MC (x/Xm/2+)) n/2
Alternatively, Pool can be thought of as masking layer with non-binary values, similar to the bilinear masking layers or bilinear attention layers used in the computer-visie vissonn literature Fang et al. (2019); Lin et al. (2015) or in the low-rank learning literature Kim et al. (2016), or as the Hadamard product of the first n/2 components of a vector in IR" with the last n components.
Fix depth D. N4. A function f: R is said to be a deep feedforward network with (bilinear) pooling if for every j JJ 1 there are Boolean pooling parameters a {0, d32 x dj,1 -dimensiona matrices AU) with dj+1,1/2 dj.2 if d22 is even and if a 1 and dj+1111 = dز2 otherwise which are called weights, bú IR funicioionfuunctionss and a e Rd called biases, and activation functions g(-i) E E such that f admits the iterative representation
f(x) +C
+c
x0+1) (ool(EU(+1)
a and dj+1 is even
for j == O.....J-1
(((-1)
:esse
20++) ((:0) (1100000
for j O...... 1; 1;1=
djt1
00)
We denote by PPol the set of all deep feedforward networks with pooling and activation functions belonging to Σ. If, in the above notation, f is such that x(++1) = x(/+1) then, we say that f is a deep feedforward network (without pooling). The collection of all deep feedforward networks (without pooling) is denoted by NN and activation functions belonging E.
In either case, if Σ consists only of single activation function o then, we use NN to denote -No-P Similarly, if Σ } then set NN d NN Let consider some examples of activation functions.
Example 1 (Non-Affine and Piecewise Linear Networks), An activation function E EC(R) is called non-affine and piecewise linear if: there exist -0 = to < < ... < tp < 1pt1 = oo and some m. .I......,,,..................... by E R for which
(i) (xx)= = m;x for every 1 E (1,,141) for each O,...,P. (ii) There exist some i [l.....p]foor which o' d'(t,) is undefined.
The prototypical example of such an activation function is Ree.U(x) = max(0,xx) Example 2 (Deep Feedforward Networks with "Adaptive" Analytic Activation Functions (N Ler C* (R) denote the set of a analytic maps from R. to itself. We set N del (R) and we use Noo+ 4d (R)*(R)=PP)

---

Published Transactions on Machine Learning Research (08/2022)
2.2 Measure Theory
Following (Schwartz, 1966, Chapter 1), we call Borel measurable function f + RR is called locally integrable if, on each compact subset K C IRd the Lebesgue integral Srex II finite. Let 4ee (R., ,R²) denote the set of locally integrable functions from Rd to IR:; with equivalence relation f' if and only if ʃ and g differ only on set of Lebesgue measure O. The set Loc (IR .) is made into a complete metric space by equipping it with the distance function d, defined on any two fig E (RR", by
1 SIIS (1(f(x) (())))(x))1 dx 2" I+ Juten [I(f(x) - -x())] dx
(fg)
The subset of (1R4 IRP) consisting of all integrable "fumctions" i.c. all f Live (R', RD) for which the integral Seet [lf(x) dx is finite, is denoted by I. (R. RR). The set L. (TR,,TRP) PRP) is made into Banach space, called the Bochner-Lebeseee space, by equipping it with the norm [|l det SaeR [I dx.
2.3 Point-Set Topology
In most of analysis function d x + [0, oo) satisfying certain axioms (see (Heinonen, 2001)), to the similarity of dissimilarity between different mathematical objects. However, not all notions of similarity can be described by metric structure and this is in particular true for several very finer notions of similarity playing central roles in functional analysis (see Narayanaswami Saxon (1986)).
the language of metric spaces, i.e.: an (abstract) set of points X together with distance
In such situations, one instead turns to the notion of a topology qualify closeness of two objects without relying the quantitative notion of distance defined though by metric. Briefly, a topology tx set X is collection of subsets of X declared as being "open"; we require only that Tx satisfy certain axioms reminiscent of the familiar open neighborhoods build using balls in metric space theory. Namely, contains the empty set and the "total" set X, the union of elements in Ty are again a member of Ty, and the countable intersection of sets in Tx are again a set in t. A topological space a pair (X, Tx) of a set X and a topology Tx on X. If clear from the context, we denote (X, Tx) by X.
Example (Metric Topology on Loc (Rd, RR))). The metric topology on L (RR, RRD, which exists, is the smallest topology on 1oo (Rdd RRP) containing all the open balls
B1 (R4 pD (.)) del {{ Looc
E (R du (f,8) <E)
where f E Lee (IR,, RDD) and E > We denote this topology by Tie-
A topology on the subset L' (Rd, of Llac (Rd (RP) can always be defined by restricting Toe as follows.
Example 4 (Subspace Topology on 1. (Rd, TRP))) The subspace topology on 1. (Rd,, ,RD), relative to the metric topology on L (Idd _RP), ). is the collection (U (
U E J.c)
A topology 5/ on X said to be strictly stronger than another topology tx on if tx C & The key relation IR and L' (Rd, ,R!) is that even if former strictly larger as set, the topology on the latter induced by the norm || |Il strictly stronger than Moe-
between 4/ (Rd (RL
The norm topology on L (Rd PR is defined as follows.
Example 5 (Norm Topology on L (IRd, ,BD)). The norm topology on L! (Rd ,BR), which exists, is the smallest topology on L' (Rd IR)) which contains all the open balls
B B d {gEL RD (f
IIf 88le: < <e).
where f E L. RR) and e > O. We denote this topology by Tnoem-

---

Published Transactions on Machine Learning Research (08/2022)
The qualitative statement being put forth by a universal approximation theorem (e.g. Leshno et al. (1993); Petrushev (1999); Yarotsky (2017a); Suzuki (2019); Grigoryeva & Ortega (2019); Heinecke et al. (2020); Kidger & Lyons (2020); Zhou (2020); Kratsios & Bilokopytov (2020); Siegel & Xu (2020); Kratsios & Hyndman (2021); Kratsios et al. (2022); Yarotsky (2022)) is statement about the topological generieness of machine learning model, such as neural network model, in specific sets topological "function" spaces. Toooloogccl genericness is called denseness, and we say that subset F X is dense with respect to topology on X if' for every non-empty open subset U E tx there exists an element f E F which also belongs to U.
Related is the notion of convergence of sequence in general topological space X. Let / be a set with preorder * (i.e. for every i. j.k E I i 5 i and if i < j and j s k then i < k), such that every finite subset of / has an upper-bound with respect to <. A typical example of a directed set is N equipped with the preorder given by S. A nel topological space is a map from a directed set to X; we denote nets by (xi)re- A typical example of a net is sequence; in which case the directed set is the natural numbers with pre-order S. The next (xi)rer is said to converge to an element x of X with respect to the topology tx if: for every tx containing x, there exists some ig I such that for every if & then x; E U.
2.4 Banic Spaces (LB-Spaces)
Our construction will exploit a special class of topological vector spaces, i.c. vector spaces wherein addition and scalar multiplication are continuous operators, formed by inductively gluing together ascending sequences of Banach spaces. Specifically, a topological vector space X is LB-space in the literature, first, one can exhibit sequence of strictly nested Banach spaces [X,]m= (i.e. each X,, is proper subspace of X,41) 1) such that
space, nearly always referred to as an 1.0
X
U X
Then, the topology on X must be smallest topology containing every convex subset B C X for which kb E B whenever & E [-1,1] and b E B, and for every positive integer n, 0 E BUX, and B X,, is an open subset of X
Conversely, given sequence of strictly nested Banach spaces (x, ) one can always form "optimal" LB-space as follows. Define x ths - X₂ and equip X with the finest topology making into an LB-space and such that, for every E N4, the inclusion X, C X continuous. Indeed, as discussed in (Osborne, 2014, Section 3.8), such topology always exists! We will henceforth refer X as the LB-space glued together from {
classical example of an L.-space arises when one wants to analyse polynomial functions but does not want to take their closure in some larger space (e.g. a larger space containing power series). We now present this example.
Example 6 (Polynomial Functions). For every n E N+, the set of degree at-most n polynomial functions mapping R to R is [x] #1 [p(x)= o B,x B E B(tl). }. We make R, [X] into Banach space through its identification the coefficients of polynomials in R, [X] with g=+1, i.e. for any polynomial p(x) = -n= E Ry [X] we define || by
|lll. 2 .... "
Thus, we may consider the R([] TB to be the LB-space glued together from [R, and Rx(x consists precisely of all polynomial functions from R E of any degree.
To illustrate the "optimality" of our LB-space, let us compare R [x[] with the smallest Banach space containing every [R, [X]== as subspace. Notice that for every positive integer n, Rn
[X] is a subspace of the following Hilbert
space of (formal) power-series [X]] (f(x)= = L Bix: E B? < oo} mapping R. to [_o0, and normed by
1/2
ll det
Σ BB}
'In the language of category theory. X is the colimit of the inductive system ((X.)=,,))) in the category of locally-convex topological vector spaces with bounded líncar maps morphisms.

---

Published Transactions on Machine Learning Research (08/2022)
By construction R[x] does not contain any function of the form f(x) Li=1 Bex where an infinite number of Bi are
equal to zero while [[] does contain such functions; e-g. f(x) di Li- belongs [[[[]] but not to [[[], In
this way. the topological vector space R[[X] is smaller than [[[[]] precisely because its topology is stronger.
Let us illustrate the topology on the L.B-space R[x). By (Osborne, 2014, Proposition 3.40) we know that a convex subset [ is open if and only U R X is open for the topology on R, [ defined by the norm in equation
Example illustrates the intuition behind LB-spaces glued together from { namely, these spaces are "minimal limits" of sequences Banach spaces which contain new element not already present in the Banach spaces (X J
3 The -SL'oTopology
We now construct the csl. -topoloy t of Theorem 2 on the set loc (TR., ,RP),, in three steps. However, before beginning construction, fix an arbitrary "good a.e. partition" of Rd As will shortly, the construction of the ' -topology t is independent of the choice of "good partition" of TRd: and thus, the construction is natural (in the precise algebraic sense describe in Proposition 3, below). However, establish this surprising algebraic property of the csL csL'-tope -topolgy t, it is more convenient to describe the construction (for any arbitrary choice of (K,, == once and for all.
Definition (Good a.e. partition of )Rd). A collection {Kr]== of compact subsets of Ted is called a good a.e.
partition if it satisfies the following conditions:
(i) The set TRd - Kn has Lebesgue measure
(ii For every n E No, Kn has positive Lebesgue measure,
(iii) For each n.m E N4, i m then K2 G Km has Lebesgue measure 0.
For instance, since our construction will be shown be independent of our choice of good a.e. partition of Red made when constructing v. Once we show this, we may, without loss of generality, henceforth only consider the following partition of RV; illustrate in Figure 2.
Example (Good a.e. partition into Cubic Annuli). For each n N4 set K₂ 4el ERERd ||||~ S +n+ 1}, where
||x| m |x). Then [ is good a.e. partition of Rdd.
Let us construct the cspoooop v, using a fixed good a.e. partition of Rd in three steps. Step 1: Given { good a.e. partition of Ed define the strictly nested sequence of Banach subspaces of 1. (Rd, RD) follows. For every E N+ let 1. (TR. IRP) consist of all f 1.! (Ted IR?)) with ess-supp(/) S K Step 2: The spaces (L,, (LR, ymm are aggregated into one LB-space, denoted by (I RD), whose underlying
is UnEN+ L,, (IB", R2.)) and equipped with the finest topology ensuring that the inclusions (IR. C L. RR)) remain continuous.
Remark 1 (Notation and Independence of Choice of Good a.e. Partition of RRd). The notation I.! RRD) does not make any reference to our choice of a good a.e. partition of Rd used to define the space L. (RRd, RD). This is because, as we will shortly see in Proposition below, the topology on L! L. RRP) ) is independent of our choice of good a.e. partition Rdd used define it. However, to formally state that result: we will make use of the notation 1! ((Km) RR)) emphasizing our choice of )== which is good a.e. partition of Rd used in Steps 1 and 2.
Step 3: Since (1R4, RRD) does not contain every function in (IR,, "RD, then, intuitively speaking, we "glue" remaining locally-ineggrable functions to (RRd, ,RD) by aggregating the topologies on L (Rd ,R.) and on Loc (Rd, ,R") to L! (Rd .RP). Rigorously, we define this gluing as follows.
Definition (CSL TTpplloy T). The cst. -topology on ( RRP) is smalles? topology on 1 (Rd RRD) containing To Tporm Tie
LL. Fnons is subbase for the topology
10

---

The next result shows that the csL L -topoloyy on Lice (TRd ,R.) is strictly finer than the norm metric topology thereon, and restriction to L (RP) is strictly stronger than the norm topology thereon ((Nagata, 1974, Chapter Published Transactions on Machine Learning Research (08/2022)
Since Enorm, Fine and F, all exist and since the smallest topology containing a collection of sets must exist (see (Munkres, 2000, page 82)); thus, t cxists. Next, we examine the key properties of & for our problem. Namely, how it compares to the usual topologies on 4oe (RR ,RR.) and on L. (R. ,R."). as well its independence of the choice of good a.e. partition of Rd used to construct it.
3.1 Properties of the CSL Copoooop T
It straightforward to see that any f Luc (IR RDD) which is essential supported on some -ー K; for some n N+ belongs L (IR4, ,).). However, Proposition 3 below implies that every essentially compactly supported Lebesgue- integrable functions must belong to (RR (Rd RP) since the set (IR. RD)) and its topology are both independent of the choice of good a.e. partition [K₂) of Ted used to construct L! (TRd RP).
The result also points to the naturality of the csL. -sopoooy t's construction. By which we mean that has the surprising and convenient algebraic property it is independent of the good a.e. partition used to build it.
Proposition 3 (The csL -topoloy t is independent of the choice of good a.e. partition). Let {Kn and {K))= be good a.e. partitions of Rd. Then ((K,, 100 RP) = ((KK, In .P). Consequentially, t is independent of the good a.e. partition TR used to construct it.
The significance of Proposition 3 that it allows us to reduce our entire understanding of the problem, and many of our proofs, simply considering single "canonical" good a.c. partition of Rd which easy to work with; namely, the Cubic Annuli of Example 7. Briefly, the reason for this is that, given good a.e. partition of IRd (K₂ )mm the approximation of compactly supported Lipschitz function f Rd - Rd in t requires to identify the smallest E N+ for which we can identify its support with respect to {K, ) which we use to discretize R4; i.e.
ess-supp(f) C Ki
(3)
Then, we must approximate í the -nom on U K2 using our model. The intuitive message Proposition is that, given any other good a.e. partition of IRd {K) the compactness of U K; implies that there is a smallest B1 E N. such that Jh=1 K, S U K'J thus, there must be smallest integer for which equation 3 holds with {K) holds in place of (Kn 1 To see the equivalence, arguing similarly, there must exist an (other) E N4, such that U K" C U K; Therefore, we may interchangeable identify where the support of a compactly supported Lipschitz function lies using any discretization of Rd by any choice of good a.c. partition of Rd
2.4)). The approximation- ippoxiimation-thhorriii implication is that fewer members of Lioc Lio ,Rd,. can be approximated by deep learning models in than in the other two topologies.
Proposition 4. The csL csL' -topology t is strictly stronger than Tee-
The phenomenon of Proposition 4 persists when restricting the topoloyy т to the subset L' L'RR', RR)) of 1.e (RR. RRD) and comparing it with the norm topology (which is stronger than Tie restricted to 1. (IRd, RRD).
Proposition 5. The restriction of the csL' -topology 4 L .R") is strictly stronger than the norm topology fnom 1.1 (Rdd (R.).
We are now in a position to prove Theorem 2. The next section outlines the main steps in the theorem's derivation, with the details being relegated to our paper's appendix.
4 Outline of the Proof of The Main Results
To better understand our main results overview the principal steps undertaken in their derivation. We begin by establishing the universality of ReLULU+PPod for the esL ' -topology, as guaranteed by Theorem 2. We build up the properties of the esI. -toplloyyy I along the way and we use them to derive the aforementioned results; whereby deriving Theorem and Theorem along the way. Propositions and are derived at the end.
Given set X and collection of subsets A of X. the smallest topology 4 X containing A is called the topology generated by A and A is called a subbasc of

---

Published Transactions on Machine Learning Research (08/2022)
4.1 Establishing Theorems 2 and 3: The universality of NNReI.U++ool in the topology t
In order establish Theorem 2, we must first understand how density in (R", R"), for the metric topology interacts with density in (Rd, RD) for the est. -opoooy. The next lemma accomplishes precisely this, by showing how dense subsets of Lice (I2 RBP) for the metrie topology can be used to construct dense subsets of (R. (R") for the -topoloy. This construction happens in two phases. First, each "function" in the original dense subset localized so that it is essentially supported on a part K2 in (any) good a.e. partition {Km] of Idd Then, each these localized "functions" are then pieced back together to form a new "function" " which is essentially supported on the compact subset U= Kn-
Let Lip (IRd, ,TPP) denote the set of "compact support" Lipschitz functions f Rd + RR:; i.e. f is Lipschitz and ess-supp(f) (f is compact subset of Rd, The first key observation in the proof of Theorem 2 is that, (IR, (R)) is dense in 4 (IR,, ,I!)) for the csL 'sL'-toop -topology t.
Lemma 1 (Density of compactly-supported Lipschitz functions in the csL ttopooyy t). The set (i,, RR) is dense in (RR ,RP) for the csL -topology t.
The second key observation, also contained in the next lemma, is a sufficient condition for approximating a "compact support" Lipschitz function with respect to the csL ss'''oopology t. Briefly, the approximation of such a function involves the simultancous approximation of its outputs as well as its essential support.
Lemma (Approximation of cempactly-supporter Lipschitz functions in the csL ctooooopoygg t), Let f L' (124 ,RP) be Lipschitz and ess-supp(f)) be compact, (K,) be the cubic-annuli of Example 7. If {fr)m is sequence in 1.c (RR RR)) for which there is an nf N4 with
flle RD) = 0 and (us-supp(f) ess-supp(ff) - 1,,y lim Ilfn fl N/ve
(4)
==1
then [fm]m= converges to f in the csL topolooy T.
Together, Lemmata 2 and provide sufficient condition for universality with respect to the csL -tooooopy Furthermore the condition is in a sense quantitative. We say in a sense, since the topology te is non- metrizaae (see (Narayanaswami & Saxon, 1986, Corollary 3) and consequentially is non-metrizable); thus there is no metric describing the approximation of function in v. L.e. no genuine quantitative statement is possible". The next lemma, Proposition and Example 7 form the content of Theorem (ii).
functions in the -spoooopology t), Let F C 4. (IRd RR). Iffor every f E Lip, (RR RR)) there exists a sequence [fn] in F satisfying the condition equation 4 then, F is dense in Toc (Re. TRP) for the est. -topology t.
Lemma 3 (Approximation of a compactly assentially-suppor
By Lemma it therefore remains construct subset of networks in Re which can approximate any compactly supported Lipschitz function in the L -nom and simultaneously correctly identify its essential support via the cubic annuli partition of Rd Figure 1 illustrates the main points of the next lemma; namely, if the target function is compactly supported then its output can be closely approximated by a ReLUU network which also simultaneously correctly identifiesthe integer n such that the target function is supported in the d-dimensional cube [-n - 1,n + 1|
Accordingly, our next lemma is an extension of the main theorem of Shen et al. (2022), which gives an estimate on the width and depth of the smallest deep ReI.U network approximating a Lipschitz map from a compact subset X of ad to RD (instead of the case where D = I and X = [0, 1.
Lemma 4 (Uniform approximation of Lipschitz maps on oow-dimensional compact subsets of Rd). Let X C Rd parameter" N E N4 there exists a f E ReLU satisfying the uniform estimate
be non-empty and compact and let f: X + R2 be Lipschitz. For every "depth parameter" L N4, and "width
D3/2/1/2
max
(f(xx)f((x) < (cez(c)())) diam (X) Lip(f) /2//112/d log, 22)1/d' NEX
"Another example of non-metric universal approximation theorem in the deep learning literature is the universal classification result of (Kratsios & Bilokopytov, 2020, Corollary 3.12)).
12

---

Published Transactions on Machine Learning Research (08/2022)
where S hides an absolute positive constant independent of D, and f. Furthermore, J satisfies
1. Width: f's width is at-most dDD+1)+3*H m J.N
2. Depth: f's depth is at-most 2011++2++19))
In order to apply Lemma 4, we need our approximating model to have support which "matches" the support of the target function f E L. (R.. R²)) UneN+ L, (TR,, IR.)) being approximated. The next lemma describes how, given ReLU network how one can build a new ReLU network with one pooling layer at its output, which coincides with the original network on an arbitrarily cubie-annuli (as in Example 7) and vanishes straightaway outsides the correct number of cubic-annuli (with possibly one part of the good a.e. partition of IRd).
Lemma 5 (Adjusting a ReLU network have support on the union of the first + cubic annuli).
Let logz (d) E N+ and f E NNReLU have depth d and width w For every N_ and each 0 < 8 < 1, there exists
frool E NNReLUU+Pool with width m - +, + w and depth 2 + 3d + d satisfying:
(i) Implementation on the Cube: For each x E [-n,n] it holds that f(x) (x),
(i) Controlled Support: ess-supp( S [- [-12--6 de + nd, 4/2 de + n
(i) Control of Error Near the Boundary: | (I(RdRRD) <E
Lemmata 1, 2, and 3 imply that NeReLU-PPol is dense in L (RR D) for the csooolop only if N has subset which can approximate any essentially compactly-supporter Lipschitz function while having almost correct support (as detected by the cubic-annuli partition) as formalized by condition 4. Since Lemma 5 implies that such a subset of networks in NeReLUUPPol exists then, Theorem 2 follows.
Proof Theorem 2. The result for PW-Lin = ReLU is a direct consequence of Lemmata 4 and 5 applied to Lemma The result for general non-affine piecewise linear activation functions from the ReLU case by (Yarotsky, 2017b, Proposition 1). This because (Yarotsky, 2017b, Proposition 1) states that any network in Npwpwii can be implemented by network in NNReLU
We now equally in position to prove the first claim in theorem Theorem 3.
Proof of Theorem 3. Since f is compactly essentially-supporeee by Lemma there is fma/2 E NNRRLU satisfying
f(x En
max supss-
(5)
with width w pmnf2 at-most d(D+1) 3d+3
max [// 13 and depth d/a// equal to
En 4/2
d paa
del.
2 (cap:ccape
diam (e))s))
(cD)id
(6)
Nlog (N + 1/2
where is an absolute constant independent of X, d, D. and f. Set ny min N4 ess-supp(f) Cl and apply Lemma fen/2 there exists an f((m) Ro with css-supp(f() C - (R0.
d
2 2- + nn 2/2-d-1 + n
equal to fea/2 on [yny and such that
$. Therefore, the estimate in equation 5 and implies that
[1s(s) (x)) xeess-supif)
(())))(()(s)) (x)]l+
-
(x) (x)12 "2-'E, 15..2-1a0 E, En
max xéess-sup(()
max
max xeess-sup(f)
13

---

Published Transactions on Machine Learning Research (08/2022)
Similarly, equation 5 implies that
- -11f - f 11 + -1 -
and that both (() and f are srventially-uupoorter in |-n , tion met. Therefore, Lemma 2 implies that the sequence (ftm) >== in NNReLU++Pd converges to f in the csp--topology
yt + 17 whence, for each N the condition equa-
remains to count each of fir)'s parameters. By construction, Lemma 5 and the estimate on w w///2 (below equa- tion 5) imply that f(n) has width at-m max - 1) 2, d(D 1) +3 34+ max J.N + 1}. Similarly,
Lemma 5 and equation 6 imply that each f(")) has depth equal to
ER 4/2
(capcsccccss dim hhtpssppppppyymmmmmmsssssppp/))/ (c29D3/d +3d) +2d
(
N Nlog (N 1/2122
C4 #t d(D+ +)+++++ yields the Relabeling G = D3/d +dd, C2 4d +2d 2, C3 dtf max (d
first conclusion.
4.2 Establishing Propositions and 2: The Non- San-University of Analytic Models in the Topology t
The main step in showing that NN fails to be dense in Li (R. RD) for the copooooy is the following necessary condition for sequence {fn] I in 4 (Rd, (RP) to convergence to some essentially compactly supported f E (IR,, (IR,,RR) D) therein with respect to t. Moreover, Proposition 3, and Example 7 Theorem (i).
Proposition 6 (Necessary condition for convergence in the esL -to-oloyy t). Let n N4 and f (R RD). A sequence {fe keNs in Loe (Ré, RD) converges to I with respect to the cst. -topology only if there is some N E N. with N 2 n such that all but a finite number of fx are in Ly (Rá, RDD) and lim [l ff =0 kt00
Together, Proposition 6 and the fact that if any analytic function on a non-empty open subset of Rd then it must be identically everywhere on Rd (see (Griffiths & Harris, 1994, page 1)) imply that no analytic function can converge essentially compactly supported "function" in 4.c (R. RP)) with respect to the csL csL' -topology.
Lemma 6 (Families analytic functions cannot be dense with respect to the esL -tooooooy t). If F is set of analytic functions from Ted to RD then
1. F is not dense in L (RR RB)) for the esL) -topology t.
2. If : I2d + R is Lipschitz, compact essential-supporte.. and not identically 0 then, a sequence
[E in o0) converging to such that no f & satisfies both Theorem (i) and (iii).
The proof of Theorem 2 (ii) is a consequence of Lemma and the observation that any network NN@-Poo is analytic function.
Proof of Theorem 2 (ii). By Lemma 6, the class of analytic functions from Rd to RR., denoted by (Rd RRP), is
not dense in L (R3, (ID) for the esZ / -topology. Now, the composition and the addition of analytic functions is again analytic. Since every affine function is analytic and since every activation function a E C is by definition analytic then, every f E " must be analytic. Le, NN C (Rd RR). Therefore, N cannot in L (Rd R for the csL -topology.
The proof of Proposition 1 now also follows from Lemma 6.
Proof of Proposition I. Since every polynomial function is analytic then, the result follows from Lemma 6.

---

Published Transactions on Machine Learning Research (08/2022)
Proof of Theorem 3 (Continued). If f Rd + RD is Lipschitz, compactly-supported, and not identically 0 then Lemma 6 and the fact that every f E NN -Pol _R[ is an analytic function implies that Theorem 3 (i)-(iii) cannot all hold simultaneously. This completes the proof of Theorem 3.
We now discuss some technical points surrounding our results, few of the implications of our findings, and how our analysis could be used to obtain similar constructions for networks designed to approximate solutions to PDEs.
5
Discussion
There are few question which arise during our analysis which we now take the time to discuss. These are: "Is Theorem 2 about refinement of the topology (RR,, IRP) in which NN Pool is universal while N is not?", "Are ReLU networks better than networks with analytic activation functions?" and "What is the significance of the bilinear pooling later pool?"
5.1 Are ReLU Networks Better Than Networks With Analytic Activation Functions?
There are several explanations for a learning model's ' success over its alternatives for a given learning task. Some of the principle reasons for a model's successful inductive bias are expressiveness, its ability to generalize well on given type of problem, and how training dynamics interact with these two properties for given problem (e.g. the impage of using different initialization schemes studied by (Martens et al., 2021)).
A key point which emphasize is that, the type of problem which we have implicitly considered in this paper concerns the approximation of compactly supported function's 's output and its support simultaneously. Therefore, we ask the following question from the approximation-ttherriii vantage point:
"Are ReLU networks better than networks with analytic activation functions?"
As may expect, the answer is mixed "yes and no". Let begin with "no" part of our answer to this question. If that is the task is to learn solution to PDE (e.g. Han et al. (2018); Beck et al. (2:21a;b) physics-informed neural networks Raissi et al. (2019); Shin et al. (2020): Mishra & Molinaro (2021)). Then, the networks should exhibit non-trivial (higher-order) partial derivatives, and the approximation should be in the C*-morm (for some (>0) 0). In such cases, is known that ReLU networks are less effective than sigmoid, tanh, or SIREN networks; see Markidis (2021) or Hornik et al. (1990); Siegel Xu (2020); De Ryck et al. (2021). fortiori, rather ReLU neural network must
I, since any weak derivative vanish outside of a set of Lebesgue measure 0. This is the "no" part of the answer the above question.
straightforward to see this when k 2 and
For the "yes" part of the answer, Theorem 2 implies that deep ReLU networks with bilinear pooling layer can approximate -ntegly-nteegrable functions while exactly implementing their support (up to good a.e. partition of RR). In contrast, as shown in Proposition 2, neural networks with analytic activation function cannot do this by virtue of their analyticity. Therefore, ReLU neural networks can be more suitable for learning tasks where the target function known to be compactly supported.
5.2 What Is The Significance Of The Bilinear Pooling Layer Pool?
We conclude our discussion by considering last question:
"What is the significance of the bilinear pooling layer?"
Our construction of network f E NNReLU+ + Pool realizing the conclusion of Theorem 3 for a given approximation error > 0 relies two distinet ReLU networks which are multiplied together using bilinear pooling layers. Suppose that f: Rd - R a compactly supported Lipschitz function and let n be the smallest integer for which ess-supp(/) is contained in the union of the first n Cubic Annuli of Example 7. The role first ReLU network fmask Rd - H2 is to implements a piece-wise affine "mask" which takes values 0 outside of 5=1 K,, value in U K,, and intermediate
15

---

Published Transactions on Machine Learning Research (08/2022)
value in Ka+1 - K2 just as in the construction of Yarotsky (2017b). The second ReLU network fe is constructed which approximates the target function f - E2 uniformly on the compact set ess-supp(f) to E e-precision, and we construct the ReLU network f in such a way that its depth and width depend on the dimension and metric capacity of ess-supp(/) well as on the regularity of the function f.
Lastly, using several bilinear pooling layers we construct the approximating network in Theorem 3 which implements f = m f Consequentially, f Rs f for every x ess-supp(s) and it is supported exactly on U Ka (i..:: its support coincides with that of the target function up to our discretization of Rd as implemented by {K₂ (=a)=)) The subtle difference in our approach and in the constructions of Yarotsky (2017b) Kidger & Lyons (2020) is that
those authors use small ReLU networks to approxinately implement the multiplication operation (x1,x2) + XjX2 instead of the bilinear pooling layers which we use. The issue here is that, their construction does not guarantee that an "approximate product" of fmask and f is supported U#+1 K₁ nor that is has compact support; whence, there is no guarantee with that method that one can construct deep ReLU network satisfying the conditions of Lemma NB, this is not say that a construction is impossible; but simply that remains an open question.
Conclusion
In this paper, we showed that deep feedforward networks with non-affine piecewise linear activation functions and bilinear pooling layers are compactly supported function; e.g. the distance map to a non-empty compact subset Euclidean space. Theorem translated this learning problem into a universal approximation problem by constructing a topology on the 11.c (TR", RD)) of locally L.ebesgue-integrable functions in which members of the subspace L. (R. IRP) of essentially compactly supporoed integrable function could only be approximated by models which match their discretized support (as formalized by good a.e. partition of Rd).
well suited to tasks where the objective is to learn
Theorem 2 demonstrated that any feedforward neural network architecture with bilinear pooling and piecewise-lineat (but non-affine) activation function is universal in this topological space. Consequentially showing that, ReLU networks with bilinear pooling layers are capable of approximating functions in (Rdd ,IP) in L Ln-rm while simultaneously implementing their support; up to a good a.e. partition Rd. Theorem provided quantitative and uniform refinement of this result for any rompactl--supoorted Lipschitz function. The result also provided quantitative estimates on the width, depth, and the number of bilinear pooling layers required for a ReLU network to implement the said approximation. Moreover, our new proof techniques allowed us explicitly encode the metric capacity and dimension of the target function's 's essential support into the models' complexity estimates.
Funding
This first stage of this research was funded by the ETH Zürich Foundation (circa 2020-2021) and the second stage was funded by the European Research Council (ERC) Starting Grant 852821 - (during 2022).
Acknowledgments
The authors would like to thank Luca Galimberti of NTNU, Florian Krach, Calypso Herrera, and Jakob Heiss from the ETH for their helpful feedback in the article's late stages. The authors would equally like to thank Ivan Dokmanić and Hieu Nguyen of the University of Basel for their helpful references concerning pooling layers and certain activation functions.
Bibliography
Beatrice Acciaio, Anastasis Kratsios, and Gudmund Pammer. Metric hypertransformers universal adapted maps. arXiv preprint arXiv:2201.13044 2022.
16

---

Published Transactions on Machine Learning Research (08/2022)
Luigi Ambrosio and Daniele Puglisi. Linear extension operators between spaces of Lipschitz maps and optimal transport. J. Reine Angew. Math., 1-21, 2020. ISSN 0075-4102. doi: 00.1515/crelee20118--1 URL
https://doi.. www.ddi.....gggoooooo
orwooog////// /0. 1515//reeeeeeeeeeeee http//..111//rreeee..... 2a1-eleee-----111 2010--00000000 0037.
Christian Beck, Sebastian Becker, Patrick Cheridito, Amulf Jentzen, and Ariel Neufeld. Deep splitting method for parabolic PDEs. SIAM J. Sei. Comput., 43(5):A3135-AS152 2021a. ISSN 1064-8275. doi: 10. 10.1137/19M1999919 URL hwtps:t/tppoo.ooooe org/10 1137/1 9M 297919.
Christian Beck, Sebastian Becker, Philipp Grohs, Nor Jaafari, and Aruulf Jentzen. Solving the Kolmogorov
PDE by means of deep learning. J. Sci. Comput., 88(3):Ppper No. 73, 28, 2021b. ISSN 0885-7474. doi:
10.10077/110155-001-0105000 URL https://dbi.org// 0000//10011--00211555-----
Aleksandr Beknazaryan. Neural networks with superexpressive activations and integer weights, arXiv preprint arXiv:2105.09911 2021.
Elia Bruè, Simone Di Marino, and Federico Stra. Linear lipschitz and el extension operators through random projection. Journal of Functional Analysis, 280(4):108868, 2021.
H. Buehler, Gonon, J. Teichmann, and Wood. Deep hedging. Quant. Finance, 19(8):127 2019. ISSN 1469-7688. doi: 40.10000//697768.2000 1571683.
URL https://doi. org/10..//o.oo... 000000009976680 2019.
Patrick Cheridito, Arnulf Jentzen, and Florian Rossmannek. Efficient approximation high-dimensional functions with neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2021a.
Patrick
Cheridito, Aruuff Jentzen, and Florian Rossmannek. Efficient approximation of high-dimensional functions with neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2021b.
Ştefan Cobzaş, Radu Miculescu, and Adriana Nicolae. Lipschitr,functions volume 2241 of Lecture Notes in Mathe- matics. Springer, Cham, 2019. ISBN 978-3-030-16488-11 978-3-030-16489-8 doi: 10010007/978-3-000-666666
URL http::tttt//o.orrreeeo org/ 10. 1007/978 3-030- 6489-8.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control Signals Systems, 2(4):
303-314, 1989. ISSN 0932-4194.
Tim De Ryck, Samuel Lanthaler, and Siddhartha Mishra. On the approximation of functions by tanh neural networks. Neural Networks, 143:732-750, 2021. ISSN 0893-6080. doi: https://doi.org/10...00 www.://....mmee2211...... http://wwwwiiieeeeeeeeeeeee htt.o///weene/rrrrreeee/////o///
URL
Ronald A. DeVore and George G. Lorentz. Constructive approximation, volume 303 of Grandlehren der mathe-
matischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer- Verlag, Berlin, 1993. ISBN 3-540-50627-6.
Vito Di Gesu and Valery Starovoitov. Distance-based functions for image comparison. Pattern Recognition Letters, 20(2):207-214, 1999.
Jean Dieudonné and Laurent Schwartz. La dualité dans les espaces LF, Ann. Inst. Fourier (Grenoble), 1:61-101 (1950), 1949.
Pengfei Fang, Jieming Zhou, Soumava Kumar Roy, Lars Petersson, and Mehrtash Harandi. Bilinear attention networks for person retrieval. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 8030-8039, 2019.
Kumihiko Fukushima. Visual feature extraction by a multilayered network of analog threshold elements. IEEE Transactions on Systems Science and Cybernetics, 5(4):322-33, 1969.
Jorge Galindo and Manuel Sanchis. Stone- Weierseeissssssss theorems for group functions. Israel J. Math., 141: 341-354, 2004. ISSN 0021-2172. doi: 10.1007/BFF22772227, URL https: //tp////..//o////////ooo //t./oooo/////////// org/10. 187.88807/F00772222
17

---

Published Transactions on Machine Learning Research (08/2022)
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Geoffrey Gordon, David Dunson, and Miroslav Dudík (eds.), Proceedings of the Fourteenth International Conference on Artificial In- telligence and Staristies, volume 15 of Proceedings of Machine Learning Research, pp- 315-323, Fort Lauderdale, mlr.
FL, USA, 11-13 Apr 2011. 1. PMLR. URL httph::p///pttt https://proceedingg htt.eed.....m....ess.//eee.. mtt..ppres//1//gllrrrooo
html.
Gribonval Rémi, Kutyniok Gitta, Nielsen Morten, and Voigtlaender Felix. Approximation spaces of deep neural networks. Constructive Approximation, forthcoming. 05 2021. ISSN 1432-0940. doi: http:://doi.or//10.0007 00066-02200055440000000000550000
Phillip Griffiths and Joseph Harris. Principles of algebraic geometry. Wiley Classics Library. John Wiley Sons, Inc., New York, 1994. ISBN 0-471-05059-8. doi: 10.1002/978111822597, URL https://doi. orgoorg////// 02gg/0..1 1002/ 97811 3781118032527. Reprint of the 1978 original.
Lyudmila Grigoryeva and Juan-Pablo Ortega. Differentiable reservoir computing. Mach, Learn. Res., 20:Paper No. 179, 62, 2019.
Ingo Gühring, Gitta Kutyniok, and Philipp Petersen. Error bounds for approximations with deep ReLU neural networks W norms. Anal. Appl. (Singup.), 18(5):803-859, 2020. ISSN 0219-5305. doi: 10.1142/
$0219530519410022 URL https: org/10. 11t.//001112/222115511 /111//122292001119990 910011111111111...
Jiequn Han, Amulf Jentzen, and Weinan E. Solving high-dimensional partial differential equations using deep learning. Proc. Natl. Acad. Sci. USA, 115(34)8505-88111 2018. ISSN 0027-8424. doi: 10.1073/pnas. 1718942115. 1ttp///paa..78942211111
URL https: //oss:////..// http:///ooooooo////////..
1073/ 1073/pnas. pnas. 111...11180 1718942115.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level
performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 110100000444 1034, 2015.
Andreas Heinecke, Jinn Ho, and Wen-Liang Hwang. Refinement and universal approximation via sparsely connected relu convolution nets. IEEE Signal Processing Letters, 27:1175-1179, 2020.
Juha Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag New York, 2001.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08413. 2016.
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks universal approximators. Neural Netw,, 2(5):359-366 July 1989.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Universal approximation of an unknown mapping and its derivatives using multilayer feedforward networks. Neural Networks, 3(5):551-560, 1990. ISSN 0893-6080. doi: http://doooog///..00000099000000 pi11/88936080089900555
URL http://www.cceeeeeeeeeeteco//ese
Sebastian Jaimungal. Reinforcement learning and stochastic optimisation.
Finance Stoch., 26(1):103- URL https://doi org/10..///. 1007/
129, 2022. ISSN 0949-2984. doi: 10. 10.1007/500330-00--0007777 500780-0211 0000--001--006-2222
Yuling Jiao, Yanming Lai, Xiliang Lu, and Zhijian Yang. Deep neural networks with relu-sine-exppoeential activations break curse of dimensionality h) older class. arXiv preprint arXiv:2103.00542 2021.
William B. Johnson and Joram Lindenstrauss, Extensions Lipschitz mappings into Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pp. 189-206. Amer. Math. Soc., Providence, RI, 1984. doi: 10.1000.100 10.1900/com/0026/77770000 URL https://doi. org/10 1090/ conm/ 0267/4400
Patrick Kidger and Terry Lyons. Universal Approximation with Deep Narrow Networks. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings Machine Learning Research, volume 125, pp. 2306-2327 PMLR, 09-12 Jul 2020.
18

---

Published Transactions on Machine Learning Research (08/2022)
Jin-Hwa Kim, Kyoung-Woon On, Woosang Lim, Jeonghee Kim, (uo Ha, and Byoung-Tak Zhang. Hadamard product for low-rank bilinear pooling. ICLR, 2016.
Anastasis Kratsios and levgen Bilokopytov. Non-euclidean universal approximation. In Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10635-10646.. Curran Associates, Inc., 2020. URL https://proceed newrips. httpeeedeiigg.rerrrrro....p///pp ccppppp/cccppp//////leeee
Anastasis Kratsios and Cody Hyndman. Neu: A meta-algorithm for universal uap-invariant feature representation. Journal of Machine Learning Research, 22(92):1-51, 2021. URL http://jmlr www.mm..orgg/pppeeeeeeee http:///mmm...rggapppe/s//////// wttp//ppprs///2/1--89/0
html.
Anastasis Kratsios and Léonie Papon. Universal approximation theorems for differentiable geometric deep
learning. Journal of Machine Learning Research, 23:1-73, 2022. doi: 10.134407RG.22222677..333
URL http://www.rr...e....e.eooa....a fo..DaFrerrrtaall....eerrrrr..ee
Anastasis Kratsios and Behnoosh Zamanlooy. Learning sub-patterns in piecewise continuous functions. Neuro-
computing, 480: 2022. ISSN 0925-2312. doi: https://doi.orr//00. 101.0/00110...eucmm0000000000000 URL
https://www.stt http://wwww..ciieeeerreeee.. http:///wwc.c.eeeeeee/ee/ateee/a
Anastasis Kratsios, Behnoosh Zamanlooy, Tianlin Liu, and Ivan Dokmanić. Universal approximation under constraints is possible with transformers. In International Conference on Learning Representations, pp. 00, 2022.
URL. / net/forummidd-GGG0CGG55::
James R. Lee and Assaf Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160 (1):59-95,, 2005. ISSN 0020-9910. 200222-004-04000
doi: 1011007:00022--044440055 URL http::://do.oorg///// 1007/
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861 867, 1993.
Tsung-Yu Yu Lin, Aruni RoyChowdhury, and Subhransu Maji. Bilinear models for fine-grained visual recognition. In Proceedings of the IEEE international conference on computer vision, pp. 1449-1457, 2015.
Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions.
SIAM J. Math. Anal., 53(5):5465-5506 2021. ISSN 0036- 1410. doi: 10.1137/20M1:4465XX URL https:
//doi, www.oogg//.0./.. / 34695X.
Liying Ma and Khashayar Khorasani. Constructive feedforward neural networks using hermite polynomial activation functions. IEEE Transactions Neural Networks, 16(4):821-833 2005.
Andrew L Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlincarities improve neural network acoustic models. In International Conference on Machine Learning, 2013. URL https::/ai..stat edw.daaaaaaaass htteers/eel__hhridiiiiee 1ato011ffnaaapppppee pdf..
Saunders MacLane. Categories for the working mathematician. Springer-Verlag, New York-Berlin, 1971. Graduate Texts in Mathematies, Vol. 5.
Stefano Markidis. The old and the new: Can physics-informed deep-learning replace traditional linear solvers? Frontiers in Big Data, 4, 2021. ISSN 2624-909X. doi: 1t.3389/faata.2222.66999 URL https://ww/ frontiersin.orge org.iinoorg//reee www.orrgg/rrrteeeeerrre 3389/fdata. 2021. 200.aa..22...66997... 669097.
James Martens, Andy Ballard, Guillaume Desjardins, Grzegorz Swirszez, Valentin Dalibard, Jascha Sohl-Dickstein. and Samuel S Schoenholz. Rapid training of deep neural networks without skip connections normalization layers using deep kernel shaping. arXiv preprint a0.0722 2021.

---

Published Transactions on Machine Learning Research (08/2022)
Warren S. McCulloch and Walter Pitts. A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophys., 5:115-133, 1943. ISSN 0007-4985. doi: 10.1007/bf02478259. URL https://doi. www.ii.rgg...o 1007/ bf02478259.
Siddhartha Mishra and Roberto Molinaro. Physics informed neural networks for simulating radiative transfer. Journal of Quantitative Spectroscopy and Radiative Transfer, 270:107705, 2021.
James R. Munkres. Topology. Prentice Hall, Inc., Upper Saddle River, NJ, 2000. ISBN 0-13-181629-2. Second edition of MR0464128).
Jun-iti Nagata. Modern general topology. North-Holland Publishing Co., Amsterdam-LLndon; Wolters-Noordhoff Publishing, Groningen; American Elsevier Publishing Co., New York, revised edition, 1974. Bibliotheca Mathematica, Vol. VII.
P. P. Narayanaswami and Stephen A. Saxon. (L.F)-ppaces, quasi-Baire spaces and the strongest locally convex topology. Math. Ann., 274 1986.
Shin-ichi Ohta. Extending Lipschitz and Hölder maps between metric spaces. Positivity, 13(2):407-425, 2009.
ISSN 1385-1292. doi: 10. 10.1007//11117-00--22000 URL https://doi..rrg/11 1000//00101 2202-2.
A. A. Opschoor, Ch. Schwab, and J. Zech. Exponential ReLU DNN expression holomorphic maps in high dimension. Constr: Approx, 55(1):537-552, 2022. ISSN 0176-4276. doi: 10.10077/400055-011-0555522 URL https://doi.c org/10 1007 w003s0003555-0 0000000000000000000-0055555
M. Scott Osborne. Locally convex spaces, volume 269 of Graduate Texts in Mathematics. Springer, Cham, 2014.
Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin. Minimum width for universal approximation. ICLR, 2021.
Pencho P. Petrushev. Approximation by ridge functions and neural networks. SIAM J. Math. Anal., 30(1):
155-189, 1999. ISSN 0036-1410. doi: 10. 10.11377503361444077299999 URI. https://doi.orgg: 1137/ 500361415 4199732295.
João Prolla. the Weierstrass-Ston -taone theorem. J. Approx. Theory. 78(3):299-311 1994. ISSN 0021-9045. doi: 10.1006/jath.1999 1994.1080. URL
100h/jath, 1994. 1080.
Michael Anthony Puthawala, Matti Lassas, Ivan Dokmanić. and Maarten V. de Hoop. Universal joint approxima- tion of manifolds and densities by simple injective flows, 2022. URL HUeyM2qVey2.
M. Raissi, P. Perdikaris, and G. E. Karniadakis. Physics-informed informed neural networks: a deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. J. Comput. Phys., 378: 686-707, 2019. ISSN 0021-9991. doi: 10. 1e.160/j.jpp.2001 2018.10.045 URL https://doot http:///oooooog////.. 1016/0061.... 2018. 14.0
Prajit Ramachandran, Barret Zoph, and Quoc Le. Searching for activation functions. In International Conference of Learning Representations, pp. 00, 2018. URL
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assisted intervention, pp. 234-241. Springer, 2015.
Raymond A. Ryan. Introduction to tensor products of Banach spaces. Springer Monographs in Mathematics. Verlag London, Ltd., London, 2002.
Laurent Schwartz. Théorie des distributions. Publications de I'Institut de Mathématique de l'Université de Strasbourg, No. IX-X. Nouvelle édition, entiérement corrigée, refondue et augmentée. Hermann, Paris, 1966.
20

---

Published Transactions on Machine Learning Research (08/2022)
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of ReLU networks in terms of width and depth. Math. Pures Appl. (9), 157:101-135, 2022. ISSN 0021-7824. doi: 10.1016f..attuu22221.000 URL https: http://ooooooo//////////// 1016/j j. matpur. 2021.07 07.009.
Yconjong Shin, Jéröme Darbon, and George Em Karniadakis. On the convergence of physics informed neural networks for linear second-order elliptic and parabolic type PDEs. Commun. Compul. Phys., 28(5):2042- 2074, 2020. ISSN 1815-2406. doi: 10.4208/cicp.or 20200000cp.00==22000199333. 2020-0193. URL https:///oi.nnn www.oi.org//1... 00000.4428//0 4288/ciccppppp/ cicp. 0a-2028-0193.
Jonathan W. Siegel and Jinchao Xu, Approximation rates for neural networks with general activation functions. Neural Networks, 128:313- 321, 2020. ISSN 0893-6080. doi: https://doi.org//00. 10w...00./....mme2220000000
Vincent Sitzmann, Julien Martel, Alexander Bergman, David Lindell, and Gordon Wetzstein. Implicit neural representations with periodic activation functions. Advances in Neural Information Processing Systems, 33: 7462-7473, 2020.
Taiji Suzuki. Adaptivity of deep reLU network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representations, pp. 00, 2019. URL wwt.viwww.neeooooo//////tttetebe
Vlad Timofte, Aida Timofte, and Liaqat Ali Khan. weieesessssss and extension theorems the nonlocally convex case. J. Math. Anal. Appl., 16242)15536-1544, 2018. ISSN 0022-247X. doi: 10.1016/j. 20w..0...........m.. URL https::/doi.org///
1016 . 2018.02..00
Yen-Hsi Richard Tsai, Rapid and accurate computation of the distance function using grids. Journal of Computa- tional Physics, 178(1):175-195, 2002.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103 114, 2017a. htw.::/....eeee.111........
ISSN 0893-6080. doi:
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103-114: 2017b. rect. com/
ISSN 0893-6080. doi: https:://oi..or//0.. 100p:/0000006.eeeeee...000000.00 URL
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31 Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 639-649. PMLR, 06-09 Jul 2018.
Dmitry Yarotsky. Elementary superexpressive activations. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11932-11940, PMLR, 18-24 Jul 2021. URL html.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constr: Approx., 55(1): 407-474, 2022. ISSN 0176-4276. doi: 10. 10.11077/000365-011--95666 URL http:://doi.org//// 1007/ 980365-021-09546-1
Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram of approximation rates for deep neural networks. H. Larochelle, M. Ranzato, Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neurul Information Processing Systems, volume 33, pp. 13005-13015. Curran Associates. Inc., 2020.
Ding-Xuan Xuan Zhou. Universality of deep convolutional neural networks. Appl. Comput. Harmon. Anal., 48()): 787-794, 2020. ISSN 1063-5203, doi: acha. 00.00.6.004. URL wtt.o/ii.rr//0..111.1110 acha. 2019. 1919.06. 06.004.
21


Reviews:
[{"review_id": "1KPOYabJ7H", "reviewer": "Reviewer_7i2i", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think that the overall idea of the proposed topological approach, as well as some specific technical contributions (the separating topology, \"good partitions\" and Proposition 1, new complexity bounds involving target's support) are interesting. However, I see some serious issues with the paper in the present state. \n\n1. I don't understand why Theorem 1 is nontrivial as formulated. Suppose that we have a dense set A in a topological space, and another set B that does not contain A. Then, as far as I understand, it is always possible to construct a refined topology in which A is dense and B is not: simply add the single-point sets for all elements of A to the topology base. Moreover, when applied to the present setting of neural networks, this works both ways, i.e. it is also possible to construct a topology in which networks with analytic activations are dense while those with piecewise linear activations are not. This point is not discusssed in the paper at all, but it conflicts with its general sentiment that one kind of activations has a fundamental advantage over another.\n\n2. The paper provides a particular construction for its topology, based on limit-Banach spaces. This construction is not easy to digest. Some of its essential properties even require category theory (Proposition 1). At the same time, the practical meaning of this topology and its relevance to approximation by neural networks are not intuitively clear. It appears from Theorem 3 that the crux of the matter is that this topology requires approximating functions to have a compact support. However, it is obvious that networks with analytic activations cannot implement nontrivial functions with compact support. This is a very simple idea already showing the significant difference between piecewise linear and analytic activations, and the added value of the whole presented complicated topological framework is not very clear to me. \n\n3. It is claimed in the end of section 2.3 (and later used) that the density of a subset in a topological space is equivalent to all points of the space being limits of sequences from the subset. This is not true in general (for non-metrizable topological spaces); one has to consider nets instead of sequences. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a topological approach to understand the differences between neural networks with piecewise linear vs. analytic activations. The results are collected in three theorems. Theorem 1 states the existence of a topology on the space of locally integrable functions with respect to which networks with piecewise linear activations are dense while those with analytic activations are not. Theorem 2 states that polynomials are not dense in this topology, either. Theorem 3 is a quantitative version of Theorem 1 providing specific bounds on the approximation by a piecewise linear network in terms of its support, accuracy and network size. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Explain why Theorem 1 is nontrivial and the two types of networks cannot be swapped in it.  \n\n2. Give a more accessible explanation of the proposed topology (e.g., if possible, describe its open sets in terms of usual metric open sets) and associated convergence. Explain why the main result is more than just the observation that analytic functions cannot be compactly supported. Give at least a heuristic explanation for Proposition 1 since it seems to play a significant role in the results. \n\n3. Fix the issue with the density described in terms of convergence of sequences. ", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nyYk6fgiMV", "reviewer": "Reviewer_jpY7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n Most of previous literatures on neural network approximation theory consider the approximation in some useful metric spaces, i.e., continuous function spaces, Holder spaces, Sobolev spaces. The manuscript deals with the network approximation issue in a more abstract sense. Specifically, the authors consider approximation in some topology spaces. I believe this is a novel way of studying neural network approximation and I think there are some novel techniques adopted in the proof of the theorems in the manuscript.\n\nWeaknesses : \nThe authors construct a separation topology but fail to show the optimality of their result. In other words, we don’t know whether there exists a weaker topology which is still able to separate ReLU and analytic neural networks.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The manuscript finds a topology such that with respect to this topology, ReLU neural network class is dense in the locally integrable space while analytic neural network classes are not dense, revealing the advantage of the former to the latter in some sense.\nThe manuscript highlights the significance of the nonsmoothness of ReLU by showing that polynomial neural networks are also not dense in the locally integrable space with respect to the separation topology. The manuscript presents a quantitative approximation result of ReLU neural network by restricting the target function being in Lipschitz and compactly supported function classes. The result is given in terms of the approximation quality, target’s regularity and the complexity of target’s support.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1.Page 3, line 2, “the essential support...”. Grammar typos.\n2.Page 3, theorem 3(i), “$x\\in [n_f,n_f]^d$”. Typos.\n3.Page 3, theorem 3(iii), the essential support should be contained in a d-dimensional cube. Typos.\n4.Page 13, discussion, paragraph 2, ”...the approximation should be in the $C^k$-norm (for some k > 0)”. In PDE settings, we often consider Sobolev spaces instead of continuous function spaces.\n\n\nAt the bottoms of page 2, the authors write “In contrast, both the above \nclassical methods cannot perform such a simultaneous approximation of a function’s output and its support. ” Can the authors turn this claim into a mathematical proposition with strict proof or cite previous results if it already exists?\nThe authors mention that the bilinear pooling can be implemented by $ReLU^2$. However, it is worth noting that the bilinear pooling can also be approximated by ReLU as ReLU can approximate multiplication (see [1]).  Does similar results still hold if we remove the pooling layer and add some ReLU layers as compensation?\n\n\n\n[1]. Dmitry Yarotsky. Error bounds for approximations with deep relu networks.\n\n\n\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HDlyc3Z4pE", "reviewer": "Reviewer_vPRx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper studies a question, regarding the choice of activation in NNs, that is (to my knowledge) poorly understood and should be of interest to the TMLR community. The paper 'takes a first step towards answering this open question'. \n- The paper provides an interesting construction of a novel topology on which PW-Lin NNs are more expressive than analytic NNs, which may be of use in its own right in theoretical studies.\n- The paper seems to be technically sound to me.\n\nWeaknesses:\n- The paper has multiple complicated definitions and concepts, and while that is inevitable I think the authors can do a much better job to make the paper more readable/accessible to the TMLR community, which will benefit the authors too (see requested changes)\n- Correct me if I'm wrong, but it seems the proof to show that analytic NNs are not dense with respect to the new constructed topology boils down to the fact that analytic functions that are compactly supported must be identically zero and that to approximate a function in this new topology we must use functions that have compact support (e.g. proposition 4 and lemma 6). This seems to be a bit simple to me, is that fair to say or have I missed something?\n- Intuition for what this separating topolgy $\\tau$ (def 2) actually is is somewhat lacking; what is included in $\\tau$ that is not present in the standing L1-norm topology $\\tau_{\\text{norm}}$?\n- The construction (provided to answer the question of activation choice) in this work seems to be somewhat far removed from practice though the question itself is of practical relevance; do the authors have any motivation for why a practitioner might find their answer interesting? Note there are results suggesting that classical analytic activations can be trained in practice to as good a better performance as PW-Lin with different initialisation schemes https://arxiv.org/abs/2110.01765, suggesting trainability is one answer rather than expressivity. \n- There are quite some typos (see below)", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper theoretically studies the question of why NNs with piecewise linear (PW-Lin) activations like ReLU empirically outperform analytic activations (e.g. sigmoid). The authors attempt to answer this question by showing that piecewise linear activations are more expressive than  their analytic activation counterparts. \n\nGiven that available universal approximation theorems in the L1-norm apply for analytic activations, the key innovation here (imo) is to construct a strictly stronger topology on the space of (locally-integrable) functions than the topology induced by the L1- norm. With respect to their constructed topology, the authors show (Theorem 1) that the NNs with PW-Lin activations is dense in the space of locally integrable functions, but that NNs with analytic activations are not. The argument for the latter seems to rely on the fact that if an analytic function is 0 in a non-empty open susbet of $\\mathbb{R}^d$ then it must be identically 0 (stated around Lemma 6). \n\nThe authors also show Theorem 3, which provides a quantitative bound on the necessary width and depth of an approximating NN with PW-Lin for a target function that is Lipschitz and compactly-supported.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Clarity:\n1. Section 1 is quite confusing given that many terms e.g. $L_{\\text{loc}}^1$ are not introduced until later e.g. Section 2/3. Also I'm not sure it makes sense to state all your results in section 1 especially because many of the terms are not defined. I would suggesting restructuring the paper to simply state the results in section 3.\n2. In abstract, should $NN^{ReLU}$ also be +Pool?\n3. The sentence 'At this point, we ask:...' comes out of nowhere and it is not very motivated the study of polynomial regressors in the build up to Theorem 2. \n4. Theorem 3 ii) should there be a hat on $f$, and also do you need another Pool given that $\\hat{f}$ is already in $NN^{Relu+Pool}$.\n5. Theorem 3 iii) should essential support be $[-c,c]^d$ not $[-c,c]$\n6. It's not clear why you need the bilinear pooling layer, can you provide more intuition for this?\n7. Page 5 Pool equation, should superscript be $n/2$ not $n$, likewise last sentence of following paragraph\n8. Why is 'the topology on the latter induced by the L1-norm is strictly stronger than $\\tau_{loc}$? This seems important as it shows that $\\tau_{loc}$ is not sufficient for your purposes, so should be explained.\n9. Where is the fact that $f$ is lipschitz used in Lemma 2 (do you need it)?\n10. What is $n$ in Proposition 4?\n11. Top line of page 13 doesn't make sense to me, shouldn't it be 'Theorem 1 (ii)' and 'Lemma 6'?\n12. I'd suggest rewriting the discussion/adding a conclusion to summarise your contributions rather than delving into higher order derivatives for future work.\n13. What do you mean by \"parts\" in top of page 11. \n\nTypos:\n1. \"approximate\" -> \"approximating\" in abstract\n2. add \"than\" after \"are more popular in practice\" in first paragraph.\n3. \"sharpe\" -> \"sharp\" (also this intuition could be interesting and is not mentioned again, so I would develop what you mean by this).\n4. \"approximate x\" not \"approximate a\" for paragraph about sec 2.4\n5. \"prove\" not \"proof in paragraph below Prop 3.\n6. \"failure\" not \"failute\" in paragraph below sec 4.\n7. \"value output of by function\" doesn't make sense last paragraph of page 10.\n8. $X=[0,1]^d$ just before Lemma 4.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I would like to thank the reviewers for a first round of on-time reviews. I would like to extend gratitude to one particular reviewer for their diligence in identifying aspects of the original presentation which would have likely obscured the nature of the contributions to the community.

After distilling some of the changes that I saw would be necessary to address this reviewer's concerns, the authors agreed on a major revision. This was carried out with such speed that the key reviewer who raised the original issues around presentation was able to re-review this updated version without the need for a formal second round. The reviewer found the changes acceptable and pointed out a few minor issues. The authors have addressed these minor issues. I also agree that the major revision addressed the key issues and find the article acceptable in its present form.


Decision: Accept (poster)