Exploring the Approximation Capabilities of Multiplicative Neural Networks for Smooth Functions
Authors: Ido Ben-Shaul
Tomer Galanti
Shai Dekel
Venue: Accepted by TMLR ()

Abstract: Multiplication layers are a key component in various influential neural network modules, including self-attention and hypernetwork layers. In this paper, we investigate the approximation capabilities of deep neural networks with intermediate neurons connected by simple multiplication operations. We consider two classes of target functions: generalized bandlimited functions, which are frequently used to model real-world signals with finite bandwidth, and Sobolev-Type balls, which are embedded in the Sobolev Space $\mathcal{W}^{r,2}$. Our results demonstrate that multiplicative neural networks can approximate these functions with significantly fewer layers and neurons compared to standard ReLU neural networks, with respect to both input dimension and approximation error. These findings suggest that multiplicative gates can outperform standard feed-forward layers and have potential for improving neural network design.

Published in Transactions on Machine Learning Research (05/2023)
Exploring the Approximation Capabilities of Multiplicative Neural Networks for Smooth Functions
Ido Ben-Shaul
ido. Sho.benshoul@gaail.co
Deportment of Applied Mathematics
Tel-Avie University, Israel
eBay Research
Tomer Galanti
galanti Cmmit, edu
Deportment of Broin and Cognitive Sciences Massachusetts Institute of Technology (MIT) Cumbridge, MA, USA
Shai Dekel
shaidekel6@@maiiccoom com
Deportment of Applied Mathematics Avio University, Ismael
Reviewed on OpenReview: https: // openreview. net/ net/forum?
forum? id= sQQJfb222
Abstract
Multiplication layers key component in various influential neural network modules, including self-attention and hypernctwork layers. In this paper, we investigate the ap- proximation capabilities of deep neural networks with intermediate neurons connected by simple multiplication operations. We consider two classes of target functions: generalized bandlimited functions, which are frequently used to model real-world signals with finite bandwidth, and Sobolev-Type balls, which are embedded in the Sobolev Space W Our results demonstrate that multiplicative neural networks with significantly fewer layers and neurons compared to standard ReLU neural networks, with respect to both input dimension and approximation error. These findings suggest that multiplicative gates can outperform standard fully-connected layers and potentially improve neural network design.
approximate these functions
1
Introduction
Deep learning has seen tremendous success in solving wide range of tasks in recent years, including image
classification (He et al.
2016 Dosovitskiy et al. 2021 Zhai et al. 2022), language processing (VVaswan et al.
2017 Devlin et al. 2019 Brown et al. 22020) interacting with open-ended environments (Silver et al. 2016
Arulkumaran et al. 2019 and code synthesis (Chen et al. 2021).
Recent empirical studies have shown that neural networks that incorporate multiplication operations between intermediate neurons (Durbin & Rumelhart 1989 Urban & van der Smagt 2016
Trask et al. 2018), such and hypernetworks (Ha particularly effective. For Dosovitskiy et al. 2021 Zhai
self-attention layers (Vaswani et al.) 2017). dynamic convolutions (Wu et al.
2019)
et a..
2017: Krueger et al. 2017 Littwin & Wolf 2019
Littwin et al. 2020
example, self-ateention layers have boen widely successful in computer vision
el al.
2022) and language processing (Cheng el al. 2016 Parikh et al. 2016
Paulus et al. 2018 Vaswani
2017). y. It has also been shown that one can achieve reasonable performance with Transformers even without applying non-lincar activation functions (Levine al. 2020). Additionally, hypernetworks, which use
et al.
multiplication to generate network weights seem improve the performance of neural networks on various
meta-learning tasks (von Oswald et al. 2020 Littwin & Woll 2019 Bensadoun et al. 2021) In different.

---

