# Exploring the Approximation Capabilities of Multiplicative Neural Networks
for Smooth Functions

Ido Ben-Shaul<EMAIL_ADDRESS>
Department of Applied Mathematics
Tel-Aviv University, Israel
eBay Research Tomer Galanti<EMAIL_ADDRESS>
Massachusetts Institute of Technology (MIT)
Cambridge, MA, USA
Shai Dekel<EMAIL_ADDRESS>
Department of Applied Mathematics
Tel-Aviv University, Israel

###### 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.

##  1 Introduction

Deep learning with large neural networks has seen tremendous success in
solving a wide range of tasks in recent years, including image classification
(He et al., 2016; Dosovitskiy et al., 2021; Zhai et al., 2021), language
processing (Vaswani et al., 2017; Devlin et al., 2019; Brown et al., 2020),
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, 2015; Trask et al., 2018), such as self-attention
layers (Vaswani et al., 2017) and hypernetworks (Ha et al., 2016; Krueger et
al., 2017; Littwin & Wolf, 2019), are particularly effective. For example,
self-attention layers have been widely successful in computer vision
(Dosovitskiy et al., 2021; Zhai et al., 2021) and language processing (Cheng
et al., 2016; Parikh et al., 2016; Paulus et al., 2017; Vaswani et al., 2017).
It has also been shown that one can achieve reasonable performance with
Transformers even without applying non-linear activation functions (Levine et
al., 2020). Additionally, hypernetworks, which use multiplication to generate
network weights seem to improve the performance of neural networks on various
meta-learning tasks (von Oswald et al., 2020; Littwin & Wolf, 2019; Bensadoun
et al., 2021). However, the benefits of multiplication layers are not well
understood from a theoretical perspective.

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 to approximate a given function within a given error
tolerance using a specific architecture. A classic result in the theory of
deep learning shows that neural networks can approximate any smooth target
function, known as the universal approximation property, with as few as one
hidden layer (Cybenko, 1989; Hornik et al., 1989; ichi Funahashi, 1989; Leshno
et al., 1991). 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.

Previous work has demonstrated that functions in Sobolev spaces can be
approximated by a 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 $\epsilon$ in the
$L_{\infty}$ norm scales as $\mathcal{O}(\epsilon^{-d/r})$, where $d$ is the
input dimension, $r$ is the smoothness degree of the target function, and
$\epsilon>0$ is the error rate. This raises the question of whether the curse
of dimensionality, 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 $\epsilon$ requires at least
$\Omega(\epsilon^{-d/r})$ parameters in the $L_{\infty}$ 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 $L_{\infty}$ 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;
Blanchard & Bennouna, 2022b; Galanti & Wolf, 2020) have investigated the
approximation capabilities of neural networks in representing other classes of
functions with weaker notions of distance, such as the $L_{2}$ 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 $L_{\infty}$ distance up to error $\epsilon$ using deep
neural networks with $\mathcal{O}(d\epsilon^{-2/r})$ neurons. Other structural
constraints have been applied to functions with structured input spaces
(Mhaskar, 2010; Nakada & Imaizumi, 2022; Schmidt-Hieber, 2019), compositions
of functions (Kohler & Krzyżak, 2017), piecewise 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. (2021) 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 $\epsilon$ using
2-layer networks with $\mathcal{O}(\epsilon^{-2})$ neurons. Another line of
research has considered spectral conditions on the function space, allowing
functions to be expressed as infinite-width limits of shallow networks
(Barron, 1991; Klusowski & Barron, 2016). In (Blanchard & Bennouna, 2022b)
they considered the space of Korobov functions, which are functions that are
practically useful for solving partial differential equations (PDEs). They
showed any Korobov function can be approximated up to error $\epsilon$ in
$L_{2}$ distance with a 2-layer neural network with ReLU activation function
with $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon)^{1.5(d-1)+1})$ and with a
$\mathcal{O}(\log(d))$-depth network with
$\mathcal{O}(\epsilon^{-0.5}\log(1/\epsilon)^{1.5(d-1)+1})$ neurons.

In a recent paper, Montanelli et al. (2021) provided approximation guarantees
were established for generalized bandlimited functions. These functions are
commonly used to model signals that have a finite range of frequencies (e.g.,
waves, video, and audio signals), which is known as a finite bandwidth. The
solutions to many PDEs in physics are bandlimited functions, as the physical
phenomena modeled by these PDEs typically have a finite range of frequencies.
For example, the solutions to the wave equation, which models the propagation
of waves, are bandlimited functions. In (Montanelli et al., 2021), it was
shown that any bandlimited function can be approximated to within error
$\epsilon$ using a ReLU neural network of depth
$\mathcal{O}(\log^{2}(1/\epsilon))$ with
$\mathcal{O}(\epsilon^{-2}\log^{2}(1/\epsilon))$ neurons with the $L_{2}$
distance.

In this paper, we study the approximation abilities of multiplicative neural
network architectures with the $L_{2}$ distance. In particular, we prove that
a multiplicative neural network of depth
$\mathcal{O}(\log({\textstyle\frac{1}{\epsilon}}))$ with
$\mathcal{O}(\epsilon^{-2}\log({\textstyle\frac{1}{\epsilon}}))$ neurons can
approximate any generalized bandlimited function up to an error of $\epsilon$
(with constants depending on the dimension and on the band). Additionally, we
also study the approximation guarantees of neural networks for approximating
functions in Sobolev-Type balls of order $r$. We show that for the same error
tolerance $\epsilon$, multiplicative neural networks can approximate these
functions with depth $\mathcal{O}(d^{2}\epsilon^{-1/r})$ and
$\mathcal{O}(d^{2}\epsilon^{-(1+1/r)})$ neurons, while standard ReLU neural
networks require depth $\mathcal{O}(d^{2}\epsilon^{-2/r})$ and
$\mathcal{O}(d^{2}\epsilon^{-(2+2/r)})$ neurons. These results demonstrate the
superior performance of multiplicative gates compared to standard fully-
connected layers. In Table 1 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 | Depth | Reference
---|---|---|---|---
$\mathcal{W}^{r,p}$ |  $C^{\infty}$, non-poly | $\mathcal{O}(\epsilon^{-d/r})$ | $\mathcal{O}(1)$ | (Mhaskar, 1996)
$\mathcal{W}^{r,\infty}$ | ReLU | $\mathcal{O}(\epsilon^{-d/r}\log{\frac{1}{\epsilon}})$ | $\mathcal{O}(\log{\frac{1}{\epsilon}})$ | (Yarotsky, 2017)
Bandlimited functions | ReLU | $\mathcal{O}(\epsilon^{-2}\log^{2}\frac{1}{\epsilon})$ | $\mathcal{O}(\log^{2}{\frac{1}{\epsilon}})$ | (Montanelli et al., 2021)
Bandlimited functions | Multiplicative | $\mathcal{O}(\epsilon^{-2}\log\frac{1}{\epsilon})$ | $\mathcal{O}(\log{\frac{1}{\epsilon}})$ | This paper
$\mathcal{B}_{2r,2}\subsetneq\mathcal{W}^{r,2}$ | ReLU | $\mathcal{O}(d^{2}\epsilon^{-(2+2/r)})$ | $\mathcal{O}(d^{2}\epsilon^{-2/r})$ | This paper
$\mathcal{B}_{2r,2}\subsetneq\mathcal{W}^{r,2}$ | Multiplicative | $\mathcal{O}(d\epsilon^{-(2+1/r)})$ | $\mathcal{O}(d\epsilon^{-1/r})$ | This paper
$\mathcal{B}_{1,1}$ | Sigmodial | $\mathcal{O}(d\epsilon^{-2})$ | $\mathcal{O}(1)$ | (Barron, 1993)

Table 1: Approximation results for Sobolev $\mathcal{W}^{r,p}$, Bandlimited
and $\mathcal{B}_{2r,2}$ functions by ReLU and multiplicative neural networks.
The number of neurons and the depth are given in $\mathcal{O}$ notation.

##  2 Problem Setup

We are interested in determining how complex (i.e., number of trainable
parameters, number of neurons and layers) a model ought to be in order to
theoretically guarantee approximation of an unknown target function $f$ up to
a given approximation error $\epsilon>0$.

Formally, we consider a Banach space of functions $\mathcal{V}$ (for example,
$L_{p}([0,1]^{d})$), equipped with a norm $\|\cdot\|_{\mathcal{V}}$ (for
example, $\|\cdot\|_{L_{p}([0,1]^{d})}$), and a set of target functions
$\mathcal{U}\subseteq\mathcal{V}$. We also consider a set of approximators
$\mathcal{H}$ and seek to quantify the ability of these approximators to
approximate $\mathcal{U}$ using the following quantity

$d_{\mathcal{V}}(\mathcal{H},\mathcal{U})~{}=~{}\inf_{\hat{f}\in\mathcal{H}}{\sup_{f\in\mathcal{U}}\|\hat{f}-f\|_{\mathcal{V}}},$

which measures the maximal approximation error for approximating a target
function $f\in\mathcal{U}$ using candidates $\hat{f}$ from $\mathcal{H}$.
Typically, $\mathcal{H}$ is a parametric set of functions (e.g., neural
networks of a certain architecture) and we denote by
$\hat{f}_{\theta}\in\mathcal{H}$ a function that is parameterized by a vector
of parameters $\theta\in\mathbb{R}^{N}$. For simplicity, we avoid writing
$\theta$ 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, as demonstrated in Theorem 7.2 in (Devroye et al.,
1996). As a result, we often consider specific spaces of target functions that
satisfy certain smoothness assumptions in order to obtain non-trivial results.
In this work, we focus specifically on target functions $\mathcal{U}$ that
satisfy the following smoothness assumptions. In this paper, we will focus on
approximating functions on the unit cube $B=[0,1]^{d}$, with $\lvert
B\rvert=1$, the volume of $B$.

Sobolev spaces.  Sobolev spaces are one of the most extensively studied
classes of functions in approximation theory (DeVore & Lorentz, 1993;
Yarotsky, 2017; Liang & Srikant, 2017). These spaces consist of smooth
functions with bounded derivatives up to a certain order and are particularly
useful in the study of partial differential equations (PDEs).

We first define the $L_{p}$ norm of a given function $f:\Omega\to\mathbb{R}$
as $\|f\|_{L_{p}(\Omega)}=(\textstyle\int_{\Omega}\lvert
f(x)\rvert^{p}~{}\textnormal{d}x)^{1/p}$, where $\Omega$ is a measurable space
equipped with a Sigma-algebra $\Sigma$ and a measure $\mu$. A function $f$ is
said to be in $L_{p}(\Omega)$ if $\|f\|_{L_{p}(\Omega)}<\infty$.

Let $r\in\mathbb{N}$ and $p\in[1,\infty)$. The Sobolev space
$\mathcal{W}^{r,p}\left(B\right)$ consists of functions
$f:B\rightarrow\mathbb{R}$ with $r$-distributional derivatives in $L_{p}$. The
Sobolev norm $\|\cdot\|_{\mathcal{W}^{r,p}(B)}$ is defined as

$\|f\|_{\mathcal{W}^{r,p}(B)}~{}=~{}\sum_{\alpha:\lvert\alpha\rvert_{1}\leq
r}\|D^{\alpha}f\|_{L_{p}(B)},$

where
$\alpha=(\alpha_{1},\dots,\alpha_{d})\in\\{0,\dots,r\\}^{d},\lvert\alpha\rvert_{1}=\alpha_{1}+\dots+\alpha_{d}$,
and $D^{\alpha}f$ is the respective distributional derivative. When
$p=\infty$, the essential supremum norm is used. We also present the semi-
norm:

$\lvert
f\rvert_{r,p}~{}=~{}\sum_{\alpha~{}:~{}\lvert\alpha\rvert=r}\|D^{\alpha}f(x)\|_{L_{p}(B)}.$

Classic results in the literature show that the number of parameters needed to
approximate functions in $\mathcal{W}^{r,\infty}$ up to error $\epsilon$ is
lower bounded by $\Omega(\epsilon^{-d/r})$ (DeVore et al., 1989). This
exponential dependence on $d$ is known as the “curse of dimensionality”.

Generalized Bandlimited functions.  Generalized bandlimited functions are
functions whose spectrum, or the set of frequencies that make up the function,
is limited to a 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 their generalized Fourier
transform given by an analytic function $K:\mathbb{R}\to\mathbb{C}$ (known as
the kernel) and a scalar $M\geq 1$ (the band). Formally, for a given function
$f:\mathbb{R}^{d}\to\mathbb{R}$, we denote the set of all functions
$F:[-M,M]^{d}\to\mathbb{C}$ that retrieve $f$ from the frequencies
$\omega\in[-M,M]^{d}$ using the kernel $K$ as follows:

$S_{f,K}~{}=~{}\left\\{F:[-M,M]^{d}\to\mathbb{R}\mid
f(x)=\textstyle\int_{[-M,M]^{d}}F(\omega)K(\omega\cdot
x)~{}\textnormal{d}\omega\right\\}.$

We define
$F_{f}=\operatorname*{arg\,min}_{F\in{S_{f,K}}}\|F\|_{L^{2}([-M,M]^{d})}$ to
be the smallest $L_{2}$-norm function in $S_{f,K}$. For instance, when
$K(x)=\exp(ix)$, the function $F_{f}$ corresponds to the normalized standard
Fourier transform of $f$, which is given by
$F={\textstyle\frac{1}{(2\pi)^{d}}}(\mathcal{F}f)(\omega)={\textstyle\frac{1}{(2\pi)^{d}}}\int_{\mathbb{R}^{d}}f(x)\exp(-i\omega\cdot
x)~{}\textnormal{d}x$.

The space $\mathcal{H}_{K,M}(B)$ of generalized bandlimited functions is a
Hilbert space of functions that can be represented as a weighted sum of the
function $K$ over a finite domain. This space is equipped with an inner
product and a norm, which allow us to measure the similarity and magnitude of
these functions, respectively. We define $\mathcal{H}_{K,M}(B)$ as the
functions $f:B\rightarrow\mathbb{R}$ such that

$\mathcal{H}_{K,M}(B)~{}=~{}\left\\{\forall x\in
B,f(x)=\textstyle\int_{[-M,M]^{d}}{F(\omega)K(\omega\cdot
x)~{}\textnormal{d}\omega}\mid F:[-M,M]^{d}\rightarrow\mathbb{C}\text{ is in
}L^{2}([-M,M]^{d})\right\\}.$

The inner product and norm in this space are defined as follows: $\langle
f,g\rangle_{\mathcal{H}_{K,M}(B)}=\textstyle\int_{[-M,M]^{d}}F_{f}(\omega)\overline{F_{g}}(\omega)~{}\textnormal{d}\omega$
and norm $\|f\|_{\mathcal{H}_{K,M}(B)}=\|F_{f}\|_{L^{2}{([-M,M]^{d})}}$.

One of the key properties of generalized bandlimited functions is that they
can be completely reconstructed from a discrete set of samples. This is known
as the Shannon-Nyquist theorem (Shannon, 1984), and it is an important result
in the field of signal processing and communication. An interesting
consequence of this theorem is that even in high-dimensions, where seemingly
unpredictable geometrical phenomena may occur (e.g. Blum et al. (2020),
Chapter 2), still perfectly reconstruct a function given it’s values at the
Nyquist frequency. For more details, see Appendix A.

Sobolev-Type Balls.  Sobolev-Type balls are sets of functions that satisfy
smoothness constraints on higher-order derivatives (Barron, 1993; Jones, 1992;
Pinkus, 1985; Wahba, 1990; Blanchard & Bennouna, 2022a). One such constraint
is that the magnitude of the function’s Fourier transform,
$\lvert\mathcal{F}f(\omega)\rvert$, decays fast enough as $\lvert\omega\rvert$
approaches infinity. These constraints are imposed by comparing the magnitude
of the Fourier transform of the function, $\mathcal{F}f(\omega)$, with the
magnitude of $|\omega|^{r}$ for some number $r>0$. In this paper we define a
generalized form of Sobolev-type balls:

$\mathcal{B}_{r,\rho}~{}=~{}\left\\{f:\mathbb{R}^{d}\rightarrow\mathbb{R},f\in
L_{2}(\mathbb{R}^{d}):\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}\lvert(\mathcal{F}f)(\omega)\rvert~{}\textnormal{d}\omega,\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}\lvert\omega\rvert^{r}\lvert(\mathcal{F}f)(\omega)\rvert^{\rho}~{}\textnormal{d}\omega\leq
1\right\\}.$

In (Barron, 1993), they explored the ability of neural networks to approximate
functions in the space $P_{1}=\\{f\in
L_{2}(\mathbb{R}^{d})\mid\int_{\mathbb{R}^{d}}\lvert\omega\rvert\lvert(\mathcal{F}f)(\omega)\rvert<\infty\\}$.
We now demonstrate that any function in $P_{1}$ has a normalized
representation in $\mathcal{B}_{1,1}$. For this, we show that the conditions
on $P_{1}$ allow us to bound $\|\mathcal{F}f\|_{L_{1}(\mathbb{R}^{d})}$.
Namely,

$\displaystyle\int_{\mathbb{R}^{d}}\lvert(\mathcal{F}f)(\omega)\rvert~{}\textnormal{d}\omega{}$
$\displaystyle=~{}\int_{[-1,1]^{d}}\lvert(\mathcal{F}f)(\omega)\rvert~{}\textnormal{d}\omega+\int_{\mathbb{R}^{d}{\backslash}[-1,1]^{d}}\lvert(\mathcal{F}f)(\omega)\rvert~{}\textnormal{d}\omega$
$\displaystyle\leq~{}C_{1}\left(\int_{[-1,1]^{d}}\lvert(\mathcal{F}f)(\omega)\rvert^{2}~{}\textnormal{d}\omega\right)^{1/2}+\int_{\mathbb{R}^{d}\backslash[-1,1]^{d}}\lvert\omega\rvert\lvert(\mathcal{F}f)(\omega)\rvert~{}\textnormal{d}\omega$
$\displaystyle\leq~{}C_{1}\|f\|_{2}+\int_{\mathbb{R}^{d}}\lvert\omega\rvert\lvert(\mathcal{F}f)(\omega)\rvert~{}\textnormal{d}\omega,$

for $C_{1}>0$. Therefore, any function in the space $P_{1}$ can be scaled to a
function in $\mathcal{B}_{1,1}$. Specifically, they showed that sigmoidal
neural networks with a bounded depth and $\mathcal{O}(d\epsilon^{-2})$ neurons
can approximate such functions with error at most $\epsilon$.

In this paper we will focus on the space $\mathcal{B}_{2r,2}$. In Lemma 2 in
the appendix we show that this space is embedded as a proper subspace of
$\mathcal{W}^{r,2}$, with the following norm:

$\|f\|_{\mathcal{B}_{2r,2}}~{}=~{}\left(\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}(1+\lvert\omega\rvert^{2r})\lvert(\mathcal{F}f)(\omega)\rvert^{2}~{}\textnormal{d}\omega\right)^{1/2}.$
(1)

It is worth mentioning that Pinkus (1985) showed that using traditional basis
functions, functions of the space $P_{2}=\\{f\in
L_{2}(\mathbb{R}^{d})\mid\int_{\mathbb{R}^{d}}\lvert\omega\rvert^{2r}\lvert(\mathcal{F}f)(\omega)\rvert^{2}<\infty\\}$
may be approximated with error at most $\epsilon$ using
$\mathcal{O}(\epsilon^{-d/2r})$ parameters. In this paper, we show that by
enforcing an additional constraint on the $L_{1}$ norm of the Fourier
coefficients, we can circumvent exponential dependence on the dimension $d$.

###  2.2 Neural Network Architectures

In the previous section, we described a setting in which a class of candidate
functions $\mathcal{H}$ serve as approximators to a class of target functions
$\mathcal{U}$. In this work, we compare the approximation guarantees of
standard multi-layered perceptrons and a generic set of neural networks that
incorporate multiplication operations. Our goal is to understand whether
multiplication layers can provide better guarantees to approximate bandlimited
functions and members of $\mathcal{B}_{2r,2}$.

Multilayered perceptrons.  A multilayered perceptron is a type of neural
network architecture that consists of $L$ layers of linear transformations
interspersed with element-wise non-linear activation functions (e.g., the ReLU
function). Typically, the last layer does not include a non-linear activation.

######  Definition 1 (Multilayered perceptron).

A multilayered perceptron is a function
$f=y_{L,1}:\mathbb{R}^{p_{0}}\to\mathbb{R}$ defined by a set of univariate
functions $\bigcup^{L}_{i=0}\\{y_{i,j}\\}^{p_{i}}_{j=1}$. Each function
$y_{i,j}:\mathbb{R}^{p_{0}}\to\mathbb{R}$ (also known as a neuron) is
recursively computed in the following manner

$\displaystyle y_{L,j}(x){}$ $\displaystyle=~{}\langle
w_{L,j},y_{L-1}(x)\rangle+b_{L,j}$ $\displaystyle y_{i,j}(x){}$
$\displaystyle=~{}\sigma(\langle w_{i,j},y_{i-1}(x)\rangle+b_{i,j})$
$\displaystyle y_{0,j}(x){}$ $\displaystyle=~{}x_{j},$