Published in Transactions on Machine Learning Research (05/2023)
line of work, (Haber & Ruthotto 2018 Eliasof et al. 2021 showed that incorporating non-linear interactions can stabilize the training of deep networks, including convolutional and graph neural networks. Despite their practical success, the theoretical reasons behind the effectiveness of multiplicative layers in deep learning remain unclear.
In this work, we study the expressive power of neural networks with multiplication layers. Specifically, we want to evaluate the number of neurons and layers needed approximate a given function within a given error tolerance using specific architecture. A classic result in the theory of deep learning, known as the universal approximation property, shows that neural networks can approximate any smooth target function with as few as one hidden layer (Cybenko) 1989 Hornik et al. 1989. Funahashi] 1989 Leshno et al. 1993). However, these papers do not provide specific information about the type of architecture and number of parameters required to achieve a given level of accuracy. This is a crucial question, as a high requirement for these resources could limit the universality of neural networks and explain their limited success in some practical applications.
In recent paper, (Jayakumar et al. 2020 investigated the role of multiplicative interaction framework including various classical and contemporary neural network components, including gating, attention layers, hypernetworks, and dynamic convolutions. The authors conjectured that multiplicative layers are well-suited for modeling conditional computations and proved that networks with multiplicative connections are more expressive than those with ReLU fully-connected layers. However, they did not investigate to what extent the multiplicative networks serve as better function approximators than standard ReLU networks.
Previous work has demonstrated that functions in Sobolev spaces can be approximated by one-hidden layer neural network with analytic activation functions (Mhaskar 1996). However, the number of neurons required to approximate these functions with an error of at most e in the Loo norm scales O(e-//r, where d is the input dimension, is the smoothness degree of the target function, and > 0 is the error rate. This raises the question of whether the curse of dimensionalityy, the phenomenon whereby the complexity of a model grows exponentially with the input dimension, is inherent to neural networks.
On the other hand, DeVore et al. 1989 proved that any continuous function approximator that approximates all Sobolev functions of order r and dimension d within error requires at least Q(c-d/r) parameters in the Lo norm. This result meets the bound of Mhaskar (1996) and confirms that neural networks cannot avoid the curse of dimensionality for the Sobolev space when approximating in the T norm. A key question is whether neural networks can overcome this curse of dimensionality for certain sets of target functions, and what kind of architectures provide the best guarantees for approximating these functions.
To overcome the curse of dimensionality, various studies (Mhaskar et al. 2017 Poggio et al. 2020 Kohler & Krzyżak 2017 Montanelli & Du. 2019 [Banchard & Bennounal 2022 Galanti & Wolf 2020 have investigated the approximation capabilities of neural networks in representing other classes of functions with some additional structural properties or by assuming weaker notions of distance, such the L2 distance. For example, Mhaskar et al. (2017): Poggio et al. (2020) showed that smooth, compositionally sparse functions with a degree of smoothness r can be approximated with the Los distance up to error e using deep neural networks with O(de-2/7 neurons. Other structural constraints have been applied to functions with structured input
spaces (Mhaskar 2010 Nakada & Imaizuui 2022 Shamidd-HHebeed 2019), compositions of functions (Kohler
& Krzyžak| (017]), piccewise smooth functions (Petersen & Voigtländer 2017 Imaizumi & Fukumizu 2018
A different line of research has focused on understanding the types of functions that certain neural network architectures can implement with regularity constraints. For example, E et al. (202I) showed that the space of 2-layer neural networks is equivalent to the Barron space when the size of their weights is restricted. They further showed that Barron functions can be approximated within e using 2-layer networks with O(c-2) neurons. Another line of research has considered spectral conditions on the function space, allowing functions to be expressed as taftt limits of shallow networks (Barron 1991 Klusowski & Barron 2018
In [Blanchard & Bennounal 2 they considered the space of Korobov functions, which are functions that are practically useful for solving partial differential equations (PDFs). They showed any Korobov function can be approximated up to error c in L2 distance with a 2-layer neural network with ReLU activation function with O /eeee//.ddddd-_// and with a ((log(d))-depth network with OlE -0.5 (og(1/e)2.m)) (.-5(dd1)+))) neurous.
2

---

Published in Transactions on Machine Learning Research (05/2023)
It is generally known that real-world datasets (such as CIFAR10 or ImageNet) often (approximately) lie
on low-dimensional manifolds of the input space (Tenenbaum et al. 2000 Belkin & Niyogi 2003). Several
publications (Nakada & Imaizumi 2022 Schmidt-HHiebrr 2019; Chen et al. 2019 Kohler et al. 2019 Suzuki
2018) studied the adaptivity of deep ReLU networks to the intrinsic dimonsionality of data and in particular showed that the curse of dimensionality avoidable when the data. lies on a low-dimensional manifold. The work of (Suzuki Nitanda 2019) further showed that deep ReLU networks can overcome the curse of dimensionality even when the imput data does not lie on a low-dimensional manifold, as long as the target function is included in some anisotropic Besov space skio (1975). In (Shen et al.) 2022) the authors showed that general target function classes (such as the Hölder or Lipschitz spaces) may be modeled by a single network, of a certain architecture, such that only a small number of 'intrinsic" parameters are used to approximate each individual function.
In a recent paper, Montanelli & Du (2021) provided approximation estimates for generalized bandlimited functions. These functions are commonly used to model signals that have finite range of frequencies (c.g.. waves, video, and audio signals), which is known as finite bandwidth. In (Montanelli & Duj 2021 ) it was shown that any bandlimited function can be approximated in Le within error using ReLU neural network of depth Olog' (1/c)) with O(e D(c-2log) (og((1/c) neurons.
In this paper, we compare the approximation capabilities of multiplicative neural network architectures with those of standard ReLU networks with respect to the L2 distance. In particular, we prove that a multiplicative neural network of depth ((lg(()) with ((g=))og(()) neurons can approximate any generalized bandlimited function up to an error of (with constants depending on the dimension and on the band). This result represents an improvement compared to the findings in (Montanelli & Du 2021 for traditional ReLU networks. Additionally, we also study the approxination guarantees of neural networks for approximating functions in Sobolev-Type balls of order r. We show that for the same error tolerance multiplicative neural networks can approximate these functions with depth (dd-11/r) and O(de neurons, while standard RcLU neural networks require depth 2/2c-2/r) and (22c-(2++)/)) nourons. These results demonstrate the superior performance of multiplicative gates compared to standard fully-connected layers. In Table [ we contrast our new bounds with preexisting bounds on the approximation power of neural networks for the Sobolev space, bandlimited functions, and the Sobolev-Type ball.
Space
Model
# neurons O(c-a/r)
Depth
Reference
WmP
C non-poly
((1)
MMaskar 1996
W7..00
ReLU
O d/r log !)
Oloo :)
Yarotsky 2017
Bandlimited functions Bandlimited functions
ReLU
O - log"
O
Monnanelli & Du 2021
Multiplicative
O log )
Oloo 2)
This paper
B2n.2 Wr.2
ReLU
((ee-12+2())
(lde-2/r)
This paper
B 5 Wr:
Multiplicative
(de
(de-
This paper
B1,1
Sigmodial
2
O(1)
(Barron 1993
Table Approximation results for Sobolev W Bandlimited and B2 functions by ReLU and multiplicative neural networks. The number of neurons and the depth are given in O notation.
Our findings offer a deeper understanding of the application of deep learning techniques in solving partial differential equations (PDFs) and signal processing. For instance, bandlimited functions are often prevalent. in signal processing applications, since the acquisition of data from sensors is frequently in the form of bandlimited functions. In such applications, neural networks are used to approximate given signal function. Our results show that multiplicative neural networks are preferable choice for approximating such functions.
In addition, recent papers suggest various approaches for solving PDEs with chysics-informen neural networks (Raissi et. al.] 2019 Karniadakis el al. 2021 Kahana el al. 2022 Ben-Shaul et al., 2023 Bar & Sochen 2021). In these methods, a deep network is trained to approximate a solution for a PDE by minimizing a loss function associated with the differential equation. For various PDEs, such as the heat equation, was shown that if the initial condition at time exists in a specific smoothness space, such as the Sobolev space WTP (refer to definition in Section 2.1 b, then the solution remains in that space for all
3

---

Published in Transactions on Machine Learning Research (05/2023)
t> O. In other scenarios, if the initial condition lies in Sobolev space W the solution can be ensured to be within a Sobolev space W where 8 r. Additionally, for elliptic boundary problems with smooth coefficients over C² smooth domains, if a weak solution exists, it automatically belongs to W (Evans 2010). Based on our findings, we recommend the use physics-aware multiplicative networks as the preferred architecture for such applications.
2 Problem Setup
We are interested determining how complex (i.e., number of trainable parameters, number of neurons and layers) model ought to be in order theoretically guarantee approximation of an unknown target function f up to given approximation error 0.
Formally, we consider a Banach space of functions V (for example, ((0, 1]9),, equipped with norm Il-liv (for example, ((.))())))))))) and a set of target functions U C. We also consider a set of approximators H and seek to quantify the ability these approximators to approximate U using the following quantity
dv(H,
sup inf ||f fllv, feu FEH
which measures the maximal approximation error for approximating target function f E U using candidates f from H. Typically, H is a parametric set of functions (e.g,, neural networks of a certain architecture) and we denote by fo E H a function that is parameterized by vector of parameters A E RN. For simplicity, we avoid writing 0 in the subscript when it is obvious from context.
2.1 Target Function Spaces
It is generally impossible to approximate arbitrary target functions using standard neural networks, demonstrated in Theorem 7.2 in (Devroye et al., 1996). As result, we oflen consider specific spaces of target functions that satisfy certain smoothness assumptions in order to obtain non-trivial results. Tn this work, we focus specifically on target functions U over the unit cube B = [0, 1]d that satisfy the following types of smoothness assumptions.
Generalized Bandlimited functions. Bandlimited functions functions whose spectrum, the set of frequencies that make up the function, is limited to certain band or range of frequencies. This property makes bandlimited functions well-suited for certain applications, such as signal processing, where it is important to ensure that the signal does not contain frequencies outside of a certain range.
Generalized bandlimited functions are defined using a generalized analytic kernel K R - C, that generalizes the classic Fourier transform, and band-limit M 2 1. Formally, for a given function Rd R, we denote the set of all functions F MM] C that retrieve f from the frequencies w E [-M, M]d using the kernel K as follows: SfKK = [F, + +R (()) F(w) x) d
We define Fy arg mig 1l MM to be the function in Sy, with the smallest Lg-norm. For instance, when K(u) exp(iu), the function Fy corresponds to the normalized standard Fourier transform of f, which is given by
F(w) (F(()) (ित / ((x))xx((ix x) dr.
The space HK,M (B) of generalized bandlimited functions a Hilbert space of functions that can be represented as weighted sum of the function K over finite domain. This space equipped with an inner product and norm, which allow us to measure the similarity and magnitude of these functions, respectively. We define HK, as the functions f
E such that
HK. (B) = (ve E B,s(x) = JJ- F(w) (w. x) dw F LMM
4

---

Published in Transactions on Machine Learning Research (05/2023)
The inner product and norm in this space are defined follows: (f. (f.9)Hmm(()) Mi- Fy(w) da, 1 ||Ey|L
One of the key properties of generalized bandlimited functions that they can be completely reconstructed from discrete set of samples. This is known as the Shannon-Nyquist theorem (Shannon 1949), and it is important result in the field of signal processing and communication. An interesting consequence of this theorem is that even in high- digh-dimensions, where seemingly unpredictable geometrical phenomena may occur (e.g. Blum et al. (2020), Chapter 2); bandlimited function can still be perfectly reconstructed given its values at the Nyquist froquency. For more dctails, sec Appendix
Sobolev spaces. Sobolev spaces are one of the most extensively studied classes of functions in approximation theory (DVoore& Lorentz 1993 Yarotsky 2017 Liang & Srikant 2017). These spaces consist of functions with bounded or p-integrable distributional derivatives up to certain order. As alrcady discussed in the introduction, they are parlicularly useful in the study of PDEs.
We first define the Lp norm, 1 S p < oo, of a given function f + R as IIfIl,, (z)l d2) where Q Rd is measurable. When p so, the essential supremum norm is used. A function f is said to be in (22) if ()))) 60.
Let r E N and S < co. The Sobolev space (B) consists of functions f B - IR with r-distributional derivatives in Lp. The Sobolev norm ||:|ww=s()) is defined as
[Illw))(B
Σ | fl)),(B): a ol
where (a1, (ai,..., ad) r.......r).. |a/1 = aatt + ad, and Da is the respective distributional derivative. We also present the semi-norm:
Σ [ll,,
|a|er
Classic results the literature show that the number of parameters needed approximate functions Wrn up to error e lower bounded by D(e ((e-d/r) (eVore et al. 1989). This exponential dependence on d is known the "curse of dimensionality".
Sobolev-Type Balls. Sobolev- Topol balls are typically subsets of Sobolev spaces with additional stronger
properties (Barron 1993 Jones 1992 Pinkus 1985; Wahba, 1990 Blanchard & Bennouna] 2022). One such property is that the magnitude of the function's 's Fourier transform, [Ff(w)], decays fast enough as [w] approaches infinity. These constraints are imposed by comparing the magnitude of the Fourier transform of the function, F Ff()), with the magnitude of (w]" for some number r > 0. In this paper we define a generalizod form of Sobolev-type balls:
Brp (1iK"= + R E L2(RR)):
(2 / (FF((w) dw S1, (2TT) / WI de S $1}
In Barron 1993), they explored the ability of neural networks approximate functions in the space < oo). We now demonstrate that any function in P1 has normalized representation in B1,1. For this, show that the conditions on P1 allow us to bound [[ Namely,
(J Le (IK)) fge (w))
/ (FF)(w)] du
[.iN (FF)(w)) du + ff
(FF)) dw
RRA1-1111
1/2
Ci (1 (FF((W) dw
[+]((F)(w)) du
JRO1-11111
s C21ff12+ + (I((F)) dw.
5

---

Published in Transactions on Machine Learning Research (05/2023)
Therefore, any function in the space P1 can be scaled to function in B1, Specifically, they showed that sigmoidal neural networks with a bounded depth and O(de neurons can approximate such functions with error at most
In this paper we will focus on the space B2.2. In Lemma 2 Appendix
we show that this space is embedded D
as proper subset of Wr2,, with the following norm:
If ((2rr)d ( (1 (1+ dw
1/2
(1)
(2TT)2
Rd
In Lemma 2 (Appendix DD, we also show an example of why the Sobolev-type ball B2r,2 is of particular interest. Specifically, we show that the additional condition that Ff(w) E L1 defines a subspace of W that can be casily approximated using multiplicative networks. It is worth mentioning that Pinkus (1985) showed that using traditional basis functions, functions the space P2 = {f E L2(Rd) fga [ [ (FF) < oo} may be approximated with error at most using (cc-d/2r) parameters. In this paper, we show that by enforcing an additional raist on the L1 norm of the Fourier transform, we can circumvent exponential dependence on the dimension
2.2 Neural Network Architectures
In the previous section, we described a setting in which a class candidate functions serve as approximators a class of target functions U. In this work, we compare the approximation guarantoes of standard multilayer perceptrons and generic set of neural networks that incorporate multiplication operations. Our goal is understand whether multiplication layers can provide better guarantees for generalized bandlimited functions and B2.2-
Multilayer perceptrons. A multilayer perceptron is neural network architecture that consists of L layers of affine linear transformations composed with element-wise non-linear activation functions (e.g., the ReLU function). Typically, the last layer does not include a non-linear activation.
Definition (Multilayer perceptron). A multilayer perceptron VL,1 IRPo + R. defined by a set of functions o Di= Each function Yi," RRP0 + IR (also known as a neuron) is recursively computed in the following manner
(x) (WL.j.VL-11 (x) = a((Wis) 10-00i:-ii1110 1z)) + bis))
bu.j
(x) = Iz..
where - 1], [pi], and w E gri-1 and big E R are the weights and a bias of the neuron ytj and Vs = (J1,1...., ). The function R + R is non-linear activation function.
this work, we focus on neural networks with ReLU activations, which are defined as ox) = max(0, æ). However, it worth noting that other activation functions have been proposed in the literature, such sigmoidal functions that measurable functions y) that satisfy v)x:) - as -c and sf(x;) 1 + 00.
Multiplicative neural networks. In this work, we are interested in comparing the approximation abilities of standard ReLU networks, with that of neural networks that incorporate multiplication layers (also known as product units (Durbin & Rumelhart, 1989)). In order to fully understand the added benefits of multiplication gates, we ask the following question: Are multipliontions belween newrons sufficient to substilute the non-lineur activations in multilayer perceptrons?
Definition 2 (Multiplicative network). A multiplicatiie neural network is a function f VL R - R
defined by set of univariate functions U (ur.) For each neuron, Yi,j T + R there erists a pair of indices j1.j2 (1.....Pi-1) (potentially dependent on i,j) such that yh is defined as follows
(x,(x)) (Wi.5.V-11'1) + ai 1. ( (z)
bb.j
(o,(x:) Ij:
where aigz bis R, waj E RPi-= are Irainable parameters, and y (yt,1,--.,7) Vb.p:)

---

Published in Transactions on Machine Learning Research (05/2023)
Multiplicative networks differ from multilayer perceptrons they rely (non-linear) multiplicative gates between neurons instead of element-wise activation functions. Each neuron Vi.j is very similar to a standard neuron in multilayer perceptron, with the distinction that a weighted multiplication between single pair of neurons 9i-1. 1i-1. is added to the output. The total number of trainable paramcters in a multiplicative layer is Pt+174 + 2p,; which is comparable to the Ps+1P; + P4 in a fully-connected layer. Following Yarolsky (2017); Blanchard & Bennouna (2022) we measure the complexity of a neural network using its depth L and its total number of neurons = == P:-
Celf-Attention and multiplicative layers. Let us describe a single-headed self-attention operation in the original Transformer (Vaswani et al., 2017]. Each layer E [L] of a depth-L Transformer encoder is defined follows. The input to the ith layer is a sequence of N tokens, denoted by æ; { where each Zi E Rdd represents the jth token of the ith layer. To compute the output of the ith layer at a particular position e [N], we use the following formula:
N
SSA =
Σ softmax, ( (L.. ri,e: WK. WVitzess
where (fftmax)((xx)) exp((tt))/EE,xxpp (xp({(x)))) is the softmax operator, and the trainable weight matrices WK,,, W WV. E Rdd xd, convert the representation from its dimension d, into the attention dimension d, = dæ, creating 'Kyy,, 'Query', and 'Value' representations, resp. As can be seen, the self-attention layers use multiplicative connections when computing the following inner product (WQ My,e. WK* xx,e). This operation compules multiplications wetween the coordinates of transformations of the same token Fi,e- In other words, it can be thought of as computing multiplicative layer on input vector zt,e. As side note, in addition to self-attention layers, transformers also incorporate commonly used layers such fully-connected layers, residual connections, and normalization layers, which are not the focus of this paper.
3 Representation Power of Multiplicative Neural Networks
In this section, we explore the expressive power of neural networks with multiplication layers. We first demonstrate that these networks can easily represent polynomial functions, which we then use to approximate bandlimited functions. This allows us to approximate functions in the space B2n, without suffering from the curse dimensionality. Specifically, we prove the following lemma:
Lemma 1. For any polynomial Pa IR + RR of degree n of the form Pa(x)) = -Eh cart, there crists a
multiplicative neural network fPOL, 1 + K, of depth L,, = -(n) with G, = O(n) neurons that satisfies (2, x, = px(x) for co E R, and x E R.
Next, we may leverage the above lemma and proceed to show how multiplicative networks can be used to approximate analytic functions For this purpose, we recall the notion of the Bernstein s-ellipse, which is a geometric shape defined on the complex plane that is useful in approximation theory.
Definition 3. Let M > 0, > be two scalars. The Bernstein s-ellipse on [-M, M] is defoned as follows
2² E. = fy C:: (ap + (6
C:
whose semi-major and semi-minor ares are a M Matg and b/ M M=
The parameter s controls the shape the ellipse. As s increases, the ellipse converges to a circle. Before stating our result in Theorem we recall the following theorem of Trefethen (019)):
Theorem (Theorem 8.2 of Trefethen (2019)). Let M > 0, 2 be scalars and K [-M, RR be on
analylic function that analylically contireuable to the elliyse E.M, where il satisfies supzeEm K(x) S Cx for some constant Cx > 0. For every n E N, there exists a polynomial hn R -> C of degree n, such that,
||hn K Kl( < 2CK8-n
7

---

Published in Transactions on Machine Learning Research (05/2023)
Theorem 1 states that any analytic function K that is bounded the Bernstein s-ellipse E can be approximated by a polynomial of degree n, with the error decreasing exponentially as the degree increases.
As we show next, the use of multiplication layers in neural networks can improve the efficiency of function ap- proximation in certain cases. The following theorem shows that deep multiplicative networks can approximate real-valued analytic functions on bounded intervals.
Theorem 2. Let M 2 1, 8 >>> 2, CK > O and c E 10 be scalors. Then, for any real-vnlued analytic function M, M] + R that is analytically continuable to the ellipse E where [K(x)] I Ck, there erists a deep mulliplicntivee network: fMA | M, .M3 - RR (MA slands for 'Multiplicative Analylic") of deplh Le = Jog, Ck) with G. 0 ( logg log2 Ck) neurons that satisfies (IMAA(Z, - (=))]lmm[-M (MM) I e.
K : [-M,
0 1og2*
Theorem 2 establishes that deep multiplicative networks with second-degree multiplications can approximate any real-valued analytic function that is bounded on the Bernstein s-ellipse E.M with error bounded by a quantity that decreases exponentially with the depth of the network.
In (Montanelli & Du 2021b, p. the authors show that the kernel may be approximated using ReLU networks with depth L. = O log5 log2
2 Ck) with G. (or log2 Ck) neurons. Thus, our approach achieves a O(log(1/e)) improvement in depth and ((log(1/e)) in the number of neurons.
Approximation of bandlimited functions. As a next step, we study the ability of neural networks to approximate bandlimited functions. The following theorem shows that a deep multiplicative network can approximate in B = [0, 1j4, a bandlimited function up to given error tolerance using a relatively small number of neurons and depth.
E Theorem 3. Let E (0, 1), M > 1, 1, 2, and K ; : C be an analytic kernel that holds the assumptions
of Theorem g with respect to > Cx > O, and bounded by a constand DR E (0, on [-dM, Let J be real-valued function in (K, Further, let F; IM M]d + C be square- square-integrable function such that f(x) = Mi K( I) dw. We define CF (Fw)) dw = - (Fw) dw. Then, there evists deep multiplicative network fMBL: B B-B R (MBL stands for MMuttipicaative bandlimited") of depth with G==0(
L, = loga CrCk
_h log,
C²
CrCi neurons that satisfies | - fllLa(B) Se
2log
According to the above theorem, one can approximate bandlimited functions up to error using multiplicative neural networks of depth L. = (loo((//e) using G. = O ((ee--loggg log(1//)) neurons. In comparison, Montanelli & Du (021)) showed that one can approximate bandlimited functions to the same level of approximation using ReLU networks of depths L. = O (log" (1/e)) with G. O log* (1/e)) neurons. This result demonstrates the parameter efficiency of multiplicative networks in comparison with standard ReLUU networks.
Approximation of Sobolev Functions. We now turn to show results for Sobolev-Type functions. We use the results on bandlimited functions shown in Theorem 3 to approximate functions in B2.2. We show that using slightly stronger assumptions, we get an approximation rate comparable to those shown by [Brroon 1993) (where the network a shallow sigmoidal network model) using multiplicative networks (i.e. without linar activations).
Theorem 4. Let d 2 2,r E N, I E B2n.2 and 6 > 0. There exists a deep ReLU network JRS (sland- ing for "ReLU Sobolev") with a depth of L. = 21fe-2 and G. = 10dde-(2+2/0) newrons, such that || -fll, S.
Theorem 5. Let d 2 2,r B2n and > 0. There erists deep ReLU network fMS (standing for "Multiplicative Sobolev") with depth of L. O(de-1/7 and G. O(de (2++(/ri))) neurons, such that g flL,,1) S..
In the following corollary, we demonstrate an application of Theorem 5 for approximating functions in the Sobolev space 2mn with an integrable Fourier transform.
Corollary 1. Let d 2 2,r E N, / E 2r2 such that [[]ll,, < co, and e > 0. There exists a deep ReLU network JMS (standing for "Multiplicative Sobolev") with depth of L. 1(r-1/r) and G. 0(c-(2((1/r))) newrons, such that MS /ll L,(B)) S max (1/R2 [[F[h where C' > O is constont dependent on r,
8

---

Published in Transactions on Machine Learning Research (05/2023)
Proof of Theorem Let f E B2r:2- We would like to approximate f using bandlimited function far and then approximate JaM using multiplicative neural network ful (standing for "Multiplicative Sobolev"). Let M > be band.
We recall the Inverse Fourier transform given by (F)) (2 J ((w) exp(iw x) di. We define the bandlimiting of f R + li as fM F (F such that fM E (B, for K K(u) exp(iu) and
F Ff. We have
- (a & (2 Ff M.
(33 I Il
1/2
((2m)d I J [Ff(w)] dw
1/2
= (2
For any w E IR \-, MJ we have |M 1 21. Therefore, since f E B2n.2
1/2
1/2
[Ff(w)) dw)
Ma M w (0 [F dw
(2 MMM
(2T)
1/2
2 M-
[P]TF dw
(2
JRd
M"
For any e >> O, we set M !r. We will construct neural network MM to approximate the bandlimitod
function Sas, such that I|ʃM fMS (LZ(BB) c/2. Assuming have constructed such fMS, then by the triangle inequality then arrive at
| - MS (B(
Il JAIlLa(B) I15M p (MSILL)(B) M + te/2 S.
Let us define the function F; 1,, MId + C as follows F(w) = (2n7 (Ff)(w). We then have the following identity
[M(x) I K(w) . x)) dw
[-SAAGe (2x) (2 F (() exp(iw- x) dw.
We may now work under the conditions of Theorem 3 We consider that Cr = Ji-M.Ma F(w)] dw (Z=ja [[MMM) dw S 1, where the inequality is due to the definition B2r.2- The kernel K(u) = exp(iu) takes as inpul. u = w- v. for x E and w E [-M, Mjd Therefore, u [-dM, d.M, and K [-dM, dM + R. Since K an entire function, is continuable to EdM for any 2, let choose 4. We notice that aM dM + 4-11 is the larger axis, and therefore the maximal norm of K on EdM is given by
Ck S exp(dM 4+4
Further, for any I we have [K(x] < 1 = Dx. We now approximate fM with multiplicative network. Using the results of Theorem 3 there exists deep multiplicative neural network fMS that approximales the bandlimited function fM in L2(B) with error bounded by e/2 and depth
CC
Le S Ci log,
log,
exp(dM 144
1
<
C2
log2
log, 4
C2
dM 1 1
+ +10g2(1/6)
(2)
2
2 2log(2)
C2 (4dM + log, (1/e))
Cz (de
1/1 -/rr logg(1/e) (1/6))
Cs de 1/2
9

---

Published in Transactions on Machine Learning Research (05/2023)
84
53
22
51-
01-
Capacity
Capacity
T12
T15
Figure Approximating Chebychev polynomials with networks of increasing complexity. We present the minimal test mean squared error (MSE) loss for approximating Chebychev polynomials T, using networks with increasing complexity, utilizing 10 initialization seeds. The network complexity (x-axis) is defined as (depth, width) and is increased linearly.
for some constants C1, C22 0. The third step follows from (og) (z) and log, (exp(x))
2/ log(a) (for all 2,, y, a 0) and the fifth inequality follows from substituting M 4/r, In addition, the number of neurons can be bounded by
2CxCr
Ge s C. - logg
s C2 e log, exp(dM4+a 444
(3)
s C "(3d(2/e) +10g2(1/6)
s C3 de -(411/))
for some constants Cj C22y C33 > 0.
Theorems provide insights into several interesting properties of the Sobolev-Tyre ball B2r First, we see that approximating these functions does not suffer from the curse of dimensionality that occurs when approximating the full Sobolev space. Secondly, for both ReLU networks and multiplicative networks, the bound decreases the smoothness index increases. In fact, the one proposed in (Barron 1993). Lastly, observe that for the same error tolerance e, multiplicative neural networks can approximate a target function f E Bzn2 with a depth of (de-1/r) and Odde neurons, while standard ReLU neural networks require a depth of c and Ofd neurons. This result demonstrates that multiplicative neural works have stronnger approximation guarantees when approximating functions in the Sopolev-Type space.
approaches infinity, the bound approaches
4 Experiments
In previous sections, demonstrated that multiplicative networks have lower complexity requirements for approximating certain target functions when compared to multilayer perceptrons. To validate these results empirically, we analyzed the influence of network complexity such depth and width on the network's approximation error. To do so, we approximated Chebyshev polynomials of varying degrees T, using multilayer perceptrons and multiplicative networks with increasing complexities (i.e., depth, width). As the degree of the Chebyshev polynomials increased, we expected multilayer perceptrons to struggle in approximating high-degree polynomials. Conversely, proven in Lemma [ T, can be perfectly constructed using a multiplicative network with depth Inn and width G,, 3n.
10

---

Published in Transactions on Machine Learning Research (05/2023)
Ground
65
34-
02-
T9
Tu
Tia
Figure Approximating Chebychev polynomials. We present the minimal test mean squared error (MSE) loss for approximating Chebychev polynomials Tn, using networks of depth n and width 10, with 10 initialization seeds. The first row displays the actual polynomials, and the second row shows the approximation errors using both multilayer perceptrons and multiplicative networks.
To validate Theorems and 5
we approximated randomly generated Gaussian mixtures. Specifically, we consider functions of the following form
N (2 E/2 exp (-5(0 ms) T,) (x mi)).
[(: =
where E Nxdxd and y E Nxd We sample lr uniformly from [0, 1j and E, uniformly from [0, 0.44.. It is straightforward to show that Gaussian mixtures are in the Schwartz class (Schwartz) 1950). This implics that they are in Wr? and that FJ E Lı (RR), which in turn means that they are also members of B2n, up to constant factor (similar to the target functions considered in Corollary I
Estimating the approximation error a model for given target function is generally a challenging problem. the ure, this is usually done by training the model fit the larget function. However, the approximation error may differ from the estimation due to optimization issues, such as sub-optimal initialization and improperly tuned hyperparameters. To obtain more procise estimation of the approximation error, we trained each model using 10 different initialization seeds and selected the minimal test mean squared error (MSE) loss of the model. This approach helped us avoid problems related to poor initialization.
In Figure [ we approximated T12 and Ti5 using networks whose depth and width varied simultaneously. The models were trained using the Adam optimizer with a learning rate 0.001 for 100 epochs and a batch size of minimize their Mean Squared Error (MSE) (with respect the target function). We used 1000 training and 1000 test samples that were uniformly selected at random from [0, 1]. As shown, multiplicative networks achieved better results (lower errors) compared to multilayer perceptrons with the same depth and width.
In Figure 2 we approximated Tn of degrees n 9, 11, 13 using multilayer perceptrons and multiplicative networks with depth n and width 10. We used the same training and testing processes as in the previous experiment. As can be seen, multiplicative networks converged to zero loss faster and provided better approximation rates for the given polynomials. For the code for generating the experiments, see Appendix B
We conducted experiments approximate the mixtures of Gaussians using multilayer perceptrons and multiplicative networks, while varying the dimensions and number of Gaussians (d and N, respectively). All
11

---

Published in Transactions on Machine Learning Research (05/2023)
Approx.
15
3
19
02
02
2 Approx:
MIE
Epach
Spec7
N
N 25
N 500
N - D00 Approx
034
$20c1
Figure 3: Approximating Gaussian mixtures with varying number of Gaussians and dimensions. We plot the test mean squared error (MSE) loss obtained by approximating Gaussian mixtures f(z; p. E) where μ E xxd xd and E E xdxd using multiplicative and ReL.U networks for different values of and N. We report their crrors averaged over 20 initialization scods along with their corresponding 95% confidence intervals.
networks had a depth and width of 10. We plotted the averaged approximation errors during training over 20 initialization seeds, along with their corresponding 95% confidence intervals, while fixing the target. function. The training was performed with the same hyperparameters in the previous experiments, except for the learning rate, which was set to 10-4
Our results, shown in Figure 3 indicate that multiplicative networks outperform multilayer perceptrons in terms of approximation errors across various dimensions and numbers of Gaussians. Interestingly, we also observed that training with multiplicative networks converges much faster than with multilayer perceptrons.
5 Conclusions
Previous papers have studiod the approximation guarantees of standard fully-connected neural networks approximate functions the Barron space B,, (Barron 1993), the space of bandlimited functions [Montanelli
& Du 2021 and the Korobov space (Blanchard & Bennouna 2022). These studies have shown that fully-
12

---

Published in Transactions on Machine Learning Research (05/2023)
connected networks can approximate wide range of smooth functions without suffering from the curse of dimensionality and have provided insights into the tradeoffs between the width and depth of neural networks in learning certain types of functions. However, these results are limited to variants of fully-connected networks and do not provide information about other types of architectures.
In this paper, we extend these results by exploring the approximation guarantees of both multiplicative neural networks and standard fully-connected networks approximate bandlimited functions and members of the Sobolev-Type ball B2r,2- Our results show that multiplicative neural networks achieve stronger approximation guarantees compared to standard ReLU networks. In addition, we show that, unlike the Barron space and the space of bandlimited functions, 2 is subset of the Sobolev space W Therefore, our results demonstrate that it is possible to avoid the curse of dimensionality for wide subsets of the Sobolev space.
13

---

Published in Transactions on Machine Learning Research (05/2023)
References
David W. Albrecht, Xuan Thinh Duong, and Alan Mcintosh. Operator theory and harmonic analysis. In Instructional Workshop on Analysis and Geometry, Part III (Canberra, 1995), volume 34, pp. 77-136. Proc. Centre Math. Appl. Austral. Nat. Univ, 1996.
Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computation perspective.
In Proceedings of the Genetic and Evolutionary Compulation Conference Companion, GECCO '19, pp. 314 1144-15, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367486. doi:
333113991991119944 URL https:
1114///9..14/3319619999 3321894
Leah Bar and Nir Sochen. Strong solutions for pde-based tomography by unsupervised learning. SIAM Journal on Imaging Sciences, 14(1):128-11) 155, 2021. doi: 10.1137 21.1137200M1332821 URL httpt:t/t//ooo btttp::/ddoi.rrg///
1137/20M132287
Andrew R. Barron. Approximation and estimation bounds for artificial neural networks. In Proceedings of the Fourth Annual Workshop on Computational Learning Theory, COLT '91, pp. 443-249, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc. ISBN 1558602135
Andrew R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930-945, 1993. doi: 10. 10.1109/18:256500.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15()):1373-3396, 2003. doi: 10. (006/88889700033288007777
Ido Ben-Shaul, Leah Bar, Dalia Fishelov, and Nir Sochen. Deep learning solution of the eigenvalue problem for differential operators. Neural Computation, pp. 1-35, 2023. ISSN 0899-7667. doi: 10.1162/neco a 01583.
URL https://doi.org: org/10
10. 1162/neco a a_01583
Raphael Bensadoun, Shir Gur, Tomer Galanti, and Lior Wolf. Meta internal learning. Tn Proceedings of the 94th International Conference on Advances in Neural Information Processing Systems, volume 34, pp. 20645 20656. Curran Associates, Inc., 2021. URL httpps:/pproceedingss wwwpaddiiinnnnn.nn..e.e.m wttppppp..pppppp2/21111 påf
file/ac796a52db33: 1at.5552233111bbbbb66333333333e1
Moise Blanchard and Mohammed Amine Bennouna. Shallow and deep networks are near-optimal approx- imators of korobov functions. In International Conference on Learning Representations, 2022. URL
https://openreeiew.rr hwtp://www.....ooooot///////o.o.
Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of Data Science. Cambridge University Press, 2020. doi: 10.1011/990 19117799711008555528.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Proceedings of the 33rd International Conference on Advances in Newrol Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL http://aa..0000000.ee//////66660
http::/pprooeednnnnen.rrrrp pd.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code. 2021.
14

---

Published in Transactions on Machine Learning Research (05/2023)
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep relu networks for functions on low dimensional manifolds. In Proceedings of the 32nd Inter- national Conference on Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL
cc/paper files//paper/219//f1ll/
(cbbecaffhbbeee2aae66600003333 pdf
Jianpeng Cheng, Li Dong, and Mirella Lapata. Long short-term memory-networks for machine reading. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 551-561, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10.18653/v1/D16-
URL httpgss//accaattdooooo.o.ogg///
George V. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2:303 314, 1989.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North Americon Chapter of the Association for Computational Linguistics: Humon Language Technologies, Volume (Long Minneapolis, Minnesota, June 2019. Association for Computational
and Short Papers), pp. Linguistics. doi: 10. 10.18653 N..1863//v1NN19-142 URL httpss//aacaaanttoooo....oooo
Ronald A. DeVore and George G. Lorentz. Constructive Approzimation. Grundlchren der mathematischen Wissenschaften. Seringer-Verlage 1993. ISBN 9783540500270..
Ronald A. DeVore, Ralph Howard, and Charles A. Micchelli. Optimal nonlinear approximation. manuscripta
mathematica, 63:469-478, 1989. doi: https:/ https://doi.nn /doi.org/ hwtpg//..100/////1 11007/BF01171759.
Lue Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recogrition. Stochastic Modelling and Applied Probability. Springer New York, NY, 1996. ISBN 978-0-387-94618-4, doi: https: ///do..org/0..000////// 1--11/7778---11--711---
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL http::///ppaaaaeeeeeeeeeeeeerrrp
Richard Durbin and David F. Rumelhart. Product units: A computationally powerful and biologically plausible extension to backpropagation networks. Neural Comput., 1(1):133 142, mar 1989. ISSN 0899-7667.
doi: 10.1162 1e..1662/nco.19800 19t.....99..1....3.. URL http://///oo....011.111100 1ttp///0..11///coo/. 1989 1.1. 1.1.133
Weinan E, Chao Ma, and Lei Wu. The barron space and the flow-induced function spaces for neural network models. Constructive Approzimation, 55:369-406, 2021. doi: /ttp:///...rgg/1111//00033333330
Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gon: Novel architectures for graph neural net-
works motivated by partial differential equations. In Proceedings of the 34th International Con- ference on Advances in Neural Information Processing Systems, volume 34, pp. 3836-3849. Cur- ran Associales, Inc., 2021. URL httpp::/pprooeeedigg.eerrrr htt.:/gs.nnrrir.ccc/.eee httpa//wwww......apppeeee//////a wtt.eee/paaee//22//1122 TT955a5ffr500sa7acccceeaaa888813
.pdf
Lawrence C. Evans. Partial differential equations. American Mathematical Society, Providence, R.I., 2010. ISBN 9780821849743 0821849743.
William Falcon et al. Pytorch lightning. GitHub. Note: http:://hhllbbboooo//////ooo/ann TorchTaghtingg////eeee pytooch lightning, 2019.
Ken-Ichi Funahashi. On the approximate realization of contimoous mappings by neural networks. Neural
Nelworks, 2(3):183-199 192, 1989. ISSN 0893-6080. doi: https://ddo..or//0..0000 10t1:///00000/0903--101 (80000000000000)000000
15

---

Published in Transactions on Machine Learning Research (05/2023)
Tomer Galanti and Lior Wolf. On the modularity of hypernetworks. In Proceedings of the 33rd In- ternational Conference on Neural Information Processing Systems, volume 33. Curran Associates Inc., 2020. ISBN 9781713829546. URL https://proceeddgs.eer nww..s..eeippppccc wwt.rps.ccccppppp.......ee..ee httpr//p....pppppp..aea////////0 /illes//paper//220//fil//
David Ha, Andrew M. Dai, and Quoc V. Lc. Hypernctoorks. In International Conference Learning Representations, 2017. URL http::///ppaaoeeeeeeeeeettrrrrrs
Eldad Haber and Lars Ruthotto. Stable architectures for deep neural networks. Inverse Problems, 34(1), 2018. doi: 111088/1361-6422/aaaaaa
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the LEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-388 366, jul 1989. ISSN 0893-6080.
Masaaki Imaizumi and Kenji Fukumizu. Deep neural networks learn non-smooth functions effectively. In International Conference on Artificial Intelligence and Stalistics, 2018.
Siddhant M. Jayakumar, Wojciech M. Czarnecki, Jacob Menick, Jonathan Schwarz, Jack Rae, Simon Osindero, Yee Whye Tch, Tim Harley, and Razvan Pascanu. Multiplicative interactions and where to find them. In International Conference on Learning Representations, 2020. URL https://openreviee..ett. www.:nnunnfttiie
ryInK6VEDH
Lee K. Jones. A Simple Lemma Greedy Approximation in Hilbert Space and Convergence Rates for Projection Pursuit Regression and Neural Network Training. The Annals of Statistics, 20(1):608 613, 1992. doi: (01214/a0s/117634458
URL https://doi org/10. 1tgg1...114//aae...... 1211//200////77445553
Adar Kahana, Eli Turkel, Shai Dekel, and Dan Givoli. A physically-informet doep-learning model using time-reversal for locating source from sparse and highly noisy sensors data. Journal of Computational Physics, 470, 2022. ISSN 0021-9991.
doi: 10. 1e.100//..jp..00220. 111592.
George Em Karniadakis, Ioannis G. Kevrekidis, Lu Lu, Paris Perdikaris, Sifan Wang, and Liu Yang. Physics-informed machine learning. Nature Reviews Physics, 3(6):222 440, 2021. ISSN 2522-5820, doi: 10.1038//44255--010000--1
Jason M. Klusowski and Andrew R. Barron. Risk bounds for high-dimensional ridge function combinations including neural networks. Xiv, 2018.
Michael Kohler and Adam Krzyžak. Nonparametric regression based on hierarchical interaction models.
IEFE Transactions on Information Theory, 63(3):1620- 1630, 2017. doi: 10.1109 2..1099/TTT2011.266633 2016.2634441.
Michael Kohler, Adam Krzyiak, and Sophie Langer. Estimation of a function of low local dimensionality by deep neural networks. IEEE Transactions on Information Theory, 68(6):4032-41)) 4042, 2019. doi: 10.1109/ 20T.202223146622
David Krueger, Chin-Wei Huang, Riashat Islam, Ryan Turner, Alexandre Lacoste, and Aaron Courville. Bayesian hypernetworks. ArXiv, 2017.
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer foodforward networks with non-polynomial activation function can approximate any function. Neural Nelworks, 6:861 867, 1993. ISSN 0893-6080. doi: https://doi.or: www.or////.......... 00..001///09960088000 508833--000000)8833---
Yoav Levine, Noam Wies, Or Sharir, Hofit Bata, and Amnon Shashua. Limits to depth efficiencies self- attention. In Proceedings of the 33rd International Conference on Advances Newral Information Processing Systems, volume 33, pp. 22640-226511 Curran Associates, Inc., 2020. URL http:sss/ppooooding.....r.r.rei.
16

---

Published in Transactions on Machine Learning Research (05/2023)
Shiyu Liang and R. Srikant. Why deep neural networks for function approximation? In International Conference on Learning Regresentations, 2017. URT. httpps://openreviee
Etai Littwin, Tomer Galanti, Lior Wolf, and Greg Yang. On infinite-widhh hypernetworks. In Aduances in Neural Information Processing Systems, volume 33, pp. 13226-13237. Curran Associates, Inc., 2020. URL
http://wwww.......e.eppppppppeee .
Gidi Littwin and Lior Wolf. Deep meta functionals for shape representation. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1824-1833. Institute of Electrical and Electronics Engineers Inc., 2019. doi: 11110//1CV..211.000000
Hrushikesh N. Mhaskar. Neural networks for optimal approximation of smooth and analytic functions. Neural Compulation, 8(1):164 177, 1996. doi: 10.1162/ neco.. htt.//ecc........ 1996.8.1.144.
Hrushikesh N. Mhaskar. Eignets for function approximation on manifolds. Applied and Compulational Harmonic Analysis, 29(1):63 87, 2010. ISSN 1063-5203. doi: https://doi.ors 111/1000111.aaiaiii 2009.08....0 08.006.
Hrushikesh N. Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better
than shallow ones? Proceedings of the AAAI Conference Artificial Intelligence, 31(1), 2017. doi: 10.1609/ http:/aai.vvi11119911111 URL https://ojs. aaai oxg//nndxx http://eeex.pppAA//a/eeeee phtp://AA///rtticc//////////////
Hadrien Montanelli and Qiang Du New error bounds for deep relu networks using sparse grids. SIAM
Journal on Mathemalics of Data Science, 1(1):78 92, 2019. doi: 10.1137/18M11800 189336. URL https
//doi.org/10. 10. 110.0.1111/11119338888888
Haizhao Montanelli, Hadrien Yang and Qiang Du Deep relu networks overcome the curse of dimensionality for generalized bandlimited functions. Journal of Computational Mathematics, 39(6):801 815, 2021. ISSN 10.4208 40.442088jjmmm 1008//cc.2000/ 200.m200772221--02200 URL http:///globall.....rr//ogggi
1991-7139. doi: https:/ httpss://doooog////// 1atg/10.44000
article article_detail/ ddetaalljcmm1911/2/ html
Ryumei Nakada and Masaaki Imaizumi.
Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. Journal of Machine Learning Research, 21(1), 2022. ISSN 1532-4435.
S. M. Nikol'skii. Approzimation of functions of several variables and imbedding theorems. Die Grundlchren der ischenatischenn Wissenschaften in Einzeldarstellungen mit besonderer Berückkichtigung der Anwen- dungsgebiete; Bd. 205. Springer-Verlag, Berlin, 1975. TSBN 0387064427.
Ankur Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit. A decomposable attention model for natural language inference. In Proceedings of the Conference on Empérical Methods in Natural Language Processing, pp. 2249 2255. Association for Computational Linguistios, 2016. doi: 10.18653/v 1118653/v11/116-1244 URL /ttpss//aalantaaai http://claaaooooooooo///-/------
org/D16-1244
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca. Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performanee deep learning library. In Pro- ceedings of the 32nd International Conference on Advances in Neural Information Processing Systems, volume 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL /ttt:://papers.nat ccppp/pcccppppppppp//////// htt.::/woor......mmmaamaaissaeee baapeeagggeppooooooooeeeeeeeaaaa
pdff
Romain Paulus, Caiming Xiong, and Richard Socher. A deep reinforced model for abstractive sum- marization. In International Conference on Learning Representations. OpenReview.net, 2018. URL
Philipp Christian Petersen and Felix Voigtländer. Optimal approximation of piccewise smooth functions using deep relu neural networks. Neural Networks, 108:296-384 -30, 2017. doi: 10.11666... neumet.2018.08.019.
17

---

Published in Transactions on Machine Learning Research (05/2023)
Allan Pinkus. N- Widths in Approzimation Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete.
3. Folge A Series of Modern Surveys in Mathematios. Springer Berlin, Heidelberg, 1985. doi: https:
Gilles Pisier. Remarks on an umpublished result of B. Maurey, 1980-1981. URL http://wwx nundam org/
Stem/SAF_1980-105 1980-1981 A5_0//
Tomaso Poggio, Andrzej Banburski, and Qianli Liao. Theoretical issues in deep networks. Proceedings
of the National Academy of Sciences, 117(48):300333 30045, 2020. doi: 10.1073 00073//mma.110039911111 1907369117. URL
https://wwz www..wwwwww.ppp..w.............. wrgg/oi/abs//..11110
190736917777
M. Raissi, P. Perdikaris, and G.E. Karniadakis.
neural networks: deep learning framework
for solving forward and inverse problems involving nonlinear partial differential equations. Journal of
Compulational Physicss 378:686 707, 2019. ISSN 0021-9991. doi: http:://bbbb.orrg11.000//////:
John J. F. Fournier Robert A. Adams. Sobolev spaces. Pure and Applied Mathematics. Academic Press,
2 edition, 2003. ISBN 97500120441433,,7781455550000000 01444444388 URL http://gen.1ib: www.ll...eeebbboooo
index. index.php7md55 pppprraf6-22aaaaa000000003333333
Johannes Schmidt-Hieber Deep relu network approximation of functions on a manifold. arXiv, 2019.
Laurent Schwartz. Théorie des noyaux. In Proceedings of the Internalional Congress of Mathemaliicinss, volume 1, pp. 220-230, 1950. URL https:///ww.mathunio.. www.mmatttinnn.mmmmm org/ wttp://///////////////////////// waaaaa/i///////////rreredrgggg/d ICM1950 1AI.MM/II.1...1111 20..0.2200.... pdfff
Claude E. Shannon. Communication in the presence of noise. Proceedings of the IRE, 37(1):10 21, 1949. doi:
191.100//RRROC.19999.. 232969.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation in terms of intrinsic parameters. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 19909 19934. PMLR, 17 23 Jul 2022. URL httpps://proceeddingg mlr press/v162/ http://hhe2ngg..em html
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Toannis Antonoglou, Veda Panneershelvam, Marc Tanctot, Sander Dieleman, Dominík Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madcleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529:484-498 2016. ISSN 0028-0836. doi: 10.1038 10.1038/naturee n666re
Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. ArXio, 2018
Taiji Suzuki and Atsushi Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic besov space. ArXiv, 2019.
Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, (00(550)) 2319 2323, 2000, doi: 10.1126/sccii /scceencee200.550..22. URL 1126 wwt.//////ence...ee/ 290 5500.5000220 2319
https://www.scli science. wttp://ewnnne.e...o//aaa//////// wwwp//////a///aare
Andrew Trask, Felix Hill, Scott Reed, Jack Rac, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. In Proceedings of the 31st International Conference on Neural Information Processing Systems, volume 31, pp. 8046 8055. Curran Associates Inc., 2018. URL https: httppss//prooceeinggs wwwp:eeweddnnnn.uuiis.....om neurips.ccppapee. httpp/ppppepeleee////ppppp files/
Lloyd N. Trefethen. Approzimation Theory and Approzimation Practice, Extended Edition. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2019. doi: 10.1187/1.978111119794444 URL
18

---

Published in Transactions on Machine Learning Research (05/2023)
Sebastian Urban and Patrick van der Smagt. A neural transfer function for smooth and differentiable transition between additive and multiplicative interactions. ArXiv, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, F ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 30th International Conference Advances in Neural Information Processing Systems, volume 30. Cur- ran Associales, Inc., 2017. URL httts::/prroceeddngg wwwwipp..ccppppeeeeppe files//paper/201//flll 3
pdf.
Gideon Schechtman Vitali D. Milman. The Mourey-Pisier Theorem, pp. 85 97. Springer Berlin Heidelberg, 1986. ISBN 978-33544-33822--7 doi: 10. 10.1007/9783 1100779978-3--40-88822---- 13. URL http::///01..orr/11010011 978-3-540-38822-7100 13
Johannes von Oswald, Christian Henning, João Sacramento, and Benjamin F. Grewe. Continual learning with hypernetworks. In International Conference on Learning Represenlations, 2020. URL https
Grace Wahba. Spline Models for Observational Dota. Society for Industrial and Applied Mathematics, 1990. doi: 10.1137/1.978161197011 URL https::/eppus..iiaet httpa//ass.....aaaaaaa//a/t..... 11T..011111111111111119900000001
Felix Wu, Angela Fan, Alexei Baevski, Yann Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions. In International Conference on Learning Representations, 2019. URL https
//openreview wwwp:nneetttdddtttttnttoeo
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural networks, 94:103 114, 2017. htwp:///oo......oooo//eeeeeee000 cac/s/ccooooArrrie////////000000
ISSN 0893-6080. doi:
URL http:://ww..ccinneirrecc
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2022.
19

---

Published in Transactions on Machine Learning Research (05/2023)
A Examples
Example 1. Let f E (2()) such that f is Bandlimited function with band (t.e., supp(Ff) C |- r Let
δ(x)= sinc(z) = (in(xx)) /TZ, T2, and Φx = 0(- - k) for all & E Zd By the Shannon-Nyquist theorem [Shannon
1949, we have:
((x) (((
E I())(< - k).
KEZ
KEZ
This means that every Bandlimited function can be completely determined using a discrete set of integer samples. This result particularly surprising for high- figh-dimnssonal functions (d is large) since the marimal distance between a point x and a sompling point grows with d. For erample, the verter of the unit cube in Bd is of distance vd/2 away from its center. Despite this, we can still recover samples from the integer vertices, even when the distances scale as vd. This property is useful when recovering high-dimensiona, functions using neural nelworks. See Figure for illustration.
v2
A/3
Figure 4: Mustootion of Example 1 A bandlimited function ʃ can be reconstructed using discrete set of values, despite the fact that the distances in each cube grow as O(vd).
B Code
In this section, we provide the code used to generate the experiments. The network architectures are described in Section 2.2 The "chebychev(n, x)" function calculates the Chebyshev polynomial of degree n for given and
input x. The HILPPolyoomaaAAproiiitttttt Lightning Falcon et al. 2019) implementations for the multilayer percept and multiplicative networks, respectively. The "MuuttpplicatvveLayr"" class based on the standard linear layer PyTorch (Paszke et al, 2019). Since the neurons in each layer are interchangeable, we arbitrarily connected the first two neurons each layer using a multiplicative operation. In each network, the layers are followed by ReLU activations.
classes are Pytorch
from torch. mn. ma.pamaeettrr import Parameter, UninitializedParamme from torch. nn import init
from torch. nn import functional as F import torch
from torch import Tensor import torch.nn as nn import torch.optim optim import pytorch_lightnitn from torch. utils. data import DataLoader, TensorDataset from tqdm import tqdm
pl
import numpy as from Mkklearn.model_seelle...
import train_test, test_pittt_
def (n x): coefs [0 for in range(n)) [1]
20

---

Published in Transactions on Machine Learning Research (05/2023)
return np. ww..poyyooial..chaaee.. chebyshev....... Chebyshev (x)
class hultiplicativellayere (nn.Modle):
_onstants___ rrin_feauures,, 'out_ [out_fettures]
in features: int
out hat_feetures: int weight: Tensor
def iiinit__ (self, in in_features: int=3, out htt_features: int=3, bias: bool = True, device=None, dtype=None) -> None:
factory.kwarge = {'device': device, 'dtype': dtype)
super (bteentinaan,,,,, self).__ini
self. featturess in_features
self outf.out_feee oeatuuess out_features
selfwwiight = Parameter (worch. (torree...tccc..e.tycc.. Betorrcc.epty(oout_eeeeo (oauureetuuuss, in featurerss), Sitactory_kwargs
= Parameter(torch cetcoorcceeepyyccccccc (out features, **factory_kwarg
gelf.muld muileehht_weihht Parameter (torch. empty(1, #*factory_kvargs)) helf.rreeet_parmeettee
def reset (aaee_pprramttessssl11 -> None:
mnit.kaiming_umiie unioorm_ weelfwweigh, =mmath.sqrt(5).
if self. bias is not None:
fan in, = init. init._calculate__F fan___aa_______ in and_and_fef fan_ can_out(( (ssel..weighh) weight) bound = / sqth. (fan_in in) if fan_ in 0 else unit..niform.pmmmm (self. bias, -bound, bound)
mit.umiform_cc (self. weight, -bound, bound)
def forward(self, Tensor) Tensor:
bs, = x. shape
x = F. F.linear (x, self weight, self. bias)
_all_output torch,
tensor ([O, .epeat (bs, 1)), dim=1)
mask forch.zeros (x)
mask[:, 1] self mult. httffmmltwwegghtmlllllle weight-mmltt_uutpp
mask
return
class Mal.Polyooniallpppoccitttoooooop (iggmnioool
def __init__ (self, width=3, depth=3, d use_relu=False):
super((._.init___ _ni__i____ self width width
delf. depth
self.poly_dee deg poly_deg
self.layers = Mo.uuuleL)stt(
self.layers apper (nn. Linear(1, (1, width))
self telf.train_los loss = 0
self.val_loss 0
for in range(self depth))
self llaerss append (ttteettooiooooyyyyeee width))
self output nn. Linear (width, 1)
self uue_uuueeeee relu use_relu
def forvard(self, x):
21

---

Published in Transactions on Machine Learning Research (05/2023)
for layer in self layers:
x layer(x)
if self uaffusee_relu.
x reluh. return self. oxtput
def training_step(satee step(self, batch, batch_idx):
X, y batch
y y_hat = self far.foorarr
loss torch.mean ( (y_hat - y) ** 2)
self logg(oraiiinnnn. loss", loss)
return {"loss": loss}
def training_epoch_enning (selff, outputs) None:
loss sum sum ['loss]] for output in outputs) len (outputs)) self. trairrnnnn. Lisian_ossaiiie [self current_epoch. = loss. item()
def validation validatiionssee((self, batch, batch_ idx):
x, y batch
y y_hat self fxrwar))))))
loss torch mean (y_hat haat y) 2)
self wow.ooogvvlllaaa _ass"s loss, prog_ bar=True) return {"val_loss"; loss}
def validation_eppee cacioon_epohheeeeee eself, outputs) -> None:
epoch_end(seff,
lyg_loss = torch.stack. (ax"tacc_xxvvalllsss for x in outputs]). .mean mean ()
self. loss [self cww.ellf.curreeeepcohhi. avg_ loss. item() ()
def inniddatio__endsaae outputs):
wyg_loss torch. torch.stack (xxck((xc ("vaaaa__ossss for in outputs]) mean ()
self ("vll"llllllooo_a ("val_losss", avg_loss)
falf.val.. [al_oos[[sel1 wurrent_epocre avg avg_loss. item avg_loss}
return
def prepare_dateae (sllf,, val val_split=0.2):
1000
X rand 1)
Y chebychev faliff.ool_degg X[:, view((1,, 1)
X_ train, X_val, Y_train, Y_val cein_test_splaee (est_split(X, Y, test_size=val_spit)
self terirtrinnaaa dataset = torch. utils www.:uutllldaaa....a. TensorDataett (X_txxttt train, Y Y_train)
self, vif.val_ddtaeee torch, utils. data. . (A_val, Y_val)
def train_ crain_dataloadersset)
return torch. utils data. DataLoader waaself..raa...mm atrain_datase,, batch size=64, shuffle=True
def val, val_ dataloadee return torch. utils. data. DatallaaDeal.. (self. mat_sata bateh_si shuffle=False)
def configure cotpuure_optimiiiesssssf.
optimizer optim. Adam parameters 1r=1e-3) return optimizer
22

---

Published in Transactions on Machine Learning Research (05/2023)
class http://a...appottaaaaaaaaaaaaaaa def
width=5, depth=3, poly_ _eg=3)
(______i___(
self.width width
self. depth
self.poly_dee deg poly_deg self.layers an.Modulelist((
self.layers wawpayyerr.pppddddcocom self.train, loss = 0
append (nn Lin.ern
Linear (1, width))
self.val_oss 0
for in range(self depth))
aappedd self self. output nn. Linear (width, 1)
self layers.ers... append (nn Linear (width, width))
def forward(self,, x):
for layer in self layers:
x rorch.relu(layerr) return self.output(x)
def training_stepleenn (sell,,,,,, batch, batch_idx)
x, y batch
y y_hat = self forwarr)))
loss = torch.meant haa y) ** 2)
self log(traan " loss)
return {"loss": loss}
def graininggepoch_endee
outputs) -> None:
loss sum sun(outut ("loss" for output in outputs) (en(oututss) self train loss [self. current_epoch, loss. item()
def validation_stepll
batch, batch_idh idx)
y = batch
y_hat self forward)))
loss forch.meant (y_hat haat y) 2)
self www.lolgvvllllll "ivvallsss"" loss, prog_ bar=True)
return {"val_loas"; loss]
def validation_epe apoocheendssef,, outputs) -> None:
log_loss = Norch.stack. (xtaaallxxvvvlllllooo for x in outputs]) mean ()
self val loss www.eccuerrrrcctiiieee avg_ loss. item()
def validationnend(sell: outputs):
avg_loss torch. stack ([x("val_loss"" for in outputs]) mean self vvll loss", log_l
self.val vww_ [self wwwrent_epoche = avg_loss. item() ()
return
avg_loss}
def prepare (sela,,, val_ val_split=0.2): 1000
rand 1)
Y chebychev peg, X[:, 0]) vieww,, 1)
X_ train, X_ val, Y Y_train, Y_val =
Y, test_ pat__sizerval_plitt)
self. trriitraaaaa dataset -rain_dataset = torch. utils data TensorDataset (x_ train, Y_train) self.val dataset self..all_ataset torch.
data. { Y_val)
23

---

Published in Transactions on Machine Learning Research (05/2023)
909
N 500 Approx.
24
130
006
064
taxh
Ppact
D = 5
D = 20
D = 30
Figure 5: Approximating Gaussian mixtures with a varying number of Gaussians and dimensions. We plot the test mcan squared error (MSE) loss obtained by approximating Gaussian mixtures f(z; p. E) where μ E Nxd and E IRNxdxd using multiplicative and ReLU networks for different values and N. We report their errors averaged over 20 initialization seeds along with their corresponding 95% confidence intervals.
def trriinddatalaon dataloader (self):
return torch. utils. data. DatttaaDDDaoooeeeeeellll (self. (self.train "rrainddatsse, batch Baich_size=64, shuffle=True
def val (ataallodderreeff)) return forch.utile Datata..aaaaadder(eee (self. wal.lallllaaaaaaa.. batch_size=32 shuffle=False)
def configuree.ptiimzzeeeeeel.
optimizer optim.Adammsell: return optimizer
Adam (etemmddddtssl..pprrrreerrro 1r=1e-3)
parameters
C Additional Experiments
In this section, we add plots regarding approximation in higher dimensions d, shown in Figure 5 We conducted the exact same experiment as in the bottom row of Figure 3 with N 500 and d = 5, 20, 30. As can be seen, both architoctures are able to achieve near error, yet we still see faster convergence using multiplicative networks multilayer perceptrons.
D Proofs
Definition 4. We say a subset U of a Banach space V1 is embedded Banach space V22 if [lullvs S ClIuulv for some fired constant C and for any U.
Lemma 2. Let O and d > 2. Then, Ba is embedded proper subset of Wr...
Proof. Since E B2r,2; have (TR"), and therefore, ||f]| oc. Additionally, by Robert A. Adams 2003) (Theorem 5.2), there exists constant C > 0 such that
Illwa & Ci(l1112 + lf(r2);
where Cj is dependant on r and the dimension d. Therefore, it remains prove that 1f is bounded. For this, use some properties of multivariate function spaces.
24

---

Published in Transactions on Machine Learning Research (05/2023)
We begin with the following claim that will use in advance. Let R d 2 2, we have
d
| = 1wllin
Σ
Σ (al....,ad) as) (wa))
(4)
Ballrr
where w = -1 wi for E Rd By Jensen's inequality,
2
Ifl
Σ
| fll2
S d' Σ
11
a:ja/=r
ac: a/
By Parseval's Tdentity in Rd Albrecht et al.
1996
11e (2 [ F(DD dw
(2 J [(FF)W) dw.
Hence, by 41
Σ |ID'
Σ (2T)d Jud
(W dw
a:/a/=r
a:/a/=r
s (2 [ (FD(wW)
Σ
(on.....os) wwap de
ad/a/=r
(2x)² J (FS(W)) dw.
where the inequality follows from the fact that (ai...aa) 2 Finally, we conclude that
Ilflww- s Ci(llfll +
- C1 (11fll+ (2w)сTτ (F dw) 122
d'
I C2
for some C₁, C2 > O, where the second inequality is due to the definition of Il-Il,,.. as given in equation !
To see that B2r,2 is a proper subset of Wr. we present a prototype function f e 2 such that f $ Berr. Let e > and d, r such that 2r + d. We define the function f E (r²((Rd)) through its Fourier transform:
| S
Ff(w) (o+((()))))
|w| > 1.
Indeed, f E (V2((R))) since:
w (FF(((W)) dw = / JuISI
+ / Ww [Ff(F( lwl>1
du S 1 |w|T1 |دس| (dd+c) dw x0.
gd
We have shown above that 1S2 d' (2= Jga FI (1) dr and so ʃ (r.((Rd). Let that Ff(w) & L1. Since 2r + < a (d +)/2 < d, the following integral diverges
[lW()) = / J [F(W))ld + f/a (F((w))ds [
- [Ff(W)ldw + I luls - (++(e+e) dw
$ Juzz [Ff(w))dew
f |o d 30.
25

---

Published in Transactions on Machine Learning Research (05/2023)
Input layer
Hidden layer
Output layer
(2 11
(w1,,))1 =1
x:
I
41.2
M2.2 -
x22
222
x
glc =
(w1,3)a
eg 60 + =12
p2,2(x)
Figure 6: Illustration of the multiplicative network in Proof of Lemma
where the polynomial degree n = 2.
1 This implies that f does not satisfy the condition [2 Sa ((w) S which is a necessary requirement for membership in B2
Lemma 1. For any polynomial Pa IR + RR of degree n of the form Pn(x) = Ei=o cat", there erists a
mulliplicatiive neural network fPOL: IR3 - R, of depth Ln = O(n) with Gn = O(n) neurons that satisfies In (POL
(I, I, co) = (x()) for co R, and x e R.
Proof. Let (x) Ei=o aa*" be polynomial of degree n and Paç = Eito caat its partial sum up to term i. We construct a network pPOL whose ith layer satisfies:
( (z,, = (#, (x).
We notice that in this construction, the input of the network three-dimennional vector composed of the input and the first coefficient co. We construct the network by specifying its weights as defined in Definition At layer i, the model weights for the three neurons are defined as:
Wi,1 = (1, 0,2 = for (f1.j2) = (1,2), w/, = (0,c,
The rest of the weights are zeros. In Figure 6 we plot the proposed architecture.
We argue that at any layer i 2 O, neuron contains x, neuron 2 contains x²+1 and neuron 3 contains (2)) Let 11+1,1 1,2 1,3 3 be the three neurons in layer i i 1. Let us address each claim individually. Since the only non-zero weight affecting the first neuron in W1411 M4+1,1 Vi = x by the assumption. The only non-zero weight affecting the second neuron appears in di=1,2, the weight affecting the multiplicative interaction, and therefore yt+12 V1,1k,2 x²+1, Lastly, M4+1,3 depends only W/+1.3, and V/+1,3 C+1131,2 + Vi,3 = (x) + G+1x'+1,, == 11.i+((z)) (x). We conclude using the fact that (,, = (x). The third neuron in the final layer then holds the value Pm (I).
J
2, CK > 0 and e E (0,1) be scalers. Then, for any real-valued analytic function MM, M] + IR that is analytically continuable to the ellipse E.M where [K(x)] & Ck, there exists a deep multiplicativv network fMA 1-M, M] + RR (MA stands for 'Multiplicative Analytic") of depth Le = 0 log, log, CR) with G. ( log, log. (k) neurons that satisfies [IMAA(, ((=))I==((MMM) S c. *
Theorem 2. Let M
Proof. Let M 1 2, Cx 0, E (0, and let K be a real-valued analytic function with the required assumptions with respect to Cx. We wish to construct network that approximates K. As a first step, we approximate K with a polynomial hn of degree n 2 2 (to be defined later). Then, we realize h, with a deep multiplicative network as proposed in Lemma [ Since K satisfies the conditions of Theorem for any integer n 2, there exists a polynomial hn of degree n, such that.
hh, K[IL=((-M.M) S -
26

---

Published in Transactions on Machine Learning Research (05/2023)
For the given > 0, with 2, we choose and estimate as follows
CK S
CK
=
loge
log2
log2* 8
<(s
log2* 8
This provides the following relation:
(s 1)
2
gl08a( ()
Cx
= 2 lo0z (loga cta logg
(5)
= 8 losg (loga ( c(o-1)))
In particular,
|/n - (I S Cxa
s-1 I E,
Given that hn is polynomial of degree n, by Lemma (x) = (oo))=pPOpppp (2, co), and achieves the required bound.
there exists frol. and co hn,o such that
Let us now recall Maurey's Theorem proof of Theorem
Pisier 1980- 1981
Vitali D. Milman 1986 which will assist us in the
Lemma (Maurey's theorem). Let be a Hilbert space with norm IH-lvv Suppose there erists Q C V such that for every q E Q, ||allv S b for some > O. Then, for every I in the conver hull of Q and every integer ni 1, there exists Jn in the conver hull of n points in Q and constant c >> -2 11fll, such that Il fll < c.
Theorem 3. Let e E (0,1), M 1,d2 2, and K ::R. :R+C be on analytic kernel that holds the assumptions 2 with respect to C, O, and bounded by constant Dr E (0, on [-dM, dM). Let f be real-valued function in (B), Further, let F M, Mid + C be square-integruble function such that -xx)= = Ji F(w)K(W (w- x) dw. We define OF = [F(W) dw = -I- dw. Then, there R (MBL stands for 'Multiplicative bandlimited") of depth CrCx neurons that satisfies PL f1L S..
of Theorem
exists deep multiplicative network fMB.. B -
L. Togg*
logg CoCx with G. =0 log,
C²
logg
(B). Further, let F(w) [F(w] exp((i((w)) the polar representation of F(w). We may write f through its Fourier representation:
Proof. Let E HK.M
f(x) = Re (F F(w)K(w-x) dw dw)
(L (pexp(if(u))
[((W]
Re
dw
(6)
CF
J-MAMGE Cr((os(((())KN(( siin(((w)) Kr (w
[[()]]
x))
dw,
Cp
where KR, Kr are the real and imaginary parts of K respectively. Since fi-M.M represents f infinite convex combination of functions in
dw = 1, equation 6 [[(w]] OF
QK.M = TMMM=(((comm) (8) xx) sin(3)Kr(w x)] I+| CF, CE
This means that f is the closure of the convex hull of QK,M- Due to the fact that x E [0, 1] and w E [-M, MMd . w E [M]. By the definition of DR, functions in QK. are bounded in the L (B)- norm by DDrDx I 2Cr. Using Lemma 3 for any 6n 1, to be defined at later time, there exist real
27

---

Published in Transactions on Machine Learning Research (05/2023)
coefficients {b,} and {3,}, and vectors wy [-M, 1sj5 [1/x0], such that:
[1/
(e)(x) = Σ
وو (c x) sin(3)) x)],
Σ
1b,1 S Cp.
and
ll - flL2(B) S 2C'e0.
We are now ready to approximate feg (4) using deep multiplicative neural network fMBL. (MBL stands for 'Multiplicative bandlimited") on B. We notice that Kn and K2 are analytic kernels that satisfy the assumptions of Theorem 2 for Ck, 8, M, eo. They can therefore be approximated to en error using networks
fRMA, fIMA of depth and number neurons
Ck ) 60
Geo Lea 0 logg
log2
where RMA stands for 'Real Multiplicative Analytic' and IMA stands for 'Imaginary Multiplicative Analytic! Let us define the multiplicative network (z) by
[1/e6]
MBL (x) Σ
by [/ (3,) fRMA (wy x)) - sin(3,) IMMA (wyj m)
This network has depth Leo O logg s
log2
Ck cn
and Geg 00 loRg
log2 Ck
neurons.
cp
MBI - Sco (2) (co
5
[b (w) KR(wy xB)
Σ
(Mo xx) - Ki(ws L>))
==
2Crco.
that implies
(B) - - I (B) - (c) + (x) [(x)]l<a(B) s 4Cros
where the last incquality is duc to the fact that
||lll>(() ( l913) S ||g1
1/2
Taking 6o c/(4Cp) achieves the sought result.
We further investigate how the constant Cx from Theorem B varies as a function of M and s. Let
K(u) = exp(iu) be an example kernel, u E [-dM, dM). We notice that ad = (s + --2 for s > 2, is the larger axis, and therefore the maximal norm of K on EdM is given by
Cx(s, dM) exp(dM 8t0
2
The resulting network MBI. then has depth
I. = (
dM dMS+58
+ + log
CF
1ogo
2
28

---

Published in Transactions on Machine Learning Research (05/2023)
and
G. 0 (
Cj
dM 8
+ logz CF ( )
log2 8
neurons. In this scenario, we see that both a large band M and a large dimension d will linearly affect the first term.
Theorem Let 2 2, E N, E B2n and E > 0. There erists a deep ReLU network fäs (sland- ing for "ReLU Sobolev") with a depth of L. 2 and G. Olde (2+12r1) neurons, such that f -f [ E.
Proof. Let f B2r.. Similar to the proof of Theorem we define the bandlimiting of f Rd + for given M by
fas F
Let us define F: 1- M] C:
F(W) (2x)a (2 (F))w),
and K(u) expliu). We then have the following identity:
SM(x) = J.MAM K(w)K(w x) dw = J-
(20ja F (() exp(iw . x) dw.
It is casy to that fM E (B). We choose M == (2/c) Using the same derivations as in the proof of Theorem seek to approxinate JM with network jRs ("ReLU Sobolev") such that
lI (881112(8) S e/2.
Once this achieved, we have:
f (1) I |l farlle + Ilfm - 1 11ا(())
I M + c/2 S c.
1 (2x)a JM-MMMJJlFFFM (F(W) dw I 1, where the incquality is due to the definition of B2r.2. The kernel K ((u) cxp(iu) takes as input a = w x, for x E B and w E [-M, Míd Therefore, u E [-dM, dM], and K [-dM,ddM + Since K is an entire function, it continuable to EdM We notice that a adM d4 + 4-1)/2 the larger axis, and therefore the maximal norm of on EdM given by:
We consider that CF = Ji- MM F(w)] du
for any > 2, let us choose
Ck = exp
Further, for any u E R we have K(u)) & 1- Dr. Using Theorem 3.2 from Montanelli Du construct deep ReLU network pRs such that
2021
we can
Il - ,RS (RSIIL2(B)) (L((B) S
e/2
whose depth is
2CFOx
Le < C
log
log 4
exp(dM 1+4 1
2
1
x C2
log,
log2
4
c
(8)
2
12C₂
loga
< Czde
77
29

---

Published in Transactions on Machine Learning Research (05/2023)
for some constants C1 C2. C3 > O. In addition, the number of neurons can be bounded by
CC
G. S C.C.P
log2
é² @log2 4
e
exp(dM 4+4-2 2
4 < Cj E² 1oog2
loge
(9)
120%
d 2
1
logg
6
x Cyde 12+
for some constants C₁ 22 C323 > O.
Corollary 1. Let d 2, r E N, f E W such that | [F (R2) < oo, and e >>> 0. There exists deep ReLU nelwork fas (slanding for "Mulliplicative Sobolev") with depth of L. ((--//) and G. ((-(2((11)) neurons, such that - S C max 21 1FFlll,,,, where C' > 0 is constont dependent on r, d.
Proof. Let f E Wr? such that Ff E Li (RR") and let 0. We define function
d' max f
We will show that f E B2n, and then by applying Theorem on f we will obtain the desired result.
By the definition of the Sobolev space, f (2(R and therefore f E (RR)). We consider Ff,
1
[Fflw)ldw
[Ff(w) dw
(2T) J
(2m)dd max 115 [[F]11]] JRd ||F[11
(2m)dd max { [F 1.
We would like to show that (2m - Saa W ( (r]FF(( (2) 1. Let Rd 2, we have
ad ) (Wa)2
1w/2r = 1wll
w = Σ
(
(10)
m==1
||a||=
where ~ [[= wit for a E Rd In addition,
11 =
Σ
| flla
2
Σ
|D
ac/a|=r
a:/a|=r
By Parseval's Identity in Rd Albrecht et al.
1996
D = (2 JRd
1
F(D (w)) du
/
((F)(w)) dw.
(2m)d R
Hence, by 10
(2m)d I
Σ 10
Σ
J (FF)())) dw
=:
a:lat a:1a/=r
((F)(w)
Σ
a1..... an) wapp dw
(2 Easaa (ay.".aa) Rc
0:/o/er
(27)) [ [Ff(w)) dw,
30

---

Published in Transactions on Machine Learning Research (05/2023)
We then arrive at the following inequality:
(2 d' 1 [= dw S 1fl:22
Finally,
1 (2 )d
| 2 (rFFf(w) = (2 max {/ [[]]]i]] Jee
1s
max 2- [F S 1.
31


Reviews:
[{"review_id": "49hKOQy3j8", "reviewer": "Reviewer_hvgK", "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:\nThe paper is well-written and the results are clearly stated and compared to the existing methods. The analysis, to my knowledge, is novel and the improvement over traditional ReLU networks is noteworthy.\n\nWeaknesses:\nThe only major weakness is the simulations which are limited to Chebyshev polynomials which can be interpreted as simple validation of Lemma 1. It is expected to see simulations verifying the main theorems of the paper.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 considers the multiplicative neural networks where instead of using non-linear activation function at each layer, the neurons are connected with simple multiplication operations. The authors explores how well the multiplicative neural networks can approximate smooth functions on Sobolev space as well as band-limited smooth functions. The authors show that compared to the standard ReLU neural networks, with the same error tolerance, the multiplicative NNs can approximate smooth or bandlimited functions with fewer number of layers or fewer neurons. \nTo achieve these results, the authors first show that multiplicative NNs can efficiently represent polynomial functions and then use the existing results on approximating functions with polynomials or kernels to achieve the desired results.\nThis potentially can shed some light on the success of the attention blocks and transformers as these models have some forms of multiplicative layers in their architecture.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors should consider adding simulations to support their theoretical results (Thm. 2-4) which I believe can considerably improve the quality of the paper.\n\nMoreover, there are a few typos or ambiguities in the manuscript:\n1. Problem setup, first equation: This formulation implies that a single best approximating function from H is used to approximate all functions in U. It seems that the authors meant to consider a separate approximator for each function in U.\n2. Definition 2: worth to mention that $j_1$ and $j_2$ can be any arbitrary index depending on $j$ and $i$.\n3. The paragraph after definition 3 is incorrect. Note that as $s\\rightarrow \\infty$, the Bernstein s-ellipse converges to a circle. As $s$ decreases, the ellipse becomes more elongated. Moreover, it is not necessary to limit $M\\geq1$. $M>0$ would be enough.\n4. proof of Thm. 5, equation 2, the reason for the third inequality is not clear.\n5. Experiments section: to avoid bad local minima, did the authors run their simulations multiple times with different seeds? If so, how many times? otherwise, to have more stable results, would be good to reiterate the simulations multiple times and show the mean and variance of the MSE. \n6. The line after equation 4, the definition of $\\omega^{\\alpha}$ should be corrected as $\\omega^{\\alpha}=\\Pi_{i=1}^d \\omega_i^{\\alpha_i}$.\n7. proof of Thm. 3, last equation, duplicate $||g||_{L^{\\infty}(B)}$?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gWVGKtgoYy", "reviewer": "Reviewer_YdBi", "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": "The paper is relatively well organized, with some technical details a bit hard to follow. But this reviewer thinks that it is the complication of the content itself, such as Sobolev function, Bernstein s-ellipse, etc.\n\nMost part of the results seem correct. To better highlight the contribution, it is suggested that some key technical steps in proofs can be explained.\n\n====================== Weaknesses ========================\n\nThe target function classes studied in the paper is purely technical. On the one hand, the function class is relatively small so that whose approximation does not suffer from the curse of dimensionality. On the other hand, these function classes give the impression that they are studied because people know how to approximate them.\n\nCompared to ReLU networks, multiplicative networks are automatically capable of exactly implementing polynomials without any error. From a theoretical standpoint, the approximation theory of using multiplicative networks seem to be thin and the advantage over ReLU networks is highly tied to the activation function. This limits the contribution of the paper.\n\nA minor point is there is no lower bound established. Are the obtained approximation rates optimal?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 establishes approximation guarantees of neural networks. The focus is on the advantage of multiplicative activation functions compared to ReLU activations. In particular, the obtained approximation rates of multiplicative activation improve those of ReLU activation by a factor of dimension or logarithmic terms. In addition to theoretical results, the paper provides empirical study of demonstrating trained neural networks for regression tasks. The MSE of multiplicative networks outperforms ReLU networks, further supporting the theory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In Definition 2, what is indexes $j_1, j_2$?\n\nSelf-Attention can be seen as an example of multiplicative networks, but the structure of the presentation makes self-attention looks like another network architecture.\n\nFollowing Definition 3, why taking $s = 2$ corresponds to a circle? If I am not misunderstanding, with $s = 2$, the two semi-axes are not equal.\n\nFollowing Theorem 2, when comparing to Montanelli et al., (2021), the improvement is a logarithmic factor in terms of the approximation error. Why this leads to an exponentially faster convergence to the target function?\n\nIn all the experiments, MSE is plotted of multiplicative and ReLU networks, respectively. However, there is a gap between the MSE and the approximation accuracy of networks. In fact, MSE consists of both bias and variance of the learner model. A smaller MSE not necessarily implies smaller approximation error. This can be made clear in verbal description. Yet the experiments still stand to demonstrate the advantage of multiplicative networks.\n\nSome recent references are missing in introduction. Approximation with structured input space or target function space: \"Efficient approximation of deep relu networks for functions on low dimensional manifolds\", \"Deep Network Approximation in Terms of Intrinsic Parameters\", \"Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space\". Please also check references therein.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yHJ7jJWXt7", "reviewer": "Reviewer_TGTp", "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\n - The paper is well organized and easy to follow.\n\n - The paper is well motivated and gives examples of where a multiplicative layer is used in practice and concerns with types of functions that can be better approximated using a multiplicative layer.\n\nWeaknesses:\n \n- I appreciate the theoretical analysis and the findings in this work. However, I feel that it lacks computational part, that in my opinion should be included in the paper, even in the form of several simple examples. For instance, I think that the paper will benefit from a short experimental section where the authors provide an example function that is hard to approximate using a standard neural layer vs a multiplicative layer.\n\n- The authors may want to add some additional references where multiplicative layers are used in practice (please see below).\n\nQuestion to the authors:\n - In page 6, you mention \"we\ndo not incorporate non-linearities (ReLU activations) between the intermediate layers\". \nCan you please elaborate on this point? why does a multiplicative linear has to be linear? is it an assumption of your paper, or is there a fundamental restriction that requires having a linear layer?\n\nMinor comments:\n\n - Section 2.1: the last two sentences can be merged. they are quite repetitive.\n\n - Page 5, above equation (1): you may want to directly refer the reader to the appendix section where the Lemma is presented.\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 authors theoretically analyse the approximation power of multiplicative neural layers compared to standard neural layers, building on previous results that are cited in the paper.\n\nThe provided theorems and discussion in this paper extends previous findings to additional types of neural networks, as well as to different types of functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please consider adding an experimental section that shows the difference between the approximation abilities of multiplicative vs standard neural layers.\n\nPlease consider adding the following background papers, in the context of using multiplicative layers in learning systems:\n - Stable architectures for deep neural networks\n -  MULTIPLICATIVE INTERACTIONS AND WHERE TO FIND THEM\n - PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations", "broader_impact_concerns": "I do not find any ethical issues in this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies an important problem and makes interesting theoretical contributions. 

The paper was reviewed by three expert reviewers. Even though two reviewers are satisfied with the author's response, one reviewer still had concerns even after the discussion period. As such, I recommend "Accept with revision", which would provide additional time for authors to address the concerns raised by this reviewer.

In particular, the reviewer is not satisfied with authors' response; yet, they acknowledge that some of their concerns are addressed in the revision. The reviewer's major concern is that the function classes do not show a clear connection to practice. 

I recommend authors to explore some practical settings/examples to demonstrate their results. After this change, the paper will be suitable for publication at TMLR.

Best, AC 

Decision: Accept (poster)