where $i\in[L-1]$, $j\in[p_{i}]$, and $w_{i,j}\in\mathbb{R}^{p_{i-1}}$ and
$b_{i,j}\in\mathbb{R}$ are the weights and a bias of the neuron $y_{i,j}$ and
$y_{i}=(y_{1},\dots,y_{p_{i}})$. The function $\sigma:\mathbb{R}\to\mathbb{R}$
is a non-linear activation function.

In this work, we focus on neural networks with ReLU activations, which are
defined as $\sigma(x)=\max(0,x)$. However, it is worth noting that other
activation functions have been proposed in the literature, such as sigmoidal
functions that are measurable functions $\eta$ that satisfy
$\eta(x)\rightarrow 0$ as $x\rightarrow-\infty$ and $\eta(x)\rightarrow 1$ as
$x\rightarrow\infty$.

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 multiplications
between neurons sufficient to substitute the non-linear activations in
multilayered perceptrons?

######  Definition 2 (Multiplicative network).

A multiplicative neural network is a function
$f=y_{L,1}:\mathbb{R}^{p_{0}}\to\mathbb{R}$ defined by a set of univariate
functions $\bigcup^{L}_{i=1}\\{y_{i,j}\\}^{p_{i}}_{j=1}$. Each function
$y_{i,j}:\mathbb{R}^{p_{0}}\to\mathbb{R}$ (also known as a neuron) is
recursively computed in the following manner

$\displaystyle y_{i,j}(x){}$ $\displaystyle=~{}\langle
w_{i,j},y_{i-1}(x)\rangle+a_{i,j}y_{i-1,j_{1}}(x)y_{i-1,j_{2}}(x)+b_{i,j}$
$\displaystyle y_{0,j}(x){}$ $\displaystyle=~{}x_{j},$

where $a_{i,j},b_{i,j}\in\mathbb{R}$, $w_{i,j}\in\mathbb{R}^{p_{i-1}}$ are
trainable parameters and $y_{i}=(y_{1},\dots,y_{p_{i}})$.

A multiplicative network differs from standard multilayered perceptrons in two
main ways. First, we do not incorporate non-linearities (ReLU activations)
between the intermediate layers. In addition, each neuron incorporates a
multiplication gate between two preceding neurons. The total number of
trainable parameters in a multiplicative layer is $p_{i+1}p_{i}+2p_{i}$, which
is $p_{i}$ more parameters than a fully-connected layer. Following Yarotsky
(2017); Blanchard & Bennouna (2022a) we measure the complexity of a neural
network using its depth $L$ and the number of neurons
$G=\sum^{L-1}_{i=1}p_{i}$ it includes.

Self-Attention and multiplicative layers.  Let us describe a single-headed
self-attention operation in the original Transformer (Vaswani et al., 2017).
Each layer $i\in[L]$ of a depth-$L$ Transformer encoder is defined as follows.
The input to the $i$th layer is a sequence of $N$ tokens, denoted by
$x_{i}=\\{x_{i,j}\\}_{j=1}^{N}$, where each $x_{i,j}\in\mathbb{R}^{d_{x}}$
represents the $j$th token of the $i$th layer. To compute the output of the
$i$th layer at a particular position $e\in[N]$, we use the following formula:

$f_{\textnormal{SA}}^{i,e}(x_{i})~{}=~{}\sum_{j=1}^{N}\textnormal{softmax}_{j}\left({\textstyle\frac{1}{\sqrt{d_{a}}}}\langle
W^{Q,i}x_{i,e},W^{K,i}x_{i,e}\rangle\right)W^{V,i}x_{i,j},$

where
$\textnormal{softmax}_{j}(f(x))={\exp(f(x)_{j})}/{\sum_{j^{\prime}}\exp(f(x)_{j^{\prime}})}$
is the softmax operator, and the trainable weight matrices $W^{K,i}$,
$W^{Q,i}$, $W^{V,i}\in\mathbb{R}^{d_{a}\times d_{x}}$ convert the
representation from its dimension $d_{x}$ into the attention dimension
$d_{a}=d_{x}$, creating ‘Key’, ‘Query’, and ‘Value’ representations, resp. As
can be seen, the self-attention layers use multiplicative connections when
computing the following inner product $\langle
W^{Q,i}x_{i,e},W^{K,i}x_{i,e}\rangle$. This operation computes multiplications
between the coordinates of transformations of the same token $x_{i,e}$. In
other words, it can be thought of as computing a multiplicative layer on an
input vector $x_{i,e}$. As a side note, in addition to self-attention layers,
transformers also incorporate commonly used layers such as 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
$\mathcal{B}_{2r,2}$ without suffering from the curse of dimensionality.
Specifically, we prove the following lemma:

######  Lemma 1.

For any polynomial $p_{n}:\mathbb{R}\rightarrow\mathbb{R}$ of degree $n$ of
the form $p_{n}(x)=\sum_{k=0}^{n}c_{k}x^{k}$, there exists a multiplicative
neural network $f^{\textnormal{POL}}_{n}:\mathbb{R}^{3}\to\mathbb{R}$, of
depth $L_{n}=\mathcal{O}(n)$ with $G_{n}=\mathcal{O}(n)$ neurons that
satisfies $f^{\textnormal{POL}}_{n}(x,x,c_{0})=p_{n}(x)$ for
$c_{0}\in\mathbb{R}$, and $x\in\mathbb{R}$.

With this lemma in hand, we can show how to use multiplicative networks to
approximate analytic kernel functions $K:\mathbb{R}\rightarrow\mathbb{C}$ by
leveraging their ability to represent polynomials. By approximating a certain
class of polynomials, we can demonstrate how to use these networks to
approximate analytic kernels. Once we have the ability to approximate analytic
kernels, we can use Maurey’s Theorem (see Lemma 3) to express any function
$f\in\mathcal{H}_{M}$ as a finite sum of kernel superpositions, and construct
a network that approximates this sum.

Approximating of real-valued analytic functions.  In this section, we show how
to approximate certain real-valued 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\geq 1$, $s>1$ be two scalars. The Bernstein s-ellipse on $[-M,M]$ is
defined as follows

$E_{s}^{M}~{}=~{}\left\\{x+iy\in\mathbb{C}:{\textstyle\frac{x^{2}}{(a_{s}^{M})^{2}}}+{\textstyle\frac{y^{2}}{(b_{s}^{M})^{2}}}=1\right\\},$

whose semi-major and semi-minor axes are
$a_{s}^{M}=M{\textstyle\frac{s+s^{-1}}{2}}$ and
$b_{s}^{M}=M{\textstyle\frac{s-s^{-1}}{2}}$.

The parameter $s$ controls the shape of the ellipse, and the parameter $M$
determines its size. For example, when $s=2$, the ellipse is a circle centered
at the origin with a radius $M$. As $s$ increases, the ellipse becomes more
elongated and its semi-minor axis decreases. The semi-major and semi-minor
axes of the ellipse determine its maximal and minimal values, respectively.
Before stating our result in Theorem 2, we recall the following theorem of
Trefethen (2019):

######  Theorem 1 (Theorem 8.2 of Trefethen (2019)).

Let $M>0,s>2$ be scalars and $K:[-M,M]\to\mathbb{R}$ be an analytic function
that is analytically continuable to the ellipse $E_{s}^{M}$, where it
satisfies $\sup_{x\in E_{s}^{M}}\lvert K(x)\rvert\leq C_{K}$ for some constant
$C_{K}>0$. For every $n\in\mathbb{N}$, there exists a polynomial
$h_{n}:\mathbb{R}\rightarrow\mathbb{C}$ of degree $n$, such that,

$\|h_{n}-K\|_{L^{\infty}([-M,M])}~{}\leq~{}\frac{2C_{K}s^{-n}}{s-1}.$

Theorem 1 states that any analytic function $K$ that is bounded on the
Bernstein s-ellipse $E_{s}^{M}$ can be accurately approximated by a polynomial
$h_{n}$ of degree $n$, with the error decreasing exponentially as the degree
$n$ increases.

As we show next, the use of multiplication layers in neural networks can
improve the efficiency of function approximation in certain cases. The
following theorem shows that deep multiplicative networks can approximate
real-valued analytic functions on bounded intervals.

######  Theorem 2.

Let $M\geq 1$, $s>2$, $C_{K}>0$ and $\epsilon\in(0,1)$ be scalars. Then, for
any real-valued analytic function $K:[-M,M]\to\mathbb{R}$ that is analytically
continuable to the ellipse $E_{s}^{M}$ where $\lvert K(x)\rvert\leq C_{K}$,
there exists a deep multiplicative network
$f^{\textnormal{MA}}:[-M,M]^{3}\to\mathbb{R}$ (MA stands for ‘Multiplicative
Analytic’) of depth
$L_{\epsilon}=\mathcal{O}({\textstyle\frac{1}{\log_{2}s}}\log_{2}{\textstyle\frac{C_{K}}{\epsilon}})$
with
$G_{\epsilon}=\mathcal{O}({\textstyle\frac{1}{\log_{2}s}}\log_{2}{\textstyle\frac{C_{K}}{\epsilon}})$
neurons that satisfies

$\|f^{\textnormal{MA}}(x,x,x)-K(x)\|_{L^{\infty}([-M,M])}~{}\leq~{}\epsilon.$

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_{s}^{M}$ with error bounded by a
quantity that decreases exponentially with the depth of the network.

In (Montanelli et al., 2021), the authors show that the kernel may be
approximated with depth
$L_{\epsilon}=\mathcal{O}({\textstyle\frac{1}{\log^{2}_{2}s}}\log^{2}_{2}{\textstyle\frac{C_{K}}{\epsilon}})$
with
$G_{\epsilon}=\mathcal{O}(\frac{1}{\epsilon^{2}\log^{2}_{2}s}\log^{2}_{2}\frac{C_{K}}{\epsilon})$
neurons. In contrast, our approach achieves a $\mathcal{O}(\log(1/\epsilon))$
improvement in depth and a $\mathcal{O}(\log(1/\epsilon^{2}))$ in number of
neurons, resulting in an exponentially faster convergence to the target
function.

Approximation of bandlimited functions.  As a next step, we study the ability
of neural networks to approximate bandlimited functions. We start by showing
how bandlimited functions can be approximated using analytic kernels. For this
purpose, we will use Maurey’s theorem (Pisier, 1980-1981; Vitali D. Milman,
1986) that states that for Hilbert subspaces with a bounded norm, any function
in the convex hull can be easily approximated using points from the subspace,
where the rate of approximation is dependent on the number of points used.

The following theorem shows that a deep multiplicative network can approximate
in $B=[0,1]^{d}$, a bandlimited function up to a given error tolerance using a
relatively small number of neurons and depth.

######  Theorem 3.

Let $\epsilon\in(0,1)$, $M>1,d\geq 2$, and $K:\mathbb{R}\rightarrow\mathbb{C}$
be an analytic kernel that holds the assumptions of Theorem 2 with respect to
$s>2,C_{K}>0$, and bounded by a constant $D_{K}\in(0,1]$ on $[-dM,dM]$. Let
$f$ be a real-valued function in $\mathcal{H}_{K,M}(B)$. Further, let
$F:[-M,M]^{d}\rightarrow\mathbb{C}$ be a square-integrable function such that
$f(x)=\textstyle\int_{[-M,M]^{d}}F(\omega)K(\omega\cdot
x)~{}\textnormal{d}\omega$. We define $C_{F}=\int_{\mathbb{R}^{d}}\lvert
F(\omega)\rvert~{}\textnormal{d}\omega$ = $\int_{[-M,M]^{d}}\lvert
F(\omega)\rvert~{}\textnormal{d}\omega$. Then, there exists a deep
multiplicative network $f^{\textnormal{MBL}}:B\to\mathbb{R}$ (MBL stands for
‘Multiplicative bandlimited’) of depth
$L_{\epsilon}=\mathcal{O}\left({\textstyle\frac{1}{\log_{2}s}}\log_{2}{\textstyle\frac{C_{F}C_{K}}{\epsilon}}\right)$
with
$G_{\epsilon}=\mathcal{O}\left({\textstyle\frac{C^{2}_{F}}{\epsilon^{2}\log_{2}s}}\log_{2}{{\textstyle\frac{C_{F}C_{K}}{\epsilon}}}\right)$
neurons that satisfies $\|f^{\textnormal{MBL}}-f\|_{L^{2}(B)}\leq\epsilon$.

The above theorem shows that one can approximate bandlimited functions up to
error $\epsilon$ using multiplicative neural networks of depth
$L_{\epsilon}=\mathcal{O}\left(\log(1/\epsilon)\right)$ using
$G_{\epsilon}=\mathcal{O}\left(\epsilon^{-2}\log(1/\epsilon)\right)$ neurons.
In comparison, Montanelli et al. (2021) showed that one can approximate
bandlimited functions to the same level of approximation using standard ReLU
networks of depths $L_{\epsilon}=\mathcal{O}\left(\log^{2}(1/\epsilon)\right)$
with $G_{\epsilon}=\mathcal{O}\left(\epsilon^{-2}\log^{2}(1/\epsilon)\right)$
neurons. This result demonstrates the inherent parameter efficiency of
multiplicative neural networks in comparison with standard ReLU networks.

Approximation of Smooth 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 $\mathcal{B}_{2r,2}\subsetneq\mathcal{W}^{r,2}$.
We show that using slightly stronger assumptions, we get an approximation rate
comparable to those shown by Barron (1993) (where the network is a shallow
sigmodial network model) using multiplicative neural networks (i.e. without
non-linear activations). Further, since these are in fact in
$\mathcal{W}^{r,2}$, we may better characterize such functions.

######  Theorem 4.

Let $d\geq 2,r\in\mathbb{N}$, $f\in\mathcal{B}_{2r,2}$ and $\epsilon>0$. There
exists a deep ReLU network $f^{\textnormal{RS}}$ (standing for “ReLU Sobolev”)
with a depth of $L_{\epsilon}=\mathcal{O}(d^{2}\epsilon^{-2/r})$ and
$G_{\epsilon}=\mathcal{O}(d^{2}\epsilon^{-(2+2/r)})$ neurons, such that
$\left\|f^{\textnormal{RS}}-f\right\|_{L_{2}(B)}\leq\epsilon$.

######  Theorem 5.

Let $d\geq 2,r\in\mathbb{N}$, $f\in\mathcal{B}_{2r,2}$ and $\epsilon>0$. There
exists a deep ReLU network $f^{\textnormal{MS}}$ (standing for “Multiplicative
Sobolev”) with a depth of $L_{\epsilon}=\mathcal{O}(d\epsilon^{-1/r})$ and
$G_{\epsilon}=\mathcal{O}(d\epsilon^{-(2+(1/r))})$ neurons, such that
$\left\|f^{\textnormal{MS}}-f\right\|_{L_{2}(B)}\leq\epsilon$.

###### Proof.

Let $f\in\mathcal{B}_{2r,2}$. We would like to approximate $f$ using a
bandlimited function $f_{M}$ and then approximate $f_{M}$ using a
multiplicative neural network $f^{\textnormal{BL}}=f^{\textnormal{MS}}$. Let
$M>1$ be a band.

We recall the Inverse Fourier transform given by
$(\mathcal{F}^{-1}g)(x)=\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}g(\omega)\exp(i\omega\cdot
x)~{}\textnormal{d}\omega$. We define the bandlimiting of
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ as
$f_{M}=\mathcal{F}^{-1}(\mathcal{F}{f}\mathbbm{1}_{[-M,M]^{d}})$, such that
$f_{M}\in{\mathcal{H}_{K,M}(B)}$ for $K(x)=\exp(ix)$ and
$F=\frac{1}{(2\pi)^{d}}\mathcal{F}f$. We have

$\displaystyle\|f-f_{M}\|_{L_{2}(B)}{}$
$\displaystyle\leq~{}\left(\frac{1}{(2\pi)^{d}}\left\|\mathcal{F}f-\mathcal{F}f\mathbbm{1}_{[-M,M]^{d}}\right\|_{L_{2}(\mathbb{R}^{d})}^{2}\right)^{1/2}$
$\displaystyle=~{}\left(\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}\backslash[-M,M]^{d}}{\left\lvert\mathcal{F}f(\omega)\right\rvert^{2}}~{}\textnormal{d}\omega\right)^{1/2}.$

For any $\omega\in\mathbb{R}^{d}\setminus[-M,M]^{d}$, we have $\lvert
M^{-1}\omega\rvert^{2r}\geq 1$. Therefore,

$\displaystyle\left(\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}\backslash[-M,M]^{d}}{\left\lvert\mathcal{F}f(\omega)\right\rvert^{2}}~{}\textnormal{d}\omega\right)^{1/2}{}$
$\displaystyle\leq~{}\left(\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}\backslash[-M,M]^{d}}\left\lvert
M^{-1}\omega\right\rvert^{2r}{\left\lvert\mathcal{F}f(\omega)\right\rvert^{2}}~{}\textnormal{d}\omega\right)^{1/2}$
$\displaystyle\leq~{}M^{-r}\left(\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}{\lvert\omega\rvert^{2r}\left\lvert\mathcal{F}f(\omega)\right\rvert^{2}}~{}\textnormal{d}\omega\right)^{1/2}$
$\displaystyle\leq~{}M^{-r},$

where the final inequality is due to $f\in\mathcal{B}_{2r,2}$. For any
$\epsilon>0$, we set $M=(2/\epsilon)^{1/r}$. We will construct a neural
network $f^{\textnormal{MS}}$ to approximate the bandlimited function $f_{M}$,
such that

$\|f_{M}-f^{\textnormal{MS}}\|_{L_{2}(B)}~{}\leq~{}\epsilon/2.$

Assuming we have constructed such $f^{\textnormal{MS}}$, then by the triangle
inequality we then arrive at

$\displaystyle\|f-f^{\textnormal{MS}}\|_{L_{2}(B)}~{}\leq~{}\|f-f_{M}\|_{L_{2}(B)}+\|f_{M}-f^{\textnormal{MS}}\|_{L_{2}(B)}~{}\leq~{}M^{-r}+\epsilon/2~{}\leq~{}\epsilon.$

We define a function $F:[-M,M]^{d}\rightarrow\mathbb{C}$ as follows

$F(\omega)~{}=~{}\frac{1}{(2\pi)^{d}}(\mathcal{F}f)(\omega).$

We then have the following identity

$f_{M}(x)~{}=~{}\int_{[-M,M]^{d}}F(\omega)K(\omega\cdot
x)~{}\textnormal{d}\omega~{}=~{}\int_{[-M,M]^{d}}{\textstyle\frac{1}{(2\pi)^{d}}}\mathcal{F}f(\omega)\exp(i\omega\cdot
x)~{}\textnormal{d}\omega.$

We may now work under the conditions of Theorem 3. We consider that
$C_{F}=\int_{[-M,M]^{d}}\lvert
F(\omega)\rvert~{}\textnormal{d}\omega=\frac{1}{(2\pi)^{d}}\int_{[-M,M]^{d}}\lvert\mathcal{F}{f}(\omega)\rvert~{}\textnormal{d}\omega\leq
1$, where the inequality is due to the definition of $\mathcal{B}_{2r,2}$. The
kernel $K(t)=\exp(it)$ takes as input $t=\omega\cdot x$, for $x\in B$ and
$\omega\in[-M,M]^{d}$. Therefore, $t\in[-dM,dM]$, and
$K:[-dM,dM]\rightarrow\mathbb{R}$. We note that $K$ is continuable to the
Bernstein 4-ellipse $E_{4}^{dM}$. We notice that $a^{dM}_{4}=dM(4+4^{-1})/2$
is the larger axis, and therefore the maximal norm of $K$ on $E^{dM}_{s}$ is
given by $K(a^{dM}_{4})$:

$C_{K}~{}=~{}\max_{t}\lvert
K(t)\rvert~{}\leq~{}\exp(dM{\textstyle\frac{4+4^{-1}}{2}}).$

Further, for any $t\in\mathbb{R}$ we have $\lvert K(t)\rvert\leq 1=D_{K}$.

We now approximate $f_{M}$ with a multiplicative network. Using the results of
Theorem 3, there exists a deep multiplicative neural network
$f^{\textnormal{MS}}$ that approximates the bandlimited function $f_{M}$ in
$L_{2}(B)$ with error bounded by $\epsilon/2$ and depth

$\displaystyle L_{\epsilon}{}$
$\displaystyle\leq~{}C_{1}\frac{1}{\log_{2}4}\log_{2}{\frac{2C_{K}C_{F}}{\epsilon}}$
(2)
$\displaystyle\leq~{}C_{2}\frac{1}{\log_{2}4}{\log_{2}{\frac{{\exp(dM\frac{4+4^{-1}}{2})}}{\epsilon}}}$
$\displaystyle\leq~{}C_{2}\left(3d\epsilon^{-1/r}+\log_{2}(1/\epsilon)\right)$
$\displaystyle\leq~{}C_{3}\cdot d\epsilon^{-1/r},$

for some constants $C_{1},C_{2},C_{3}>0$. In addition, the number of neurons
can be bounded by

$\displaystyle G_{\epsilon}{}$
$\displaystyle\leq~{}C^{\prime}_{1}{C_{F}^{2}}\cdot\epsilon^{-2}\log_{2}{\frac{2C_{K}C_{F}}{\epsilon}}$
(3)
$\displaystyle\leq~{}C^{\prime}_{2}\cdot\epsilon^{-2}{\log_{2}{\frac{{\exp(dM\frac{4+4^{-1}}{2})}}{\epsilon}}}$
$\displaystyle\leq~{}C^{\prime}_{2}\cdot\epsilon^{-2}(3d(2/\epsilon)^{1/r}+\log_{2}(1/\epsilon))$
$\displaystyle\leq~{}C^{\prime}_{3}\cdot d\epsilon^{-(2+1/r)},$

for some constants $C^{\prime}_{1},C^{\prime}_{2},C^{\prime}_{3}>0$. ∎

Theorems 4-5 provide insights into several interesting properties of the
Sobolev-Type ball $\mathcal{B}_{2r,2}$. 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 becomes tighter as the smoothness $r$
increases, which is a desirable property for approximation error bounds. In
fact, as $r$ approaches infinity, the bound approaches the one proposed in
(Barron, 1993). Lastly, we show that for the same error tolerance $\epsilon$,
multiplicative neural networks can approximate a target function
$f\in\mathcal{B}_{2r,2}$ with a depth of $\mathcal{O}(d^{2}\epsilon^{-1/r})$
and $\mathcal{O}(d^{2}\epsilon^{-(1+1/r)})$ neurons, while standard ReLU
neural networks require a depth of $\mathcal{O}(d^{2}\epsilon^{-2/r})$ and
$\mathcal{O}(d^{2}\epsilon^{-(2+2/r)})$ neurons. This result demonstrates that
multiplicative neural networks have stronger approximation guarantees when
approximating functions in the Sobolev-Type space.

##  4 Conclusions

Previous papers have studied the approximation guarantees of standard fully-
connected neural networks to approximate functions in the Barron space
$\mathcal{B}_{1,1}$ (Barron, 1993), the space of bandlimited functions
(Montanelli et al., 2021), and the Korobov space (Blanchard & Bennouna,
2022a). These studies have shown that fully-connected networks can approximate
a 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 network 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 to approximate bandlimited functions and members of the Sobolev-Type
ball $\mathcal{B}_{2r,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, $\mathcal{B}_{2r,2}$ is a subset of the Sobolev space
$\mathcal{W}^{r,2}$. Therefore, our results demonstrate that it is possible to
avoid the curse of dimensionality for wide subsets of the Sobolev space.

## Acknowledgements

Tomer Galanti was supported by the Center for Minds, Brains and Machines
(CBMM), funded by NSF STC award CCF-1231216 and by NSF award 213418.

## References

  * Albrecht et al. (2021) David W. Albrecht, Xuan Thinh Duong, and Alan Mcintosh.  Operator theory and harmonic analysis.  _Springer Proceedings in Mathematics & Statistics_, 2021.
  * Arulkumaran et al. (2019) Kai Arulkumaran, Antoine Cully, and Julian Togelius.  Alphastar: an evolutionary computation perspective.  _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2019.
  * Barron (1991) A. R. Barron.  Approximation and estimation bounds for artificial neural networks.  In _Proceedings of the Fourth Annual Workshop on Computational Learning Theory_ , COLT ’91, pp. 243–249, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc.  ISBN 1558602135.
  * Barron (1993) Andrew R. Barron.  Universal approximation bounds for superpositions of a sigmoidal function.  _IEEE Trans. Inf. Theory_ , 39:930–945, 1993.
  * Bensadoun et al. (2021) Raphael Bensadoun, Shir Gur, Tomer Galanti, and Lior Wolf.  Meta internal learning.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 20645–20656. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/ac796a52db3f16bbdb6557d3d89d1c5a-Paper.pdf.
  * Blanchard & Bennouna (2022a) Moise Blanchard and Mohammed Amine Bennouna.  Shallow and deep networks are near-optimal approximators of korobov functions.  In _ICLR_ , 2022a.
  * Blanchard & Bennouna (2022b) Moise Blanchard and Mohammed Amine Bennouna.  Shallow and deep networks are near-optimal approximators of korobov functions.  In _International Conference on Learning Representations_ , 2022b.  URL https://openreview.net/forum?id=AV8FPoMTTa.
  * Blum et al. (2020) Avrim Blum, John Hopcroft, and Ravindran Kannan.  _Foundations of Data Science_.  Cambridge University Press, 2020.  doi: 10.1017/9781108755528.
  * Brown et al. (2020) 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 _Advances in Neural Information Processing Systems_ , volume 33, pp. 1877–1901. Curran Associates, Inc., 2020.
  * Chen et al. (2021) 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 Wojciech Zaremba.  Evaluating large language models trained on code, 2021.
  * Cheng et al. (2016) Jianpeng Cheng, Li Dong, and Mirella Lapata.  Long short-term memory-networks for machine reading.  In _Conference on Empirical Methods in Natural Language Processing_ , 2016.
  * Cybenko (1989) George V. Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of Control, Signals and Systems_ , 2:303–314, 1989.
  * Devlin et al. (2019) 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 American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. Association for Computational Linguistics, jun 2019.
  * DeVore & Lorentz (1993) Ronald A. DeVore and George G. Lorentz.  Constructive approximation.  In _Grundlehren der mathematischen Wissenschaften_ , 1993.
  * DeVore et al. (1989) Ronald A. DeVore, Ralph Howard, and Charles A. Micchelli.  Optimal nonlinear approximation.  _manuscripta mathematica_ , 63:469–478, 1989.
  * Devroye et al. (1996) Luc Devroye, László Györfi, and Gábor Lugosi.  A probabilistic theory of pattern recognition.  In _Stochastic Modelling and Applied Probability_ , 1996.
  * Dosovitskiy et al. (2021) 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 is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=YicbFdNTTy.
  * Durbin & Rumelhart (1989) Richard Durbin and David E. 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/neco.1989.1.1.133.  URL https://doi.org/10.1162/neco.1989.1.1.133.
  * E et al. (2021) Weinan E, Chao Ma, and Lei Wu.  The barron space and the flow-induced function spaces for neural network models.  _Constructive Approximation_ , 55:369–406, 2021.
  * Galanti & Wolf (2020) Tomer Galanti and Lior Wolf.  On the modularity of hypernetworks.  In _Advances in Neural Information Processing Systems 33_. Curran Associates, Inc., 2020.
  * Ha et al. (2016) David Ha, Andrew Dai, and Quoc V Le.  Hypernetworks.  _arXiv preprint arXiv:1609.09106_ , 2016.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep Residual Learning for Image Recognition.  In _Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition_ , CVPR ’16, pp. 770–778. IEEE, June 2016.  doi: 10.1109/CVPR.2016.90.  URL http://ieeexplore.ieee.org/document/7780459.
  * Hornik et al. (1989) Kurt Hornik, Maxwell B. Stinchcombe, and Halbert L. White.  Multilayer feedforward networks are universal approximators.  _Neural Networks_ , 2:359–366, 1989.
  * ichi Funahashi (1989) Ken ichi Funahashi.  On the approximate realization of continuous mappings by neural networks.  _Neural Networks_ , 2:183–192, 1989.
  * Imaizumi & Fukumizu (2018) Masaaki Imaizumi and Kenji Fukumizu.  Deep neural networks learn non-smooth functions effectively.  In _International Conference on Artificial Intelligence and Statistics_ , 2018.
  * Jones (1992) Lee K. Jones.  A simple lemma on greedy approximation in hilbert space and convergence rates for projection pursuit regression and neural network training.  _Annals of Statistics_ , 20:608–613, 1992.
  * Klusowski & Barron (2016) Jason M. Klusowski and Andrew R. Barron.  Risk bounds for high-dimensional ridge function combinations including neural networks.  _arXiv: Statistics Theory_ , 2016.
  * Kohler & Krzyżak (2017) Michael Kohler and Adam Krzyżak.  Nonparametric regression based on hierarchical interaction models.  _IEEE Transactions on Information Theory_ , 63(3):1620–1630, 2017.  doi: 10.1109/TIT.2016.2634401.
  * Krueger et al. (2017) David Krueger, Chin-Wei Huang, Riashat Islam, Ryan Turner, Alexandre Lacoste, and Aaron Courville.  Bayesian hypernetworks.  _arXiv preprint arXiv:1710.04759_ , 2017.
  * Leshno et al. (1991) Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken.  Multilayer feedforward networks with a non-polynomial activation function can approximate any function.  _New York University Stern School of Business Research Paper Series_ , 1991.
  * Levine et al. (2020) Yoav Levine, Noam Wies, Or Sharir, Hofit Bata, and Amnon Shashua.  Limits to depth efficiencies of self-attention.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 22640–22651. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/ff4dfdf5904e920ce52b48c1cef97829-Paper.pdf.
  * Liang & Srikant (2017) Shiyu Liang and Rayadurgam Srikant.  Why deep neural networks for function approximation?  In _ICLR_ , 2017.
  * Littwin & Wolf (2019) Gidi Littwin and Lior Wolf.  Deep meta functionals for shape representation.  In _The IEEE International Conference on Computer Vision (ICCV)_ , 2019.
  * Mhaskar (2010) H.N. Mhaskar.  Eignets for function approximation on manifolds.  _Applied and Computational Harmonic Analysis_ , 29(1):63–87, 2010.  ISSN 1063-5203.  doi: https://doi.org/10.1016/j.acha.2009.08.006.  URL https://www.sciencedirect.com/science/article/pii/S106352030900089X.
  * Mhaskar et al. (2017) Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio.  When and why are deep networks better than shallow ones?  In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence_ , AAAI’17, pp. 2343–2349. AAAI Press, 2017.
  * Mhaskar (1996) Hrushikesh Narhar Mhaskar.  Neural networks for optimal approximation of smooth and analytic functions.  _Neural Computation_ , 8:164–177, 1996.
  * Montanelli & Du (2019) Hadrien Montanelli and Qiang Du.  New error bounds for deep relu networks using sparse grids.  _SIAM Journal on Mathematics of Data Science_ , 1(1):78–92, 2019.  doi: 10.1137/18M1189336.  URL https://doi.org/10.1137/18M1189336.
  * Montanelli et al. (2021) Hadrien Montanelli, Haizhao Yang, and Qiang Du.  Deep ReLU networks overcome the curse of dimensionality for bandlimited functions.  _Journal of Computational Mathematics_ , 39:801–815, 2021\.
  * Nakada & Imaizumi (2022) Ryumei Nakada and Masaaki Imaizumi.  Adaptive approximation and generalization of deep neural network with intrinsic dimensionality.  _J. Mach. Learn. Res._ , 21(1), jun 2022.  ISSN 1532-4435.
  * Parikh et al. (2016) Ankur Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit.  A decomposable attention model for natural language inference.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pp. 2249–2255, Austin, Texas, November 2016. Association for Computational Linguistics.  doi: 10.18653/v1/D16-1244.  URL https://aclanthology.org/D16-1244.
  * Paulus et al. (2017) Romain Paulus, Caiming Xiong, and Richard Socher.  A deep reinforced model for abstractive summarization, 2017.  URL https://arxiv.org/abs/1705.04304.
  * Petersen & Voigtländer (2017) Philipp Christian Petersen and Felix Voigtländer.  Optimal approximation of piecewise smooth functions using deep relu neural networks.  _Neural networks : the official journal of the International Neural Network Society_ , 108:296–330, 2017.
  * Pinkus (1985) Allan Pinkus.  _N-Widths in Approximation Theory_.  Springer-Verlag, 1985.
  * Pisier (1980-1981) Gilles Pisier.  Remarks on an unpublished result of B. Maurey, 1980-1981.  URL http://www.numdam.org/item/SAF_1980-1981____A5_0/.
  * Poggio et al. (2020) Tomaso Poggio, Andrzej Banburski, and Qianli Liao.  Theoretical issues in deep networks.  _Proceedings of the National Academy of Sciences_ , 117(48):30039–30045, 2020.  doi: 10.1073/pnas.1907369117.  URL https://www.pnas.org/doi/abs/10.1073/pnas.1907369117.
  * Robert A. Adams (2003) John J. F. Fournier Robert A. Adams.  _Sobolev spaces_.  Pure and Applied Mathematics. Academic Press, 2 edition, 2003.  ISBN 9780120441433,9781435608108,0120441438.  URL http://gen.lib.rus.ec/book/index.php?md5=72db1ed30d242bd3ebcb73bcd099a6b4.
  * Schmidt-Hieber (2019) Johannes Schmidt-Hieber.  Deep relu network approximation of functions on a manifold, 2019.  URL https://arxiv.org/abs/1908.00695.
  * Shannon (1984) Claude E. Shannon.  Communication in the presence of noise.  _Proceedings of the IEEE_ , 72:1192–1201, 1984.
  * Silver et al. (2016) David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.  Mastering the game of Go with deep neural networks and tree search.  _Nature_ , 529:484–489, 2016.  ISSN 0028-0836.  doi: 10.1038/nature16961.
  * Trask et al. (2018) Andrew Trask, Felix Hill, Scott Reed, Jack Rae, Chris Dyer, and Phil Blunsom.  Neural arithmetic logic units, 2018.  URL https://arxiv.org/abs/1808.00508.
  * Trefethen (2019) Lloyd N. Trefethen.  _Approximation Theory and Approximation Practice, Extended Edition_.  Society for Industrial and Applied Mathematics, Philadelphia, PA, 2019\.  doi: 10.1137/1.9781611975949.  URL https://epubs.siam.org/doi/abs/10.1137/1.9781611975949.
  * Urban & van der Smagt (2015) Sebastian Urban and Patrick van der Smagt.  A neural transfer function for a smooth and differentiable transition between additive and multiplicative interactions, 2015.  URL https://arxiv.org/abs/1503.05724.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Vitali D. Milman (1986) Gideon Schechtman Vitali D. Milman.  _The Maurey-Pisier Theorem_ , pp. 85–97.  Springer Berlin Heidelberg, Berlin, Heidelberg, 1986.  ISBN 978-3-540-38822-7.  doi: 10.1007/978-3-540-38822-7_13.  URL https://doi.org/10.1007/978-3-540-38822-7_13.
  * von Oswald et al. (2020) Johannes von Oswald, Christian Henning, João Sacramento, and Benjamin F. Grewe.  Continual learning with hypernetworks.  In _International Conference on Learning Representations_ , 2020.
  * Wahba (1990) Grace Wahba.  _Spline Models for Observational Data_.  Society for Industrial and Applied Mathematics, 1990.  doi: 10.1137/1.9781611970128.  URL https://epubs.siam.org/doi/abs/10.1137/1.9781611970128.
  * Yarotsky (2017) Dmitry Yarotsky.  Error bounds for approximations with deep relu networks.  _Neural networks : the official journal of the International Neural Network Society_ , 94:103–114, 2017.
  * Zhai et al. (2021) Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer.  Scaling vision transformers.  _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 1204–1213, 2021.

##  Appendix A Examples

######  Example 1.

Let $f\in{L}_{2}(\mathbb{R}^{d})$ such that $f$ is Bandlimited function with
band $\pi$ (i.e., $\operatorname{supp}(\mathcal{F}f)\subset[-\pi,\pi]^{d}$).
Let $\phi(x)=\operatorname{sinc}(x)=\sin(\pi x)/{\pi x}$, and
$\phi_{k}=\phi({\cdot}-k)$ for all $k\in\mathbb{Z}^{d}$. By the Shannon-
Nyquist theorem (Shannon, 1984), we have:

$\displaystyle f(x)~{}=~{}\sum_{k\in\mathbb{Z}^{d}}\langle
f,\phi_{k}\rangle\phi_{k}(x)~{}=~{}\sum_{k\in\mathbb{Z}^{d}}f(k)\phi{(x-k)}.$

This means that every Bandlimited function can be completely determined using
a discrete set of integer samples. This result is particularly surprising for
high-dimensional functions ($d$ is large) since the maximal distance between a
point $x$ and a sampling point grows with $d$. For example, the vertex of the
unit cube in $\mathbb{R}^{d}$ is of distance $\sqrt{d}/2$ away from its
center. Despite this, we can still recover samples from the integer vertices,
even when the distances scale as $\sqrt{d}$. This property is useful when
recovering high-dimensional functions using neural networks. See Figure 1 for
illustration.

$\frac{1}{2}$$\frac{\sqrt{2}}{2}$$\frac{\sqrt{3}}{2}$ Figure 1: Illustration
of Example 1. A bandlimited function $f$ can be reconstructed using a discrete
set of values, despite the fact that the distances in each cube grow as
$\mathcal{O}(\sqrt{d})$.

##  Appendix B Proofs

######  Definition 4.

For two Banach spaces $V_{1}$ and $V_{2}$, we say that $V_{1}$ is embedded in
$V_{2}$ if $\|u\|_{V_{2}}\leq C\|u\|_{V_{1}}$ for some constant $C$ and for
$u\in V_{1}$.

######  Lemma 2.

Let $r>0$ and $d\geq 2$. Then, $\mathcal{B}_{2r,2}$ is embedded as a proper
subspace of $\mathcal{W}^{r,2}$.

###### Proof.

Since $f\in\mathcal{B}_{2r,2}$, we have $f\in L_{2}(\mathbb{R}^{d})$, and
therefore, $\|f\|_{2}<\infty$. Additionally, by Robert A. Adams (2003)(Theorem
5.2), there exists a constant $C_{1}>0$ such that

$\|f\|_{\mathcal{W}^{r,2}}~{}\leq~{}C_{1}(\|f\|_{2}+\lvert f\rvert_{r,2}),$

where $C_{1}$ is dependant on $r$ and the dimension $d$. Therefore, it remains
to prove that $\lvert f\rvert_{r,2}$ is bounded. For this, we use some
properties of multivariate function spaces.

We begin with the following claim that we will use in advance. Let
$\omega\in\mathbb{R}^{d},d\geq 2$, we have

$\lvert\omega\rvert^{2r}~{}=~{}\|\omega\|_{l_{2}}^{2r}~{}=~{}\left(\sum_{m=1}^{d}\omega_{m}^{2}\right)^{r}~{}=~{}\sum_{\|\alpha\|_{1}=r}\binom{r}{\alpha_{1},\dots,\alpha_{d}}\cdot(\omega^{\alpha})^{2},$
(4)

where $\omega^{\alpha}=\prod^{d}_{i=1}\omega^{\alpha_{i}}$ for
$\alpha\in\mathbb{R}^{d}$.

By Jensen’s inequality,

$\displaystyle\lvert
f\rvert_{r,2}^{2}~{}=~{}\left(\sum_{\alpha:\lvert\alpha\rvert=r}\|D^{\alpha}f\|_{2}\right)^{2}~{}\leq~{}d^{r}\sum_{\alpha:\lvert\alpha\rvert=r}\|D^{\alpha}f\|_{2}^{2}$

By Parseval’s Identity in $\mathbb{R}^{d}$ (Albrecht et al., 2021):

$\|D^{\alpha}f\|_{2}^{2}~{}=~{}\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}\lvert\mathcal{F}(D^{\alpha}f)(\omega)\rvert^{2}~{}\textnormal{d}\omega~{}=~{}\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}\lvert(\mathcal{F}f)(\omega)\rvert^{2}{\lvert\omega^{\alpha}\rvert^{2}}~{}\textnormal{d}\omega.$

Hence, by (4)

$\displaystyle\sum_{\alpha:\lvert\alpha\rvert=r}\|D^{\alpha}f\|_{2}^{2}{}$
$\displaystyle=~{}\sum_{\alpha:\lvert\alpha\rvert=r}\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}\lvert(\mathcal{F}f)(\omega)\rvert^{2}{\lvert\omega^{\alpha}\rvert^{2}}~{}\textnormal{d}\omega$
$\displaystyle\leq~{}\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}\lvert(\mathcal{F}f)(\omega)\rvert^{2}\left(\sum_{\alpha:\lvert\alpha\rvert=r}\binom{r}{\alpha_{1},\dots,\alpha_{d}}\cdot{\lvert\omega^{\alpha}\rvert^{2}}\right)~{}\textnormal{d}\omega$
$\displaystyle=~{}\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}\lvert\mathcal{F}f(\omega)\rvert^{2}\lvert\omega\rvert^{2r}~{}\textnormal{d}\omega.$

where the inequality follows from the fact that
$\binom{r}{\alpha_{1},\dots,\alpha_{d}}\geq 1$. Finally, we conclude that

$\displaystyle\|f\|_{\mathcal{W}^{r,2}}~{}\leq~{}C_{1}(\|f\|_{2}+\lvert
f\rvert_{r,2}){}$
$\displaystyle\leq~{}C_{1}\left(\|f\|_{2}+{\textstyle\frac{d^{r}}{(2\pi)^{d/2}}}\left(\textstyle\int_{\mathbb{R}^{d}}\lvert(\mathcal{F}f)(\omega)\rvert^{2}\lvert\omega\rvert^{2r}~{}\textnormal{d}\omega\right)^{1/2}\right)$
$\displaystyle\leq~{}C_{2}\|f\|_{\mathcal{B}_{2r,2}},$

for some $C_{1},C_{2}>0$, where the second inequality is due to the definition
of $\|\cdot\|_{\mathcal{B}_{2r,2}}$ as given in equation 1.

To see that $\mathcal{B}_{2r,2}$ is a proper subspace of $\mathcal{W}^{r,2}$,
let us define as an example, the function
$f\in\mathcal{W}^{r,2}\left(\mathbb{R}^{d}\right)$ through its Fourier
transform:

$\mathcal{F}f(\omega)=\begin{cases}1&\lvert\omega\rvert\leq 1\\\
\lvert\omega\rvert^{-(r+(d+\epsilon)/2)}&\lvert\omega\rvert>1\end{cases}$

for any $\epsilon>0$.

Indeed, $f\in\mathcal{W}^{r,2}\left(\mathbb{R}^{d}\right)$ since:

$\displaystyle\int_{\mathbb{R}^{d}}\lvert\omega\rvert^{2r}\lvert\mathcal{F}f(\omega)\rvert^{2}~{}\textnormal{d}\omega{}$
$\displaystyle=~{}\int_{\lvert\omega\rvert\leq
1}\lvert\omega\rvert^{2r}\lvert\mathcal{F}f(\omega)\rvert^{2}d\omega+\int_{\lvert\omega\rvert>1}\lvert\omega\rvert^{2r}\lvert\mathcal{F}f(\omega)\rvert^{2}~{}\textnormal{d}\omega$
$\displaystyle\leq~{}1+\int_{\lvert\omega\rvert>1}\lvert\omega\rvert^{-(d+\epsilon)}~{}\textnormal{d}\omega<\infty.$

However, for this example $\mathcal{F}f(\omega)\notin L_{1}$ in the cases
where the dimension is relatively higher than the smoothness index. That is,
whenever

$r+(d+\epsilon)/2\leq d\Leftrightarrow 2r+\epsilon\leq d.$

This implies that $f$ does not satisfy the condition
$\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}\lvert\mathcal{F}f(\omega)\rvert
d\omega\leq 1$ which is required in $\mathcal{B}_{2r,2}$. We see that the
$L_{1}$ condition on the Fourier transform of functions in
$\mathcal{B}_{2r,r}$ allows us to circumvent the curse of dimensionality when
approximating in Sobolev spaces. ∎

See 1

###### Proof.

Let $p_{n}(x)=\sum_{k=0}^{n}c_{k}x^{k}$ be a polynomial of degree $n$ and
$p_{n,i}=\sum_{k=0}^{i}c_{k}x^{k}$ its partial sum up to term $i$. We
construct a network $f^{\textnormal{POL}}_{n}$ whose $i$th layer satisfies:

$(f^{\textnormal{POL}}_{n})_{i}(x,x,c_{0})=(x,x^{i+1},p_{n,i}(x)).$

At layer $i$, the model weights for the three neurons are defined as:

$w_{i,1}=(1,0,0),\quad a_{i,2}=1\text{ for }(j_{1},j_{2})=(1,2)\text{ },\quad
w_{i,3}=(0,c_{i},1)$

The rest of the weights are zeros.

We argue that at any layer $i\geq 0$, neuron 1 contains $x$, neuron 2 contains
$x^{i+1}$ and neuron 3 contains $p_{n,i}(x)$. Let
$y_{{i+1},1},y_{{i+1},2},y_{{i+1},3}$ be the three neurons in layer $i+1$.
Since the only non-zero weight affecting the first neuron is in $w_{i+1,1}$,
$y_{i+1,1}=y_{i,1}=x$ by the assumption. The only non-zero weight affecting
the second neuron appears in $a_{i=1,2}$, and therefore
$y_{i+1,2}=y_{i,1}y_{i,2}=x^{i+1}$. Lastly, $y_{i+1,3}$ depends only on
$w_{i+1,3}$, and so
$y_{i+1,3}=c_{i+1}y_{i,2}+y_{i,3}=p_{n,i}(x)+c_{i+1}x^{i+1}:=p_{n,i+1}(x)$. We
conclude using the fact that $p_{n,n}(x)=p_{n}(x)$. ∎

$x$$x$$c_{0}$$x$$x^{2}$$c_{0}+c_{1}x$$x$$x^{3}$$p_{2,2}(x)$$(w_{i,1})_{1}=1$$a_{i,2}=1$$a_{i,2}=1$$(w_{i,3})_{2}=c_{i}$$(w_{i,3})_{3}=1$$(w_{i,1})_{1}=1$$a_{i,2}=1$$a_{i,2}=1$$(w_{i,3})_{2}=c_{i}$$(w_{i,3})_{3}=1$InputlayerHiddenlayerOutputlayer
Figure 2: Illustration of the multiplicative network in Proof of Lemma 1,
where the polynomial degree $n=2$.

See 2

###### Proof.

Let $M\geq 1$, $s>2$, $C_{K}>0$, $\epsilon\in(0,1)$ and let $K$ be an analytic
function with the required assumptions. As a first step, we approximate $K$
with a polynomial $h_{n}$ of degree $n\geq 2$ (to be defined later). Then, we
realize $h_{n}$ with a deep multiplicative network using Lemma 1. We recall
the polynomial $h_{n}$ described in Theorem 1. For any integer $n\geq 2$, we
have

$\|h_{n}-K\|_{L^{\infty}([-M,M])}~{}\leq~{}{\textstyle\frac{C_{K}s^{-n}}{s-1}}~{}=~{}\mathcal{O}(C_{K}s^{-n}).$

By choosing
$n=\frac{1}{\log_{2}s}\log_{2}\frac{C_{K}}{\epsilon(s-1)}\leq\frac{1}{\log_{2}s}\log_{2}\frac{C_{K}}{\epsilon}$
we obtain the following relation:

$\displaystyle\frac{\epsilon(s-1)}{C_{K}}{}$
$\displaystyle=~{}2^{\log_{2}(\frac{\epsilon(s-1)}{C_{K}})}$ (5)
$\displaystyle=~{}2^{-\frac{1}{\log_{2}s}(\log_{2}(\frac{C_{K}}{\epsilon(s-1)}))\log_{2}s}$
$\displaystyle=~{}s^{-\frac{1}{\log_{2}s}(\log_{2}(\frac{C_{K}}{\epsilon(s-1)}))}~{}=~{}s^{-n}.$

In particular,

$\|h_{n}-K\|_{L^{\infty}([-M,M])}~{}\leq~{}{\textstyle\frac{C_{K}s^{-n}}{s-1}}~{}\leq~{}\epsilon,$

for $s\geq 1$. Given that $h_{n}$ is a polynomial of degree $n$, by Lemma 1,
there exists $f^{\textnormal{POL}}$ and $c_{0}=h_{n,0}$ such that
$h_{n}(x)=f^{\textnormal{POL}}(x,x,c_{0})$, and achieve the desired result. ∎

Let us now recall Maurey’s Theorem (Pisier, 1980-1981; Vitali D. Milman, 1986)
which will assist us in the proof of Theorem 3.

######  Lemma 3 (Maurey’s theorem).

Let $\mathcal{V}$ be a Hilbert space with norm $\|\cdot\|_{\mathcal{V}}$.
Suppose there exists $Q\subset\mathcal{V}$ such that for every $q\in Q$,
$\|q\|_{\mathcal{V}}\leq b$ for some $b>0$. Then, for every $f$ in the convex
hull of $Q$ and every integer $n\geq 1$, there exists a $f_{n}$ in the convex
hull of $n$ points in $Q$ and a constant $c>b^{2}-\|f\|_{\mathcal{V}}^{2}$
such that $\|f_{n}-f\|_{\mathcal{V}}^{2}\leq\frac{c}{n}$.

See 3

###### Proof.

Let $f\in\mathcal{H}_{K,M}(B)$. Further, let $F(\omega)=\lvert
F(\omega)\rvert\cdot\exp(i\theta(\omega))$, the polar representation of
$F(\omega)$. The following holds:

$\displaystyle f(x){}$
$\displaystyle=~{}\text{Re}\left(\int_{[-M,M]^{d}}F(\omega)K(\omega\cdot
x)~{}\textnormal{d}\omega\right)$ (6)
$\displaystyle=~{}\text{Re}\left(\int_{[-M,M]^{d}}C_{F}\exp(i\theta(\omega))K(\omega\cdot
x)\frac{\lvert F(\omega)\rvert}{C_{F}}~{}\textnormal{d}\omega\right)$
$\displaystyle=~{}\int_{[-M,M]^{d}}{C_{F}\left[\cos(\theta(\omega))K_{R}(\omega\cdot
x)-\sin(\theta(\omega))K_{I}(\omega\cdot x)\right]\frac{\lvert
F(\omega)\rvert}{C_{F}}~{}\textnormal{d}\omega},$

where $K_{R},K_{I}$ are the real and imaginary parts of $K$ respectively.
Given that the integral represents $f$ as an infinite convex combination of
functions in

$Q_{K,M}=\left\\{\gamma\left[\cos(\beta)K_{R}{(\omega\cdot
x)}-\sin(\beta)K_{I}(\omega\cdot
x)\right]\mathrel{\Big{|}}\lvert\gamma\rvert\leq
C_{F},\beta\in\mathbb{R},\omega\in[-M,M]^{d}\right\\},$

then $f$ is in the closure of the convex hull of $Q_{K,M}$. Due to the fact
that $x\in[0,1]^{d}$ and $\omega\in[-M,M]^{d}$, $t=\omega\cdot x\in[-dM,dM]$.
By the definition of $D_{K}$, functions in $Q_{K,M}$ are bounded in the
$L^{2}(B)$-norm by $2C_{F}D_{K}\leq 2C_{F}$. Using Lemma 3, there exist real
coefficients $\\{b_{j}\\}$ and $\\{\beta_{j}\\}$, and vectors
$\omega_{j}\in[-M,M]^{d}$ for $1\leq j\leq\lceil 1/\epsilon_{0}^{2}\rceil$,
such that:

$f_{\epsilon_{0}}(x)=\sum_{j=1}^{\lceil
1/\epsilon_{0}^{2}\rceil}{b_{j}\left[\cos(\beta_{j})K_{R}(\omega_{j}\cdot
x)-\sin(\beta_{j})K_{I}(\omega_{j}\cdot x)\right]},\quad\sum_{j=1}^{\lceil
1/\epsilon_{0}^{2}\rceil}{\lvert b_{j}\rvert}\leq C_{F},$

for $0<\epsilon_{0}<1$ to be defined at a later time, such that

$\|f_{\epsilon_{0}}(x)-f(x)\|_{L^{2}(B)}\leq 2C_{F}\epsilon_{0}.$

We are now ready to approximate $f_{\epsilon_{0}}(x)$ using a deep
multiplicative neural network $f^{\textnormal{MBL}}$ on $B$. We notice that
$K_{R}(x)$ and $K_{I}(x)$ are analytic kernels that hold the assumptions of
Theorem 2. They can therefore be approximated to $\epsilon_{0}$ error using
networks $f^{\textnormal{RMA}}$, $f^{\textnormal{IMA}}$ of depth and number of
neurons

$G_{\epsilon_{0}}\sim
L_{\epsilon_{0}}=\mathcal{O}(\frac{1}{\log_{2}s}\log_{2}\frac{C_{K}}{\epsilon_{0}}),$

where RMA stands for ‘Real Multiplicative Analytic’ and IMA stands for
‘Imaginary Multiplicative Analytic’. Let us define the multiplicative network
$f^{\textnormal{MBL}}(x)$ by

$f^{\textnormal{MBL}}(x)=\sum_{j=1}^{\lceil
1/\epsilon_{0}^{2}\rceil}{b_{j}\left[\cos(\beta_{j}){f^{\textnormal{RMA}}}(\omega_{j}\cdot
x)-\sin(\beta_{j})f^{\textnormal{IMA}}(\omega_{j}\cdot x)\right]}.$

This network has depth
$L_{\epsilon_{0}}=\mathcal{O}(\frac{1}{\log_{2}s}\log_{2}\frac{C_{K}}{\epsilon_{0}})$
and
$G_{\epsilon_{0}}=\mathcal{O}(\frac{1}{{\epsilon_{0}^{2}}\log_{2}s}\log_{2}\frac{C_{K}}{\epsilon_{0}})$
neurons.

$\displaystyle\|f^{\textnormal{MBL}}(x)-f_{\epsilon_{0}}(x)\|_{L^{\infty}(B)}{}$
$\displaystyle\leq~{}\sum_{j=1}^{\lceil 1/\epsilon_{0}^{2}\rceil}{\lvert
b_{j}\rvert\|f^{\textnormal{RMA}}(\omega_{j}\cdot x)-K_{R}(\omega_{j}\cdot
x)\|_{L^{\infty}(B)}}$ $\displaystyle\quad+\sum_{j=1}^{\lceil
1/\epsilon_{0}^{2}\rceil}{\lvert
b_{j}\rvert\|f^{\textnormal{IMA}}(\omega_{j}\cdot x)-K_{I}(\omega_{j}\cdot
x)\|_{L^{\infty}(B)}}$ $\displaystyle\leq~{}2C_{F}\epsilon_{0},$

that implies

$\|f^{\textnormal{MBL}}(x)-f(x)\|_{L^{2}(B)}\leq\|f^{\textnormal{MBL}}(x)-f_{\epsilon_{0}}(x)\|_{L^{2}(B)}+\|f_{\epsilon_{0}}(x)-f(x)\|_{L^{2}(B)}\leq
4C_{F}{\epsilon_{0}},$

where the last inequality is due to the fact that

$\|g\|_{L^{2}(B)}=\left(\int_{B}\lvert
g\rvert^{2}\right)^{1/2}\leq\|g\|_{L^{\infty}(B)}=\|g\|_{L^{\infty}(B)}.$

Taking $\epsilon_{0}=\epsilon/(4C_{F})$ achieves the sought result. ∎

We further investigate how the constant $C_{K}$ from Theorem 3 behaves as
functions of $M$ and $s$. Let $K(x)=\exp(ix)$ be an example kernel,
$x\in[-M,M]^{d}$. We notice that $a^{M}_{s}=M(s+s^{-1})/2$ for $s>2$, is the
larger axis, and therefore the maximal norm of $K$ on $E^{M}_{s}$ is given by
$K(a^{M}_{s})$:

$\max_{x}\lvert
K(x)\rvert\leq\exp(M{\textstyle\frac{s+s^{-1}}{2}})=C_{K}(s,M).$

In our setting, inputs are in the interval $t=\omega\cdot x\in[-dM,dM]$, so we
may use the bounding constant

$\max_{t}\lvert
K(t)\rvert~{}\leq~{}\exp(dM{\textstyle\frac{s+s^{-1}}{2}})=C_{K}(s,dM).$

The resulting network $f^{\textnormal{MBL}}$ then has depth

$L_{\epsilon}~{}=~{}\mathcal{O}\left(\frac{1}{\log_{2}s}\left(dM\frac{s+s^{-1}}{2}+\log_{2}\frac{C_{F}}{\epsilon}\right)\right)$

and

$G_{\epsilon}=\mathcal{O}\left(\frac{C_{F}^{2}}{\epsilon^{2}\log_{2}s}\left(dM\frac{s+s^{-1}}{2}+\log_{2}\frac{C_{F}}{\epsilon}\right)\right)$

neurons. In this scenario, we see that both a large band $M$ and a large
dimension $d$ will linearly affect the first term.

See 4

###### Proof.

Let $f\in\mathcal{B}_{2r,2}$, and $M>1$. Similar to the proof of Theorem 5, we
define the bandlimiting of $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ by

$f_{M}~{}=~{}\mathcal{F}^{-1}(\mathcal{F}{f}\mathbbm{1}_{[-M,M]^{d}}).$

Let us define $F:[-M,M]^{d}\rightarrow\mathbb{C}$:

$F(\omega)~{}=~{}\frac{1}{(2\pi)^{d}}(\mathcal{F}f)(\omega),$

and $K(x)=\exp(ix)$. We then have the following identity:

$f_{M}(x)~{}=~{}\int_{[-M,M]^{d}}F(\omega)K(\omega\cdot
x)~{}\textnormal{d}\omega~{}=~{}\int_{[-M,M]^{d}}{\textstyle\frac{1}{(2\pi)^{d}}}\mathcal{F}f(\omega)\exp(i\omega\cdot
x)~{}\textnormal{d}\omega.$

It is then easy to see that $f_{M}\in{\mathcal{H}_{K,M}(B)}$. We choose
$M=(2/\epsilon)^{1/r}$. Using the same derivations as in the proof of Theorem
5, we seek to approximate $f_{M}$ with a network $f^{\textnormal{RS}}$ such
that

$\|f_{M}-f^{\textnormal{RS}}\|_{L_{2}(B)}~{}\leq~{}\epsilon/2.$

We then arrive at

$\displaystyle\|f-f^{\textnormal{RS}}\|_{L_{2}(B)}{}$
$\displaystyle\leq~{}\|f-f_{M}\|_{L_{2}(B)}+\|f_{M}-f^{\textnormal{RS}}\|_{L_{2}(B)}$
(7) $\displaystyle\leq~{}M^{-r}+\epsilon/2~{}\leq~{}\epsilon.$

We consider that $C_{F}=\int_{[-M,M]^{d}}\lvert
F(\omega)\rvert~{}\textnormal{d}\omega=\frac{1}{(2\pi)^{d}}\int_{[-M,M]^{d}}\lvert\mathcal{F}{f}(\omega)\rvert~{}\textnormal{d}\omega\leq
1$, where the inequality is due to the definition of $\mathcal{B}_{2r,2}$. The
kernel $K(t)=\exp(it)$ takes as input $t=\omega\cdot x$, for $x\in B$ and
$\omega\in[-M,M]^{d}$. Therefore, $t\in[-dM,dM]$, and
$K:[-dM,dM]\rightarrow\mathbb{R}$. We note that $K$ is continuable to the
Bernstein 4-ellipse $E_{4}^{dM}$. We notice that $a^{dM}_{4}=dM(4+4^{-1})/2$
is the larger axis, and therefore the maximal norm of $K$ on $E^{dM}_{s}$ is
given by $K(a^{dM}_{4})$:

$C_{K}~{}=~{}\max_{t}\lvert
K(t)\rvert~{}\leq~{}\exp(dM{\textstyle\frac{4+4^{-1}}{2}}).$

Further, for any $t\in\mathbb{R}$ we have $\lvert K(t)\rvert\leq 1=D_{K}$.

Using Theorem 3.2 from (Montanelli et al., 2021) we can construct a deep ReLU
network $f^{\textnormal{RS}}$ such that

$\|f_{M}-f^{\textnormal{RS}}\|_{L_{2}(B)}~{}\leq~{}\epsilon/2$

whose depth is

$\displaystyle L_{\epsilon}{}$
$\displaystyle\leq~{}C_{1}\frac{1}{\log_{2}^{2}4}\log_{2}^{2}{\frac{2C_{F}C_{K}}{\epsilon}}$
(8)
$\displaystyle\leq~{}C_{2}\frac{1}{\log_{2}^{2}4}\left(\log_{2}{\frac{{\exp(dM\frac{4+4^{-1}}{2})}}{\epsilon}}\right)^{2}$
$\displaystyle\leq~{}12C_{2}\left(d\left(\frac{2}{\epsilon}\right)^{\frac{1}{r}}-\log_{2}{\frac{1}{\epsilon}}\right)^{2}$
$\displaystyle\leq~{}C_{3}d^{2}\epsilon^{-\frac{2}{r}},$

for some constants $C_{1},C_{2},C_{3}>0$. In addition, the number of neurons
can be bounded by

$\displaystyle G_{\epsilon}{}$
$\displaystyle\leq~{}C^{\prime}_{1}{C_{F}^{2}}\frac{1}{\epsilon^{2}\log_{2}^{2}4}\log_{2}^{2}{\frac{2C_{K}C_{F}}{\epsilon}}$
(9)
$\displaystyle\leq~{}C^{\prime}_{2}\frac{1}{\epsilon^{2}\log_{2}^{2}4}\left(\log_{2}{\frac{{\exp(dM\frac{4+4^{-1}}{2})}}{\epsilon}}\right)^{2}$
$\displaystyle\leq~{}\frac{12C^{\prime}_{2}}{\epsilon^{2}}\left(d\left(\frac{2}{\epsilon}\right)^{\frac{1}{r}}-\log_{2}{\frac{1}{\epsilon}}\right)^{2}$
$\displaystyle\leq~{}C^{\prime}_{3}d^{2}\epsilon^{-(2+\frac{2}{r})},$

for some constants $C^{\prime}_{1},C^{\prime}_{2},C^{\prime}_{3}>0$. ∎