summaries: The paper proves upper and lower bounds on neural networks for approximating Korobov functions $X^{2, \infty}$. Upper and lower bounds match for approximation in $L^\infty$ norm sense, and the rate is free of the curse of data dimensionality. The scope of network architectures discussed is extensive, including shallow (2-layer) networks, deep networks with ReLU(-like) activation functions and Sigmoidal activation functions.

summaries: This paper studies what function class can be efficiently approximated by neural networks. This paper focuses on a special function class, namely the Korobov function space $X^{2, \infty}$, which contains function with $L^\infty$ bounded weak $\alpha$-order derivative, where $\| \alpha \|_\infty \le 2$. This is a local constraint on the local smoothness of the function space. This paper shows that shallow (with depth=$2$) and deep neural networks can efficiently approximate $X^{2, \infty}$, and the number of parameters does not scale with $\varepsilon^{-\mathrm{poly}(d)}$, thus efficiently escaping the curse of dimensionality. Furthermore, this paper shows the optimality of their parameters bound by showing a matching lower bound.

summaries: This paper studies the ability of shallow and deep neural networks to approximate Korobov functions, and analyses their representation power in terms of the number of used parameters. The authors first show that 2 layers neural networks using common activation functions can approximate any Korobov function within eps error in infinity norm using O(eps^{-1/2} (log 1/eps)^{3(d-1)/2}) parameters. This result improves the existing upper bound of O(eps^{-d/r}) parameters for approximating Sobolev functions in W^{r,p} using 1-hidden layer neural networks, hence reducing the curse of dimensionality.  For deep neural network, this paper provides a new result, showing that neural networks with depth O(log d) and O(eps^{-1/2} (log 1/eps)^{3(d-1)/2}) approximate Korobov functions in X^{2, infinity} within eps error in L-infinity norm. This improves the result of [1], by requiring a depth independent of the required accuracy. However, the current work requires a C^2 and non-linear activation function, and is hence not applicable to ReLU.  Finally, the authors show that any continuous function approximator for the Korobov space requires O(eps^{-1/2} (log 1/eps)^{(d-1)/2}) parameters for achieving error eps, hence matching the previous upper bound for NNs up to factor (log 1/eps)^{d-1}.  [1] Hadrien Montanelli, Haizhao Yang, and Qiang Du. Deep ReLU networks overcome the curse of dimensionality for bandlimited functions

summaries: This paper studies approximation capabilities of neural networks for the purpose of approximating Korobov functions which are multivariate functions of bounded second mixed derivatives.  The paper presents a complete study for approximating such functions with NNs: they study shallow nets and show that 2 layers with ReLUs and total #neurons of O(1/eps log^{1.5d}(1/eps))  where d is the dimension, can \eps-approximate  Korobov functions. Moreover, by allowing larger depths, close to logd, they can get a better depedence on \eps. Finally, they prove that any continuous function approximator requires a #params close to their upper bound in order to approximation Korobov functions.  This gives a complete picture for how Korobov functions behave wrt to function approximation with shallow or deep nets.

abstractText: In this paper, we analyze the number of neurons and training parameters that a neural network needs to approximate multivariate functions of bounded second mixed derivatives — Korobov functions. We prove upper bounds on these quantities for shallow and deep neural networks, drastically lessening the curse of dimensionality. Our bounds hold for general activation functions, including ReLU. We further prove that these bounds nearly match the minimal number of parameters any continuous function approximator needs to approximate Korobov functions, showing that neural networks are near-optimal function approximators.

authors: Montanelli Du

title: 2019) and numerical analysis literature

venue: (Novak,

title: Let X be a Banach space and let K ⊂ X

title: Approximation and estimation bounds for artificial neural networks

venue: Machine learning,

title: Dünne Gitter und deren Anwendung bei der adaptiven Lösung der dreidimensionalen Poisson-Gleichung

venue: Technische Universität München,

authors:
Gilles Deslauriers
Serge Dubuc

title: Symmetric iterative interpolation processes

venue: In Constructive approximation,

authors:
Ronald A DeVore
Ralph Howard
Charles Micchelli

title: Optimal nonlinear approximation

venue: Manuscripta mathematica,

authors:
Kurt Hornik
Maxwell Stinchcombe
Halbert White

title: Multilayer feedforward networks are universal approximators

venue: Neural networks,

authors:
Masaaki Imaizumi
Kenji Fukumizu

title: Deep neural networks learn non-smooth functions effectively

venue: In The 22nd international conference on artificial intelligence and statistics,

authors:
Jason M Klusowski
Andrew R Barron

title: Risk bounds for high-dimensional ridge function combinations including neural networks

venue: arXiv preprint arXiv:1607.01434,

title: Approximation by combinations of relu and squared relu ridge functions with l1 and l0 controls

venue: IEEE Transactions on Information Theory,

authors:
Michael Kohler
Adam Krzyżak

title: Adaptive regression estimation with multilayer feedforward neural networks

venue: Nonparametric Statistics,

title: Nonparametric regression based on hierarchical interaction models

authors:
Michael Kohler
Jens Mehnert

title: Analysis of the rate of convergence of least squares neural network regression estimates in case of measurement errors

venue: Neural Networks,

title: Approximate solution of integral equations

venue: Doklady Akademii Nauk SSSR,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

venue: Communications of the ACM,

authors:
Shiyu Liang
Rayadurgam Srikant

title: Why deep neural networks for function approximation

venue: arXiv preprint arXiv:1610.04161,

authors:
Henry W Lin
Max Tegmark
David Rolnick

title: Why does deep and cheap learning work so well

venue: Journal of Statistical Physics,

title: Neural networks for optimal approximation of smooth and analytic functions

venue: Neural computation,

title: Eignets for function approximation on manifolds

venue: Applied and Computational Harmonic Analysis,

authors:
Hrushikesh N Mhaskar
Qianli Liao
Tomaso Poggio

title: Learning functions: when is deep better than shallow

venue: arXiv preprint arXiv:1603.00988,

authors:
Hadrien Montanelli
Qiang Du

title: New error bounds for deep ReLU networks using sparse grids

venue: SIAM Journal on Mathematics of Data Science,

authors:
Hadrien Montanelli
Haizhao Yang
Qiang Du

authors:
Ryumei Nakada
Masaaki Imaizumi

title: Adaptive approximation and estimation of deep neural network with intrinsic dimensionality

title: Deterministic and stochastic error bounds in numerical analysis

authors:
Philipp Petersen
Felix Voigtlaender

title: Optimal approximation of piecewise smooth functions using deep ReLU neural networks

title: Deep ReLU network approximation of functions on a manifold

venue: arXiv preprint arXiv:1908.00695,

authors:
David Silver
Aja Huang
Chris J Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

title: Mastering the game of Go with deep neural networks and tree

venue: search. Nature,

title: Quadrature and interpolation formulas for tensor products of certain classes of functions

venue: In Doklady Akademii Nauk,

title: Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality

venue: arXiv preprint arXiv:1810.08033,

title: Benefits of depth in neural networks

venue: In Conference on learning theory,

authors:
E Weinan
Chao Ma
Lei Wu

title: Barron spaces and the compositional function spaces for neural network models

title: Error bounds for approximations with deep ReLU networks

authors:
Ch Zenger
W Hackbusch

title: Parallel algorithms for partial differential equations

venue: In Notes on Numerical Fluid Mechanics,

heading: 1 INTRODUCTION

text:
Neural networks have known tremendous success in the past years in many applications such as computer vision and pattern detection (Krizhevsky et al., 2017; Silver et al., 2016). A natural question that arises is how to explain their practical success theoretically. Neural networks are shown to be universal (Hornik et al., 1989): any Borel-measurable function can be approximated arbitrarily well by a neural network provided the network has a sufficient number of neurons. Furthermore, universality holds for as low as 1-hidden-layer neural network with reasonable activation functions. However, these results do not specify the number of neurons and parameters to train needed for this approximation. If these numbers are unreasonably high, the universality of neural networks would not explain their practical success.
We are interested in evaluating the number of neurons and training parameters needed to approximate a given function within with a neural network. An interesting question is how do these numbers scale with and the dimensionality of the problem, that is, the number of variables of the function. Mhaskar (1996) showed that any function of the Sobolev space of order r and dimension d can be approximated within with a 1-layer neural network with O( − dr ) neurons and an infinitely differentiable activation function. This bound exhibits the curse of dimensionality: the number of neurons needed for an −approximation scales exponentially in the dimension of the problem d. Thus, Mhaskar’s bound raises the question of whether this curse is inherent to neural networks.
DeVore et al. (1989) showed an important result towards answering this question. They proved that any continuous function approximator (a notion we formalize in Section 5) that approximates all Sobolev functions of order r and dimension dwithin , needs at least Θ( − d r ) parameters. This result bridges the gap with Mhaskar’s bound and confirms that neural networks cannot escape the curse of dimensionality for the Sobolev space. A main question is therefore for which set of functions can neural networks break this curse of dimensionality.
One way to circumvent the curse of dimensionality is to restrict considerably the considered space of functions and focus on functions with specific structures adapted to neural networks. For example, Mhaskar et al. (2016) showed that compositional functions with regularity r can be approximated within with deep neural networks with O(d · − 2r ) neurons. Other structural constraints have been considered for compositions of functions (Kohler & Krzyżak, 2016), piecewise smooth functions (Petersen & Voigtlaender, 2018; Imaizumi & Fukumizu, 2019), or structures on the data space e.g. lying on a manifold (Mhaskar, 2010; Nakada & Imaizumi, 2019; Schmidt-Hieber, 2019). Approximation bounds have also been obtained for the function approximation from data under smoothness constraints (Kohler & Krzyżak, 2005; Kohler & Mehnert, 2011) and specifically on mixed smooth Besov spaces which are known to circumvent the curse of dimensionality (Suzuki, 2018). An-
other example is the class of Sobolev functions of order d/α and dimension d for which Mhaskar’s bound becomes O( −α). Recently, Montanelli et al. (2019) considered bandlimited functions and showed that they can be approximated within by deep networks with depth O((log 1 )
2) and O( −2(log 1 )
2) neurons. Weinan et al. (2019) showed that the closure of the space of 2-layer neural networks with a particular regularity (namely a restriction on the size of the network’s weights) is the Barron space. They further show that Barron functions can be approximated within with 2-layer networks with O( −2) neurons. Similar line of work restrict the function space with spectral conditions that allows functions to be written as limits of shallow networks (Barron, 1994; Klusowski & Barron, 2016; 2018).
In this work, we are interested in more general and generic spaces of functions. Our space of interest is the space of multivariate functions of bounded second mixed derivatives, namely the Korobov space. This space is included in the Sobolev space but is reasonably large and general. The Korobov space presents two motivations. The first motivation is theoretical: it is a natural candidate for a large and general space included in the Sobolev space where numerical approximation methods can overcome the curse of dimensionality to some extent (see Section 2.1). The second motivation is practical: Korobov spaces are useful for solving partial differential equations (Korobov, 1959) and have been used in the context of high-dimensional function approximation (Zenger & Hackbusch, 1991; Zenger, 1991). Recently, Montanelli & Du (2019) showed that deep neural networks with depth O(log 1 ) and O( − 12 (log 1 ) 3(d−1)
2 +1) neurons can approximate Korobov functions within , lessening the curse of dimensionality for deep neural networks asymptotically in . While they used deep structures to prove their result, the question of whether shallow neural networks also break the curse of dimensionality for the Korobov space remains open.
In this paper, we study deep and shallow neural network’s approximation power for the Korobov space and make the following contributions:
• Representation power of shallow neural networks. We prove that any Korobov function can be approximated within with a 2-layer neural network with ReLU activation function with O( −1(log 1 ) 3(d−1) 2 +1) neurons and O( − 12 (log 1 ) 3(d−1) 2 ) training parameters
(Theorem 3.1). We further extend this result to a large class of commonly used activation functions (Theorem 3.4). Asymptotically in , our bound can be written as O( −1−δ) for all δ > 0, and in that sense breaks the curse of dimensionality for shallow neural networks.
• Representation power of deep neural networks. We prove that any function of the Korobov space can be approximated within with a deep neural network of depth dlog2(d)e+1 independent of , with non-linear C2 activation function,O( − 12 (log 1 ) 3(d−1) 2 ) neurons and
O( − 12 (log 1 ) 3(d−1)
2 ) training parameters (Theorem 4.1). This result improves over the result in Montanelli & Du (2019) that constructed an approximating neural network with larger depthO(log 1 log d) –increasing with the precision – and larger number of neurons O( − 12 (log 1 ) 3(d−1) 2 +1). We note however that they used a different activation function,
namely ReLU. • Near-optimality of neural networks as function approximators. Under continuous
function approximators model introduced by DeVore et al. (1989), we prove that any continuous function approximator needs Θ( − 1 2 (log 1 ) d−1 2 ) parameters to approximate functions of the Korobov space within (Theorem 5.2). This lower bound nearly matches our established upper bounds on the number of training parameters needed by deep and shallow neural networks to approximate functions of the Korobov space, proving that deep and shallow neural networks are near-optimal function approximators of the Korobov space.
Table 1 summarizes our new bounds and some of the existing bounds on shallow and deep neural network approximation power for the Korobov space, Sobolev space and bandlimited functions. Our proofs are constructive and give explicit structures to construct such neural networks with ReLU and general activation functions. Our constructions rely on sparse grid approximation introduced by Zenger (1991), and studied in detail in Bungartz (1992); Bungartz & Griebel (2004). Specifically, we use the sparse grid approach to approximate smooth functions with sums of products then construct neural networks which approximate this structure. A key difficulty is to approximate the product function. In particular in the case of shallow neural networks, we propose, to the best of our knowledge, the first architecture approximating the product function with polynomial number of neurons.
To derive our lower bound on the number of parameters needed to approximate the Korobov space, we construct a linear subspace of the Korobov space, with large Bernstein width. This subspace is then used to apply a general lower bound on nonlinear approximation derived by DeVore et al. (1989).
The rest of the paper is structured as follows. In Section 2, we define the notions of interest, formalize our objective and introduce the sparse grids approach which will be key in our constructions. In Section 3 and 4, we prove our bounds on the number of neurons and training parameters needed by a neural network to approximate functions of the Korobov space. Section 3 provides bounds for shallow networks and Section 4 for deep networks. Finally, we formalize in Section 5 the notion of optimal continuous function approximators and prove our novel near-optimality result.

heading: 2 PRELIMINARIES

text:
We begin by presenting the basic definitions that will be used in the paper. In this work, we consider feed-forward neural networks, using a linear output neuron and a non-linear activation function σ : R→ R for the other neurons, such as the commonly-used rectified unit (ReLU) σ(x) = max(x, 0), the sigmoid σ(x) = (1 + e−x)−1 or the Heaviside function σ(x) = 1{x≥0}. Let d ≥ 1 be the dimension of the input. We define a 1-hidden-layer network with N neurons as
x 7→ N∑ k=1 ukσ(w > k x+ bk),
wherewk ∈ Rd, bk ∈ R for i = 1, . . . , N are the parameters of the network. A neural network with several hidden layers is obtained by feeding the outputs of a given layer as inputs to the next layer. We are interested in the expressive power of neural networks i.e. the ability to approximate a target function f : Rd → R with as few neurons as possible, on the unit hyper-cube Ω := [0, 1]d. Another relevant metric is the number of parameters that needs to be trained to approximate the function, that is, the number of parameters of the approximating network (uk, wk and bk) depending on the function to approximate. We will adopt L∞ norm as a measure of approximation error.
Let us now define some notations that are necessary to present the space of functions that we will approximate. For an integer r, we denote Cr the space of one dimensional functions differentiable r times and with continuous derivatives. In our analysis, we consider functions f with bounded mixed derivatives. For a multi-index α ∈ Nd, we define the derivative of order α, Dαf := ∂ |α|1f
∂x α1 1 ...∂x αd d
, where |α|1 = ∑d i=1 |αi|. Two common function spaces in a compact Ω ⊂ Rd are the Sobolev spacesW r,p(Ω) of functions having weak partial derivatives up to order r in Lp(Ω) and the Korobov spaces Xr,p(Ω) of functions vanishing at the boundary and having weak mixed second derivatives up to order r in Lp(Ω).
W r,p(Ω) = {f ∈ Lp(Ω) : Dαf ∈ Lp(Ω), |α|1 ≤ r}, Xr,p(Ω) = {f ∈ Lp(Ω) : f |∂Ω = 0, Dαf ∈ Lp(Ω), |α|∞ ≤ r}.
where ∂Ω denotes the boundary of Ω, |α|1 = ∑d i=1 |αi| and |α|∞ = supi=1,...,d |αi| are respectively the L1 and infinity norm. Note that Korobov spaces Xr,p(Ω) are subsets of Sobolev spaces W r,p(Ω). For p =∞, the usual norms on these spaces are given by
|f |W r,p(Ω) := max |α|1≤r ‖Dαf‖∞ , |f |Xr,p(Ω) := max|α|∞≤r ‖Dαf‖∞ ,
For simplicity we will write | · |2,∞ for | · |X2,∞ . We focus our analysis on approximating functions on the Korobov space X2,∞(Ω) for which the curse of dimensionality is drastically lessened and we show that neural networks are near-optimal. Intuitively, one of the key differences compared to the Sobolev space is that Korobov functions do not have high frequency oscillations in all directions at a time. Such functions are known to require an exponential number of neurons Telgarsky (2016) and are one of the main difficulties to approximating the Sobolev space which therefore exhibits the curse of dimensionality DeVore et al. (1989). On the contrary, the Korobov space prohibits such behaviour by ensuring that functions can be differentiable on all dimensions together. Further discussions on Korobov functions and concrete examples are provided in Appendix A.

heading: 2.1 THE CURSE OF DIMENSIONALITY

text:
In analysing neural networks representation power, we adopt the point of view of asymptotic results in (or equivalently, in the number of neurons), which is a well-established setting in the neural networks representation power literature (Mhaskar, 1996; Bungartz & Griebel, 2004; Yarotsky, 2017; Montanelli & Du, 2019) and numerical analysis literature (Novak, 2006). In the rest of the paper, for convenience, we use O notation which hide constants in d. For each result, full dependencies in d are provided in the appendix.
Previous efforts to quantify the number of neurons needed to approximate large general class of functions within showed that neural networks and most classical functional approximation schemes exhibit the curse of dimensionality. For example, in the case of Sobolev functions, Mhaskar proved the following approximation bound.
Theorem 2.1 (Mhaskar (1996)). Let p, r ≥ 1, and σ : R → R be an infinitely differentiable activation function, non-polynomial on any interval of R. Let > 0 sufficiently small. For any f ∈ W r,p, there exists a shallow neural network with one hidden layer, activation function σ, and O( − dr ) neurons approximating f within for the infinity norm.
Therefore, the approximation of Sobolev functions by neural networks suffers from the curse of dimensionality since the number of neurons needed grows exponentially with the input space dimension d. This curse is not due to poor performance of neural networks but rather to the choice of the Sobolev space. DeVore et al. (1989) proved that any learning algorithm with continuous parameters needs at least Θ( − d r ) parameters to approximate the Sobolev spaceW r,p. This shows that the class of Sobolev functions suffers inherently from the curse of dimensionality and no continuous function approximator can overcome it. We detail this notion later in Section 5.
The natural question that arises is whether there exists a reasonable and sufficiently large class of functions for which there is no inherent curse of dimensionality. We are interested in this case in the performance of neural networks in approximating this space of functions. Instead of the Sobolev space, we seek to add more regularity to be able to overcome the curse of dimensionality while having a reasonably large space. The Korobov space X2,∞(Ω)—functions with bounded mixed derivatives—is the natural candidate: it is known in the numerical analysis community as a reasonably large space where numerical approximation methods can lessen the curse of dimensionality (Bungartz & Griebel, 2004). Korobov functions have been introduced for solving partial differential equations (Korobov, 1959; Smolyak, 1963), and have then been used extensively in the context of high-dimensional function approximation (Zenger & Hackbusch, 1991; Bungartz & Griebel, 2004). This space of functions is included in the Sobolev space, but still reasonably large as the regularity condition concerns only second order derivatives. Two questions will be of interest. First, how many neurons and training parameters a neural network needs to approximate any Korobov function within in the L∞ norm? Second, how does neural network performance compare to the theoretically best possible function approximators for Korobov space?

heading: 2.2 SPARSE GRIDS AND HIERARCHICAL BASIS

text:
We review in this subsection the notion of sparse grids which will be key in our neural networks constructions to approximate Korobov functions. Sparse grids were introduced by Zenger Zenger (1991) and have since then been extensively used for high-dimensional function approximation. They have been proven to lessen the curse of dimensionality for Korobov spaces. We refer to Bungartz & Griebel (2004) for a thorough review of the topic.
The goal is to define discrete approximation spaces with basis functions. Instead of a classical uniform grid partition of the hyper-cube [0, 1]d involving nd components, where n is the number of partitions in each coordinate, the sparse grid approach uses a smarter partitioning of the cube preserving the approximation accuracy while drastically reducing the number of components of the grid. The construction involves a 1-dimensional mother function φ which is used to generate all the functions of the basis. For example, a simple choice for the building block φ is the standard hat function φ(x) := (1 − |x|)+. The hat function is not the only possible choice. In the latter proofs we will specify which mother function is used, in our case either the interpolates of Deslauriers & Dubuc (1989) (which we define rigorously later in our proofs) or the hat function φ which can be seen as the Deslaurier-Dubuc interpolet of order 1. These more elaborate mother functions enjoy more smoothness while essentially preserving the approximation power.
Assume the mother function has support in [−k, k]. For j = 1, . . . , d, it can be used to generate a set of local functions φlj ,ij : [0, 1] −→ R for all lj ≥ 1 and 1 ≤ ij ≤ 2lj −1 with support [ ij−k 2lj , ij+k 2lj ] as follows, φlj ,ij (x) := φ(2
ljx− ij), x ∈ [0, 1]. We then define a basis of d-dimensional functions by taking the tensor product of these 1-dimensional functions. For all l, i ∈ Nd with l ≥ 1 and 1 ≤ i ≤ 2l − 1 where 2l denotes (2l1 , . . . , 2ld), define φl,i(x) := ∏d j=1 φlj ,ij (xj), x ∈ Rd. For a fixed l ∈ Nd, we will consider the hierarchical increment space Wl which is the subspace spanned by the functions {φl,i : 1 ≤ i ≤ 2l − 1}, as illustrated in Figure 1,
Wl := span{φl,i, 1 ≤ i ≤ 2l − 1, ij odd for all 1 ≤ j ≤ d}. Note that in the hierarchical increment Wl, all basis functions have disjoint support. A key obser-
vation is that Korobov functions X2,p(Ω) can be expressed uniquely in this hierarchical basis. More precisely, there is a unique representation of u ∈ X2,p(Ω) as u(x) = ∑ l,i vl,iφl,i(x), where the sum is taken over all multi-indices l ≥ 1 and 1 ≤ i ≤ 2l − 1 where all components of i are odd. In particular, all basis functions are linearly independent. Notice that this sum is infinite, the objective is now to define a finite-dimensional subspace of X2,p(Ω) that will serve as an approximation space. Sparse grids use a carefully chosen subset of the hierarchical basis functions to construct the approximation space V (1)n := ⊕ |l|1≤n+d−1Wl. For the particular choice of the hat function for φ, Bungartz and Griebel Bungartz & Griebel (2004) showed that this choice of approximating space leads to a good approximating error.
Theorem 2.2 (Bungartz & Griebel (2004)). Let f ∈ X2,∞(Ω) and f (1)n be the projection of f on the subspace V (1)n . We have, ‖f−f (1)n ‖∞ = O ( 2−2nnd−1 ) . Furthermore, if vl,i denotes the coefficient of φl,i in the decomposition of f (1) n in V (1) n , then we have the upper bound |vl,i| ≤ 2−d2−2|l|1 |f |2,∞, for all l, i ∈ Nd with |l|1 ≤ n+ d− 1, 1 ≤ i ≤ 2l − 1 where i has odd components.

heading: 3 THE REPRESENTATION POWER OF SHALLOW NEURAL NETWORKS

text:
It has recently been shown that deep neural networks, with depth scaling with , lessen the curse of dimensionality on the numbers of neuron needed to approximate the Korobov space Montanelli &
Du (2019). However, to the best of our knowledge, the question of whether shallow neural networks with fixed universal depth — independent of and d — escape the curse of dimensionality as well for the Korobov space remains open. We settle this question by proving that shallow neural networks also lessen the curse of dimensionality for Korobov space.
Theorem 3.1. Let > 0. For all f ∈ X2,∞(Ω), there exists a neural network with 2 layers, ReLU activation, O( −1(log 1 ) 3(d−1) 2 +1) neurons, and O( − 12 (log 1 ) 3(d−1) 2 ) training parameters that approximates f within for the infinity norm.
In order to prove Theorem 3.1, we construct the approximating neural network explicitly. The first step is to construct a neural network architecture with two layers and O(d 32 − 12 log 1 ) neurons that approximates the product function p : x ∈ [0, 1]d 7−→ ∏n i=1 xi within for all > 0.
Proposition 3.2. For all > 0, there exists a neural network with depth 2, ReLU activation and O(d 32 − 12 log 1 ) neurons, that approximates the product function p : x ∈ [0, 1] d −→ ∏d i=1 xi within for the infinity norm. Sketch of proof The proof builds upon the observation that p(x) = exp( ∑d i=1 log xi). We construct an approximating 2-layer neural network where the first layer approximates log xi for 1 ≤ i ≤ d, and the second layer approximates the exponential. We illustrate the construction of the proof in Figure 2. More precisely, fix > 0. Consider the function h : x ∈ [0, 1] 7→ max(log x, log ). We approximate h within d with a piece-wise affine function withO(d 1 2 − 1 2 log 1 ) pieces and then represent this piece-wise affine function with a single layer neural network ĥ with the same number of neurons as the number of pieces (Lemma B.1, Appendix B.1). This 1-layer network verifies, therefore, ‖h − ĥ ‖∞ ≤ d . The first layer of our final network is the union of d copies of the 1-layer network ĥ : one for each dimension i, approximating log xi. Similarly, consider the exponential g : x ∈ R− 7→ ex. We construct a 1-layer neural network ĝ withO( − 1 2 log 1 ) neurons such that ‖g − ĝ ‖∞ ≤ . This will serve as second layer. Formally, the constructed approximation p̂ of the product function is p̂ = ĝ (∑d i=1 ĥ (xi) ) . This 2-layer neural network has O(d 32 − 12 log 1 ) neurons and verifies ‖p̂ − p‖∞ ≤ . We use this result to prove Theorem 3.1 and show that we can approximate any Korobov function f ∈ X2,∞(Ω) within with a 2-layer neural network of O( − 12 (log 1 ) 3(d−1) 2 ) neurons. Consider
the sparse grid construction of the approximating space V (1)n using the standard hat function as mother function to create the hierarchical basis Wl (introduced in Section 2.2). Recall that the approximation space is defined as V (1)n := ⊕ |l|1≤n+d−1Wl. The key idea is to construct a shallow neural network approximating the sparse grid approximation and then use the result of Theorem 2.2 to derive the approximation error. Let f (1)n be the projection of f on the subspace V (1) n defined in Section 2.2. f (1)n can be written as f (1) n (x) = ∑ (l,i)∈U(1)n vl,iφl,i(x), where U (1) n contains the
indices (l, i) of basis functions present in V (1)n . We can use Theorem 2.2 and choose n carefully such that f (1)n approximates f within for L∞ norm. The goal is now to approximate f (1) n with a shallow neural network. Note that the basis functions can be written as a product of univariate functions φl,i = ∏d j=1 φlj ,ij . We can therefore use a similar structure to the product approximation of Proposition 3.2 to approximate the basis functions. Specifically, the first layer approximate the d(2n − 1) = O( − 12 (log 1 ) d−1 2 ) terms log φlj ,ij necessary to construct the basis functions of V (1)n and a second layer to approximate the exponential in order to obtain approximations of the O(2nnd−1) = O( − 12 (log 1 ) 3(d−1) 2 ) basis functions of V (1)n . We provide a detailed figure illustrating the construction, Figure 5 in Appendix B.3.
The shallow network that we constructed in Theorem 3.1 uses the ReLU activation function. We extend this result to a larger class of activation functions which include commonly used ones. Definition 3.3. A sigmoid-like activation function σ : R → R is a non-decreasing function having finite limits in ±∞. A ReLU-like activation function σ : R → R is a function having a horizontal asymptote in −∞ i.e. σ is bounded in R−, and an affine (non-horizontal) asymptote in +∞, i.e. there exists b > 0 such that σ(x)− bx is bounded in R+.
The majority of the commonly used activation functions fall into one of the two classes. Examples of sigmoid-like activations include the Heaviside, logistic, tanh, arctan and softsign activations, while ReLU-like activations include the ReLU, ISRLU, ELU and soft-plus activations. We extend Theorem 3.1 to all these activations. Theorem 3.4. For any approximation tolerance > 0, and for any f ∈ X2,∞(Ω) there exists a neural network with depth 2 and O( − 12 (log 1 ) 3(d−1) 2 ) training parameters that approximates f
within for the infinity norm, with O ( −1 log( 1 ) 3(d−1) 2 +1) (resp. O( − 32 log( 1 ) 3(d−1) 2 )) neurons for a ReLU-like (resp. sigmoid-like) activation.
We note that these results can further be extended to more general Korobov spaces Xr,p. Indeed, the main dependence of our neural network architectures in the parameters r and p arise from sparse grid approximation. Bungartz & Griebel (2004) show that results similar to Theorem 2.2 can be extended to various settings with the same sparse grid construction. For instance, we can use these results combined with our proposed architecture to show that the Korobov space Xr,∞ can be approximated in infinite norm by neural networks with O( − 1 r (log 1 ) r+1 r (d−1)) training parameters and same number of neurons up to a polynomial factor in .

heading: 4 THE REPRESENTATION POWER OF DEEP NEURAL NETWORKS

text:
Montanelli and Du Montanelli & Du (2019) used the sparse grid approach to construct deep neural networks with ReLU activation, approximating Korobov functions with O( − 12 (log 1 ) 3(d−1) 2 +1) neurons, and depth O(log 1 ) for the L ∞ norm. We show that we can improve this bound for deep neural networks with C2 non-linear activation functions. We prove that we only need O( − 12 (log 1 ) 3(d−1) 2 ) neurons and fixed depth, independent of , to approximate the unit ball of the Korobov space within in the L∞ norm. Theorem 4.1. Let σ ∈ C2 be a non-linear activation function. Let > 0. For any function f ∈ X2,∞(Ω), there exists a neural network of depth dlog2 de + 1, with ReLU activation on the first layer and activation function σ for the next layers, O( − 12 (log 1 ) 3(d−1) 2 ) neurons, and O( − 12 (log 1 ) 3(d−1) 2 ) training parameters approximating f within for the infinity norm.
Compared to the bound of shallow networks, Theorem 3.1, the number of neurons for deep networks is lower by a factorO( √ ), while the number of training parameters is exactly the same. This result indicates that deep neural networks are more efficient than shallow neural network in the sense that shallow networks need more “inactive” neurons to reach the same approximation power as deep networks while having the same number of parameters. This gap in the number of the “inactive” neurons can be consequent in practice, as in common used architectures, we do not know exactly which neurons to train and which neurons to fix.
We also point out that this new bound on the number of parameters and neurons matches the approximation power of sparse grids. In fact, sparse grids use Θ( − 1 2 (log 1 ) 3(d−1) 2 ) parameters (weights of basis functions) to approximate Korobov functions within . Our construction in Theorem 4.1 shows that deep neural networks with fixed depth in can fully encode sparse grids approximators. Neural networks are therefore more powerful function approximators. In particular, any sparse grid approximation using O(N( )) parameters, can be represented exactly by a neural network using O(N( )) neurons.
2 ) neurons and depth dlog2 de+ 1.
The deep approximating neural network (see Figure 3) has a very similar structure to our construction of an approximating shallow network in the Theorem 3.1. The main difference lies in the approximation of the product function. Instead of using a 2-layer neural network, we now make use of a deep network. The following result of Lin et al. (Lin et al., 2017, Appendix A) shows that deep neural networks can represent exactly the product function. Proposition 4.2 (Lin et al. (2017)). Let σ be C2 non linear activation function. For any approximation error > 0, there exists a neural network with dlog2 de hidden layers and activation σ, using at most 8d neurons arranged in a binary tree network that approximates the product function ∏d i=1 xi on [0, 1]d within for the infinity norm.
An important remark is that the structure of the constructed neural network is independent of . In particular, the depth and number of neurons is independent of the approximation precision , which we refer to as exact approximation. It is known that an exponential number of neurons is needed in order to exactly approximate the product function with a 1-layer neural network Lin et al. (2017), however, the question of whether one could approximate the product with a shallow network and a polynomial number of neurons, remained open. In Proposition 3.2, we answer positively to this question by constructing an -approximating neural network of depth 2 with ReLU activation and O(d 32 − 12 log 1 ) neurons. Using the same ideas as in Theorem 3.4, we can generalize this result to obtain an -approximating neural network of depth 2 withO(d 32 − 12 log 1 ) neurons for a ReLU-like activation, or O(d2 −1 log 1 ) neurons for a sigmoid-like activation.

heading: 5 NEURAL NETWORKS ARE NEAR-OPTIMAL FUNCTION APPROXIMATORS

text:
In the previous sections, we proved and discussed upper bounds on the number of neurons and training parameters needed by deep and shallow neural networks to approximate the Korobov space
X2,∞(Ω). In this section, we investigate how good is the performance of neural networks as functional approximators. We prove a lower bound on the number of parameters needed by any continuous function approximator to approximate the Korobov space. We will show in particular that neural networks, deep and shallow, nearly match this lower bound, making them near-optimal function approximators. Let us first formalize the notion of continuous function approximators, following the framework of DeVore et al. DeVore et al. (1989).
For any Banach space X — one can think of X as a space of functions — and a subset K ⊂ X of elements to approximate, we define a continuous function approximator with N parameters as a continuous parametrization a : K → RN together with a reconstruction scheme which is a N - dimensional manifold MN : RN → X . For any element f ∈ K, the approximation given is MN (a(f)) : the parametrization a is derived continuously from the function f and then given as input to the reconstruction manifold that outputs an approximation function in X . The error of this function approximator is defined as EN,a,MN (K)X := supf∈K |f −MN (a(f))|X . The best function approximator for space K minimizes this error. The minimal error for space K is given by
EN (K)X = min a,MN EN,a,MN (K)X .
In other terms, a continuous function approximator with N parameters cannot hope to approximate K better than withinEN (K)X . A class of function approximators is a set of function approximators with a given structure. For example, neural networks with continuous parametrizations are a class of function approximators where the number of parameters corresponds to the number of training parameters i.e, the parameters of the network that depend on the desired function to approximate. We say that a class of function approximators is optimal for the space of functions K if it matches this minimal error asymptotically in N , within a constant multiplicative factor. In other words, the number of parameters needed by the class to approximate functions in K within matches asymptotically, within a constant, the least number of parametersN needed to satisfyEN (K)X ≤ . The norm considered in the approximation of the functions of K is the norm associated to the space X . DeVore et al. DeVore et al. (1989) showed that this minimum error EN (K)X admits a lower bound characterized by the Bernstein width of the subset K ⊂ X defined as
bN (K)X := sup XN+1
sup{ρ : ρU(XN+1) ⊂ K},
where the outer sup is taken over all N + 1 dimensional linear sub-spaces of X , and U(Y ) denotes the unit ball of Y for any linear subspace Y of X . Theorem 5.1 (DeVore et al. (1989)). Let X be a Banach space and let K ⊂ X . Then, EN (K)X ≥ bN (K)X .
We prove a lower bound on the least number of parameters any class of continuous function approximators needs to approximate functions of the Korobov space.
Theorem 5.2. Take X = L∞(Ω) and K = {f ∈ X2,∞(Ω) : |f |X2,∞(Ω) ≤ 1} the unit ball of the Korobov space. Then, there exists c > 0 such that EN (K)X ≥ cN2 (logN) d−1.
Equivalently, for > 0, a continuous function approximator approximating the unit Korobov ball within in L∞ norm uses at least Θ( − 1 2 (log 1 ) d−1 2 ) parameters.
This lower bound matches within a logarithmic factor the upper bound on the number of training parameters needed by deep and shallow neural networks to approximate the Korobov space within : O( − 12 (log 1 ) 3(d−1) 2 ) (Theorem 3.1 and Theorem 4.1). It exhibits the same exponential dependence in d with base log 1 and the same main dependence on of − 12 . Note that the upper and lower bound can be rewritten as O( −1/2−δ) for all δ > 0. Moreover, our constructions in Theorem 3.1 and Theorem 4.1 are continuous, which comes directly from the continuity of the sparse grid parameters (see bound on vl,i in Theorem 2.2). Our bounds prove therefore that deep and shallow neural networks are near optimal classes of function approximators for the Korobov space.
Sketch of proof We seek an appropriate subspaceXN+1 in order to get lower bound the Bernstein width bN (K)X , which in turn provides a lower bound on the approximation error (Theorem 5.1). To do so, we use the Deslaurier-Dubuc interpolet of degree 2, φ(2) (see Figure 6) which is C2. Using the
sparse grids approach, we construct a hierarchical basis in X2,∞(Ω) using φ(2) as mother function and define XN+1 as the approximation space V (1) n . Here n is chosen such that the dimension of V (1) n is roughly N + 1. The goal is to estimate sup{ρ : ρU(XN+1) ⊂ K}, which will lead to a bound on bN (K)X . To do so, we upper bound the Korobov norm by the L∞ norm for elements of XN+1. For any function u ∈ XN+1 we can write u = ∑ l,i vl,i ·φl,i. Using a stencil representation of the coefficients vl,i, we are able to obtain an upper bound |u|X2,∞ ≤ Γd‖u‖∞ where Γd = O(22nnd−1). Then, bN (K)X ≥ 1/Γd which yields the desired bound. Interestingly, the subspace XN+1 our proof uses to show the lower bound is essentially the same as the subspace we use to approximate Koborov functions in our proof of the upper bounds (Theorem 3.1 and 4.1). The difference is in the choice of the interpolate φ to construct the basis functions, degree 2 for the former (which provides needed regularity for the proof), and 1 for the later.

heading: 6 CONCLUSION AND DISCUSSION

text:
We have proved new upper and lower bounds on the number of neurons and training parameters needed by shallow and deep neural networks to approximate functions of the Korobov space. Our bounds show that shallow and deep networks, not only lessen the curse of dimensionality but are also near-optimal function approximators of the space of Korobov functions. This work therefore contributes to understanding the practical success of neural networks theoretically.
Our work suggests several extensions. First, we have constructed throughout the paper explicitly deep and shallow structures nearly reaching the optimal number of parameters needed to approximate Korobov functions. It would be very interesting to see if the theoretical near-optimality of these structures translates into powerful empirical performance. While commonly used structures (e.g. Convolution Neural Networks, or Recurrent Neural Networks) are motivated by properties of the data such as symmetries, our structures are motivated by theoretical insights on how to optimally approximate a large general class of functions with a given number of neurons and parameters. These new structures might prove to be competitive with commonly used structures and constitute new building blocks of neural networks in learning tasks.
Second, our upper bounds (Theorem 3.1 and 4.1) nearly match our lower bound (Theorem 5.2) on the least number of training parameters needed to approximate functions of the Korobov space. We wonder if it is possible to close the gap between these bounds and prove neural network’s optimality as function approximators. Using our approach, proving neural network’s optimality would boil down to proving that sparse grids are optimal function approximators by improving our lower bound to match sparse grid number of parameters O( − 12 (log 1 ) 3(d−1) 2 ).
Finally, we showed the near-optimality of neural networks among the set of continuous function approximators. An interesting question would be to explore lower bounds (analog to Theorem 5.2) that we can get when considering larger sets of function approximators. One possibility would be that the curse of dimensionality vanishes for the Sobolev space when considering discontinuous function approximators. In this case, it would be insightful to investigate whether some discontinuous neural network construction can break the curse of dimensionality for the Sobolev space leading to stronger approximation results. The question is then whether neural networks are still near-optimal in these larger sets of function approximators.

heading: APPENDIX

heading: A ON KOROBOV FUNCTIONS

text:
In this section, we further discuss Korobov functions X2,p(Ω). Korobov functions enjoy more smoothness than Sobolev functions: smoothness for X2,p(Ω) is measured in terms of mixed derivatives of order two. Korobov functions X2,p(Ω) can be differentiated twice in each coordinates simultaneously, while Sobolev W 2,p(Ω) functions can only be differentiated twice in total. For example, in two dimensions, for a function f to be Korobov it is required to have
∂f ∂x1 , ∂f ∂x2 , ∂2f ∂2x1 , ∂2f ∂2x2 , ∂2f ∂x1∂x2 , ∂3f ∂2x1∂x2 , ∂3f ∂x1∂2x2 ,
∂4f
∂2x1∂2x2 ∈ Lp(Ω),
while for f to be Sobolev it requires only
∂f ∂x1 , ∂f ∂x2 , ∂2f ∂2x1 , ∂2f ∂2x2 , ∂2f ∂x1∂x2 ∈ Lp(Ω).
The former can be seen from |α|∞ ≤ 2 and the latter from |α|1 ≤ 2 in the definition of Xr,p(Ω) and W r,p(Ω).
We now provide intuition on why Korobov functions are easier to approximate. One of the key difficulties in approximating Sobolev functions are possible high frequency oscillations which may require an exponential number of neurons (Telgarsky, 2016). For instance, consider functions which have similar structure to W(n...n) (defined in Subsection 2.2): for any smooth basis function φ with support on the unit cube (see Figure 6 for example), consider the linear function space formed by linear combinations of dilated function φ with support on each cube d-dimensional grid of step 2−n. This corresponds exactly to the construction of W(n...n) which uses the product of hat function on each dimension as basis function φ. This function space can have strong oscillations in all directions at a time. The Korobov space prohibits such behavior by ensuring that functions can be differentiated twice on each dimension, simultaneously. As a result, functions cannot oscillate in all directions at a time without having large Korobov norm. We end this paragraph by comparing the Korobov space to the space of bandlimited functions which was shown to avoid the curse of dimensionality (Montanelli et al., 2019). These are functions for which the support frequency components is restricted to a fixed compact. Intuitively, approximating these functions can be achieved because the set of frequencies is truncated to a compact, which then allows to sample frequencies and obtain
approximation guarantees. Instead of imposing a hard constraint of cutting high frequencies, the Korobov space asks for smoothness conditions which do not prohibit high frequencies but rather impose a budget for high frequency oscillations. We precise this idea in the next example.
A concrete example of Korobov functions is given by an analogous of the function space V (1)n which we used as approximation space in the proof of our results (see Section 2.2). Similarly to the previous paragraph, one should use a smooth basis function to ensure differentiability. Recall that V (1) n is defined as
V (1)n := ⊕
|l|1≤n+d−1
Wl.
Intuitively, this approximation space introduces a ”budget” of oscillations for all dimensions through the constraint ∑d i=1 li ≤ n + d − 1. As a result, dilations of the basis function can only occur in a restricted set of directions at a time, which ensures that the Korobov norm stays bounded.

heading: B PROOFS OF SECTION 3

heading: B.1 APPROXIMATING THE PRODUCT FUNCTION

text:
In this subsection, we construct a neural network architecture with two layers and O(d 32 − 12 log 1 ) neurons that approximates the product function p : x ∈ [0, 1]d 7−→ ∏n i=1 xi within for all > 0, which proves Proposition 3.2. We first prove a simple lemma to represent univariate piece-wise affine functions by shallow neural networks.
Lemma B.1. Any one dimensional continuous piece-wise affine function with m pieces is representable exactly by a shallow neural network with ReLU activation, with m neurons on a single layer.
Proof. This is a simple consequence from Proposition 1 in Yarotsky (2017). We recall the proof for completeness. Let x1 ≤ · · · ≤ xm−1 be the subdivision of the piece-wise affine function f . We use a neural network of the form
g(x) := f(x1) + m−1∑ k=1 wk(x− xk)+ − w0(x1 − x)+,
where w0 is the slope of f on the piece ≤ x1, w1 is the slope of f on the piece [x1, x2],
wk = f(xk+1)− f(x1)−
∑k−1 i=1 wi(xk+1 − xi)
xk+1 − xk ,
for k = 1, · · · ,m−2, and wm−1 = w̃− ∑m−2 k=1 wk where w̃ is the slope of f on the piece≥ xm−1. Notice that f and g coincide on all xk for 1 ≤ k ≤ m − 1. Furthermore, g has same slope as f on each pieces, therefore, g = f .
We can approximate univariate right continuous functions by piece-wise affine functions, and then use Lemma B.1 to represent them by shallow neural networks. The following lemma shows that O( −1) neurons are sufficient to represent an increasing right-continuous function with a shallow neural network.
Lemma B.2. Let f : I −→ [c, d] be a right-continuous increasing function where I is an interval, and let > 0. There exists a shallow neural network with ReLU activation, with
⌈ d−c ⌉ neurons on
a single layer, that approximates f within for the infinity norm. Proof. Let m = ⌊ d−c ⌋ Define a subdivision of the image interval c ≤ y1 ≤ . . . ≤ ym ≤ d where
yk = c+k for k = 1, . . . ,m. Note that this subdivision contains exactly ⌈ d−c ⌉ pieces. Now define a subdivision of I , x1 ≤ x2 ≤ . . . ≤ xm by
xk := sup{x ∈ I, f(x) ≤ yk},
for k = 1, . . . ,m. This subdivision stills has ⌈ d−c ⌉ pieces. We now construct our approximation
function f̂ on I as the continuous piece-wise affine function on the subdivision x1 ≤ . . . ≤ xm such that f̂(xk) = yk for all 1 ≤ k ≤ m and f̂ is constant before x1 and after xm (see Figure 4). Let x ∈ I .
• If x ≤ x1, because f is increasing and right-continuous, c ≤ f(x) ≤ f(x1) ≤ y1 = c+ . Therefore |f(x)− f̂(x)| = |f(x)− (c+ )| ≤ .
• If xk < x ≤ xk+1, we have yk < f(x) ≤ f(xk+1) ≤ yk+1. Further note that yk ≤ f̂(x) ≤ yk+1. Therefore |f(x)− f̂(x)| ≤ yk+1 − yk = .
• If xm < x, then ym < f(x) ≤ d. Again, |f(x)− f̂(x)| = |f(x)− ym| ≤ d− ym ≤ .
Therefore ‖f − f̂‖∞ ≤ . We can now use Lemma B.1 to end the proof.
If the function to approximate has some regularity, the number of neurons needed for approximation can be significantly reduced. In the following lemma, we show that O( − 12 ) neurons are sufficient to approximate a C2 univariate function with a shallow neural network. Lemma B.3. Let f : [a, b] −→ [c, d] ∈ C2, and let > 0. There exists a shallow neural network with ReLU activation, with 1√
2 min(
∫ √ |f ′′|(1 + µ(f, )), (b − a) √ ‖f ′′‖∞) neurons on a single
layer, where µ(f, )→ 1 as → 0, that approximates f within for the infinity norm.
Proof. See Appendix B.2.1.
We will now use the ideas of Lemma B.2 and Lemma B.3 to approximate a truncated log function, which we will use in the construction of our neural network approximating the product. Corollary B.4. Let > 0 sufficiently small and δ > 0. Consider the truncated logarithm function log : [δ, 1] −→ R. There exists a shallow neural network with ReLU activation, with − 12 log 1δ neurons on a single layer, that approximates f within for the infinity norm.
Proof. See Appendix B.2.2.
We are now ready to construct a neural network approximating the product function and prove Proposition 3.2. The proof builds upon on the observation that ∏d i=1 xi = exp( ∑d i=1 log xi). We construct an approximating 2-layer neural network where the first layer computes log xi for 1 ≤ i ≤ d, and the second layer computes the exponential. We illustrate the construction of the proof in Figure 2.
Proof of Proposition 3.2 Fix > 0. Consider the function h : x ∈ [0, 1] 7→ max(log x, log ) ∈ [log , 0]. Using Corollary B.4, there exists a neural network ĥ : [0, 1] −→ [log , 0] with 1 + dd 12 − 12 log 1 e neurons on a single layer such that ‖h − ĥ ‖∞ ≤
d . Indeed, one can take
the -approximation of h : x ∈ [ , 1] 7→ log x ∈ [log , 0], then extend this function to [0, ] with a constant equal to log . The resulting piece-wise affine function has one additional segment corresponding to one additional neuron in the approximating function. Similarly, consider the exponential g : x ∈ R− 7→ ex ∈ [0, 1]. Because g is right-continuous increasing, we can use Lemma B.3 to construct a neural network ĝ : R− −→ [0, 1] with 1 + ⌈ 1√ 2 log 1 ⌉ neurons on a single layer such that ‖g − ĝ ‖∞ ≤ . Indeed, again one can take the -approximation of g : x ∈ [log , 0] 7→ ex ∈ [0, 1], then extend this function to (−∞, log ] with a constant equal to . The corresponding neural network has an additional neuron. We construct our final neural network φ̂ (see Figure 2) as
φ̂ = ĝ ( d∑ i=1 ĥ (xi) ) .
Note that φ̂ can be represented as a 2-layer neutral network: the first layer is composed of the union of the 1+dd 12 − 12 log 1 e neurons composing each of the 1-layer neural networks ĥ i : x ∈ [0, 1]d 7→
ĥ (xi) ∈ R for each dimension i ∈ {1, . . . , d}. The second layer is composed of the 1+ ⌈
1√ 2 log 1 ⌉ neurons of ĝ . Hence, the constructed neural network φ̂ has O(d 3 2 − 1 2 log 1 ) neurons. Let us now
analyze the approximation error. Let x ∈ [0, 1]d. For the sake of brevity, denote ŷ = ∑d i=1 ĥ (xi)
and y = ∑d i=1 log(xi). We have,
|φ̂ (x)− p(x)| ≤ |φ̂ (x)− exp(ŷ)|+ | exp(ŷ)− exp(y)| ≤ + d∏ i=1 xi · | exp(ŷ − y)− 1|,
where we used the fact that |φ̂ (x)− exp(ŷ)| = |ĝ (ŷ)− g(ŷ)| ≤ ‖ĝ − g‖∞ ≤ .
First suppose that x ≥ . In this case, for all i ∈ {1, . . . , d} we have |ĥ (xi)− log(xi)| = |ĥ (xi)− h (xi)| ≤ d . Then, |ŷ−y| ≤ . Consequently, |φ̂ (x)−p(x)| ≤ +max(|e
−1|, |e− −1|) ≤ 3 , for > 0 sufficiently small. Without loss of generality now suppose x1 ≤ . Then ŷ ≤ h (x1) ≤ log , so by definition of ĝ , we have 0 ≤ φ̂ (x) = ĝ (ŷ) ≤ exp(log ) = . Also, 0 ≤ p(x) ≤ so finally |φ̂ (x)− p(x)| ≤ . Remark B.5. Note that using Lemma B.2 instead of Lemma B.3 to construct approximating shallow networks for log and exp would yield approximation functions ĥ withO( ⌈ d log 1 ⌉ ) neurons and ĝ
with O( ⌈ 1 ⌉ ) neurons. Therefore, the corresponding neural network would approximate the product p with O(d2 −1 log 1 ) neurons.

heading: B.2 MISSING PROOFS OF SECTION B.1

heading: B.2.1 PROOF OF LEMMA B.3

text:
Proof. Similarly as the proof of Lemma B.2, the goal is to approximate f by a piece-wise affine function f̂ defined on a subdivision x0 = a ≤ x1 ≤ . . . ≤ xm ≤ xm+1 = b such that f and f̂ coincide on x0, . . . , xm+1. We first analyse the error induced by a linear approximation of the function on each piece. Let x ∈ [u, v] for u, v ∈ I . Using the mean value theorem, there exists αx ∈ [u, x] such that f(x) − f(u) = f ′(αx)(x − u) and βx ∈ [x, v] such that f(v) − f(x) =
f ′(βx)(v − x). Combining these two equalities, we get,
f(x)− f(u)− (x− u)f(v)− f(u) v − u = (v − x)(f(x)− f(u))− (x− u)(f(v)− f(x)) v − u
= (x− u)(x− v)f ′(βx)− f ′(αx)
v − u = (x− u)(v − x) ∫ βx αx f ′′(t)dt
v − u
Hence,
f(x) = f(u) + (x− u)f(v)− f(u) v − u
+ (x− u)(v − x) ∫ βx αx f ′′(t)dt
v − u . (1)
We now apply this result to bound the approximation error on each pieces of the subdivision. Let k ∈ [m]. Recall f̂ is linear on the subdivision [xk, xk+1] and f̂(xk) = f(xk) and f̂(xk+1) = f(xk+1). Hence, for all x ∈ [xk, xk+1], f̂(x) = f(xk) + (x− xk) f(xk+1)−f(xk)xk+1−xk . Using Equation equation 1 with u = xk and v = xk+1, we get,
‖f − f̂‖∞,[xk,xk+1] ≤ sup x∈[xk,xk+1]
∣∣∣∣∣(x− xk)(xk+1 − x) ∫ βx αx f ′′(t)dt
xk+1 − xk ∣∣∣∣∣ ≤ 1
2 (xk+1 − xk) ∫ xk+1 xk |f ′′(t)|dt
≤ 1 2 (xk+1 − xk)2‖f ′′‖∞,[xk,xk+1].
Therefore, using a regular subdivision with step √
2 ‖f ′′‖∞ yields an -approximation of f with⌈
(b−a) √ ‖f ′′‖∞√ 2 ⌉ pieces.
We now show that for any µ > 0, there exists an -approximation of f with at most ∫ √ |f ′′|√ 2 (1 + µ)
pieces. To do so, we use the fact that the upper Riemann sum for √ f ′′ converges to the integral since √ f ′′ is continuous on [a, b]. First define a partition a = X0 ≤ XK = b of [a, b] such that the upper Riemann sum R( √ f ′′) on this subdivision satisfies R( √ f ′′) ≤ (1 + µ/2) ∫ b a √ f ′′. Now
define on each interval Ik of the partition a regular subdivision with step √
2 ‖f ′′‖Ik as before. Finally,
consider the subdivision union of all these subdivisions, and construct the approximation f̂ on this final subdivision. By construction, ‖f − f̂‖∞ ≤ because the inequality holds on each piece of the subdivision. Further, the number of pieces is
K−1∑ i=0 1 + (Xi+1 −Xi) sup[Xi,Xi+1] √ f ′′ √ 2 = R( √ f ′′)√ 2 +K ≤ ∫ √ |f ′′|√ 2 (1 + µ),
for > 0 small enough. Using Lemma B.1 we can complete the proof.

heading: B.2.2 PROOF OF COROLLARY B.4

text:
Proof. In view of Lemma B.3, the goal is to show that we can remove the dependence of µ(f, ) in δ. This essentially comes from the fact that the upper Riemann sum behaves well for approximating log. Consider the subdivision x0 := δ ≤ x1 ≤ . . . ≤ xm ≤ xm+1 := 1 with m = ⌊ 1 ̃ log 1 δ ⌋ where
̃ := log(1 + √
2 ), such that xk = elog δ+k̃, for k = 0, . . . ,m − 1. Denote f̂ the corresponding piece-wise affine approximation. Similarly to the proof of Lemma B.3, for k = 0, . . . ,m− 1,
‖ log−f̂‖∞,[xk,xk+1] ≤ 1 2 (xk+1 − xk)2‖f ′′‖∞,[xk,xk+1] ≤
(ẽ − 1)2
2 ≤ .
The proof follows.
and O( −1
(
log 1
) 3(d−1)
2 +1) neurons on the second layer.

heading: B.3 PROOF OF THEOREM 3.1: APPROXIMATING THE KOROBOV SPACE X2,∞(Ω)

text:
In this subsection, we prove Theorem 3.1 and show that we can approximate any Korobov function f ∈ X2,∞(Ω) within with a 2-layer neural network ofO( − 12 (log 1 ) 3(d−1) 2 ) neurons. We illustrate the construction in Figure 5. Our proof combines the constructed network approximating the product function and a decomposition of f as a sum of separable functions, i.e. a decomposition of the form
f(x) ≈ K∑ k=1 d∏ j=1 φ (k) j (xj), ∀x ∈ [0, 1] d.
Consider the sparse grid construction of the approximating space V (1)n using the standard hat function as mother function to create the hierarchical basisWl (introduced in Section 2.2). We recall that the approximation space is defined as V (1)n := ⊕ |l|1≤n+d−1Wl. We will construct a neural network approximating the sparse grid approximation and then use the result of Theorem 2.2 to derive the approximation error. Figure 5 gives an illustration of the construction.
Let f (1)n be the projection of f on the subspace V (1) n . f (1) n can be written as f (1)n (x) = ∑
(l,i)∈U(1)n
vl,iφl,i(x),
where U (1)n contains the indices (l, i) of basis functions present in V (1) n i.e.
U (1)n := {(l, i), |l|1 ≤ n+ d− 1, 1 ≤ i ≤ 2l − 1, ij odd for all 1 ≤ j ≤ d}. (2) Throughout the proof, we explicitly construct a neural network that uses this decomposition to approximate f (1)n . We then use Theorem 2.2 and choose n carefully such that f (1) n approximates f within for L∞ norm. Note that the basis functions can be written as a product of univariate functions φl,i = ∏d j=1 φlj ,ij . We can therefore use the product approximation of Proposition 3.2 to approximate the basis functions. Specifically, we will use one layer to approximate the terms log φlj ,ij and a second layer to approximate the exponential.
We now present in detail the construction of the first layer. First, recall that φlj ,ij is a piece-wise affine function with subdivision 0 ≤ ij−1
2lj ≤ ij 2lj ≤ ij+1 2lj ≤ 1. Define the error term ̃ := 2|f |2,∞ .
We consider a symmetric subdivision of the interval [ ij−1+̃
2lj , ij+1−̃ 2lj
] . We define it as follows:
x0 = ij−1+̃ 2lj ≤ x1 ≤ · · · ≤ xm+1 = ij2lj ≤ xm+2 ≤ · · · ≤ x2m+2 = ij+1−̃ 2lj where m =⌊ 1 0 log 1̃ ⌋ and 0 := log(1 + √ 2̃/d), such that
xk = ij − 1 + elog ̃+k 0
2lj 0 ≤ k ≤ m,
xk = ij + 1− elog ̃+(2m+2−k)k 0
2lj m+ 2 ≤ k ≤ 2m+ 2.
Note that with this definition, the terms log(2ljxk − ij) form a regular sequence with step 0. We now construct the piece-wise affine function ĝlj ,ij on the subdivision x0 ≤ · · · ≤ x2m+2 which coincides with log φlj ,ij on x0, · · · , x2m+2 and is constant on [0, x0] and [x2m+2, 1]. By Lemma B.1, this function can be represented by a 1-layer neural network with as much neurons as the number of
pieces of ĝ, i.e. at most 2 √
3d ̃ log 1 ̃ neurons for sufficiently small. A similar proof to that of Corol-
lary B.4 shows that ĝ approximates max(log φlj ,ij , log(̃/3)) within ̃/(3d) for the infinity norm. We use this construction to compute in parallel, ̃/(3d)-approximations of max(log φlj ,ij (xj), log ̃) for all 1 ≤ j ≤ d, and 1 ≤ lj ≤ n, 1 ≤ ij ≤ 2lj where ij is odd. These are exactly the 1-dimensional functions that we will need, in order to compute the d-dimensional function basis of the approximation space V (1)n . There are d(2n − 1) such univariate functions, therefore our first layer contains at most 2n+1d √ 3d ̃ log 1 ̃ neurons.
We now turn to the second layer. The result of the first two layers will be ̃/3-approximations of φl,i for all (l, i) ∈ U (1)n . Recall that U (1)n contains the indices for the functions forming a basis of the approximation space V (1)n . To do so, for each indexes (l, i) ∈ U (1)n we construct a 1-layer neural network approximating the function exp, which will compute an approximation of exp(ĝl1,i1 +· · ·+ ĝld,id). The approximation of exp is constructed in the same way as for Lemma B.3. Consider a regular subdivision of the interval [log(̃/3), 0] with step √ 2(̃/3), i.e. x0 := log(̃/3) ≤ x1 ≤
· · · ≤ xm ≤ xm+1 = 0 where m = ⌊√ 3 2̃ log 3 ̃ ⌋ , such that xk = log ̃ + k √ 2̃, 0 ≤ k ≤ m.
Construct the piece-wise affine function ĥ on the subdivision x0 ≤ · · · ≤ xm+1 which coincides with exp on x0, · · · , xm+1 and is constant on (−∞, x0]. Lemma B.3 shows that ĥ approximates exp on R− within ̃ for the infinity norm. Again, Lemma B.1 gives a representation of ĥ as a 1-layer neural network with as many neurons as pieces in ĥ i.e. 1 + ⌈√ 3 2̃ log 3 ̃ ⌉ . The second layer is
the union of 1-layer neural networks approximating exp within ̃/3, for each indexes (l, i) ∈ U (1)n . Therefore, the second layer contains ∣∣∣U (1)n ∣∣∣ (1 + ⌈√ 32̃ log 3̃⌉) neurons. As shown in Bungartz & Griebel (2004),∣∣∣U (1)n ∣∣∣ = n−1∑
i=0
2i· ( d− 1 + i d− 1 ) = (−1)d+2n d−1∑ i=0 ( n+ d− 1 i ) (−2)d−1−i = 2n· ( nd−1 (d− 1)! +O(nd−2) ) .
Therefore, the second layer hasO ( 2n n d−1
(d−1)! ̃ − 12 log 1̃
) neurons. Finally, the output layer computes
the weighted sum of the basis functions to approximate f (1)n . Denote by f̂ (1) n the corresponding function of the constructed neural network (see Figure 5), i.e.
f̂ (1)n = ∑
(l,i)∈U(1)n
vl,i · ĥ  d∑ j=1 ĝ(xj)  . Let us analyze the approximation error of our neural network. The proof of Proposition 3.2 shows that the output of the two first layers h (∑d j=1 ĝ(·j) ) approximates φl,i within ̃. Therefore, we
obtain ‖f (1)n − f̂ (1)n ‖∞ ≤ ̃ ∑
(l,i)∈U(1)n |vl,i|. We now use approximation bounds from Theorem 2.2
on f (1)n .
‖f−f̂ (1)n ‖∞ ≤ ‖f−f (1)n ‖∞+‖f (1)n −f̂ (1)n ‖∞ ≤ 2 · |f |2,∞
8d ·2−2n ·A(d, n)+ 2|f |2,∞ ∑ (l,i)∈U(1)n |vl,i|,
where ∑ (l,i)∈U(1)n |vl,i| ≤ |f |2,∞2−d ∑ i≥0 2−i · ( d− 1 + i d− 1 ) ≤ |f |2,∞.
Let us now take n = min { n :
2|f |2,∞ 8d 2−2nA(d, n) ≤ 2 } . Then, using the above inequality shows
that the neural network f̂ (1)n approximates f within for the infinity norm. We will now estimate the number of neurons in each layer of this network. Note that
n ∼ 1
2 log 2 log
1 and 2n ≤ 4
8 d 2 (2 log 2) d−1 2 (d− 1)! 12
√ |f |2,∞ ( log 1 ) d−1 2 · (1 +O(1)).
(3) We can use the above estimates to show that the constructed neural network has at most N1 (resp. N2) neurons on the first (resp. second) layer where
N1 ∼ →0
8 √ 6d2
8 d 2 (2 log 2) d−1 2 d! 1 2
· |f |2,∞ ( log 1 ) d+1 2 ,
N2 ∼ →0
4 √ 3d 3 2
8d/2(2 log 2) 3(d−1) 2 d! 3 2
· |f |2,∞ ( log 1 ) 3(d−1) 2 +1 .
This proves the bound the number of neurons. Finally, to prove the bound on the number of training parameters of the network, notice that the only parameters of the network that depend on the function f are the parameters corresponding to the weighs vl,i of the sparse grid decomposition. This number is |U (1)n | = O(2n nd−1 ) = O( − 1 2 (log 1 ) 3(d−1) 2 ).

heading: B.4 PROOF OF THEOREM 3.4: GENERALIZATION TO GENERAL ACTIVATION FUNCTIONS

text:
We start by formalizing the intuition that a sigmoid-like (resp. ReLU-like) function is a function that resembles the Heaviside (resp. ReLU) function by zooming out along the x (resp. x and y) axis.
Lemma B.6. Let σ be a sigmoid-like activation with limit a (resp. b) in −∞ (resp.+∞). For any δ > 0 and error tolerance > 0, there exists a scaling M > 0 such that x 7→ σ(Mx)b−a − a approximates the Heaviside function within outside of (−δ, δ) for the infinity norm. Furthermore, this function has values in [0, 1].
Let σ be a ReLU-like activation with asymptote b · x+ c in +∞. For any δ > 0 and error tolerance > 0, there exists a scaling M > 0 such that x 7→ σ(Mx)Mb approximates the ReLU function within for the infinity norm.
Proof. Let δ, > 0 and σ a sigmoid-like activation with limit a (resp. b) in −∞ (resp. +∞). There exists x0 > 0 sufficiently large such that (b−a)|σ(x)−a| ≤ for x ≤ −x0 and (b−a)|σ(x)−b| ≤ for x ≥ x0. It now suffices to take M := x0/δ to obtain the desired result. Now let σ be a ReLU-like activation with oblique asymptote bx in +∞ where b > 0. Let M such that |σ| ≤ Mb for x ≤ 0 and |σ(x) − bx| ≤ Mb for x ≥ 0. One can check that |σ(Mx)Mb | ≤ for x ≤ 0, and |σ(Mx)Mb − x| ≤ for x ≥ 0.
Using this approximation, we reduce the analysis of sigmoid-like (resp. ReLU-like) activations to the case of a Heaviside (resp ReLU) activation to prove the desired theorem.
Proof of Theorem 3.4 We start by the class of ReLU-like activations. Let σ be a ReLU-like activation function. Lemma B.6 shows that one can approximate arbitrarily well the ReLU activation with a linear map σ. Take the neural network approximator f̂ of a target function f given by Theorem 3.1. At each node, we can add the linear map corresponding to x 7→ σ(Mx)Mb with no additional neuron nor parameter. Because the approximation is continuous, we can take M > 0 arbitrarily large in order to approximate f̂ with arbitrary precision on the compact [0, 1]d.
The same argument holds for sigmoid-like activation functions in order to reduce the problem to Heaviside activation functions. Although quadratic approximations for univariate functions similar to Lemma B.3 are not valid for general sigmoid-like activations – in particular the Heaviside — we can obtain an analog to Lemma B.2 as Lemma B.7 given in the Appendix B.4.1. This results is an increased number of neurons. In order to approximate a target function f ∈ X2,∞(Ω), we use the same structure as the neural network constructed for ReLU activations and use the same notations as in the proof of Theorem 3.1. The first difference lies in the approximation of log φlj ,ij in the first layer. Instead of using Corollary B.4, we use Lemma B.7. Therefore, 12d̃ log 3 ̃ neurons are needed to compute a ̃/(3d)-approximation of max(log φlj ,ij , log(̃/3)). The second difference is in the approximation of the exponential in the second layer. Again, we use Lemma B.7 to construct a ̃/3-approximation of the exponential on R− with 6̃ neurons for the second layer. As a result, the first layer contains at most 2n+2 3d 2
̃ log 1 ̃ neurons for sufficiently small, and the second layer contains ∣∣∣U (1)n ∣∣∣ 6̃ neurons. Using the same estimates as in the proof of Theorem 3.1 shows that the constructed neural network has at mostN1 (resp. N2) neurons on the first (resp. second) layer where
N1 ∼ →0
3 · 25 · d5/2
8 d 2 (2 log 2) d−1 2 d! 1 2
|f | 3 2 2,∞
3 2
( log 1 ) d+1 2 ,
N2 ∼ →0
24 · d 32
8 d 2 (2 log 2) 3(d−1) 2 d! 3 2
· |f |
3 2 2,∞ 3 2
( log 1 ) 3(d−1) 2 .
This ends the proof.

heading: B.4.1 PROOF OF LEMMA B.7

text:
Lemma B.7. Let σ be a sigmoid-like activation. Let f : I −→ [c, d] be a right-continuous increasing function where I is an interval, and let > 0. There exists a shallow neural network with activation σ, with at most 2d−c neurons on a single layer, that approximates f within for the infinity norm.
Proof. The proof is analog to that of Lemma B.2. Let m = bd−c c. We define a regular subdivision of the image interval c ≤ y1 ≤ . . . ≤ ym ≤ d where yk = c + k for k = 1, . . . ,m, then using the monotony of f , we can define a subdivision of I , x1 ≤ . . . ≤ xm such that xk := sup{x ∈ I, f(x) ≤ yk}. Let us first construct an approximation neural network f̂ with the Heaviside activation. Consider
f̂(x) := y1 + m−1∑ i=1 1 ( x− xi + xi+1 2 ≥ 0 ) .
Let x ∈ [c, d] and k such that x ∈ [xk, xk+1]. We have by monotony yk ≤ f(x) ≤ yk+1 and yk = y1 + (k − 1) ≤ f̂(x) ≤ y1 + k = yk+1. Hence, f̂ approximates f within in infinity norm. Let δ < mini=1,...,m(xi+1−xi)/4 and σ a general sigmoid-like activation with limits a in−∞ and b in +∞. Take M given by Lemma B.7 such that σ(Mx)b−a − a approximates the Heaviside function within 1/m outside of (−δ, δ) and has values in [0, 1]. Using the same arguments as above, the function
f̂(x) := y1 + m−1∑ i=1
σ ( Mx−M xi+xi+12 ) b− a − a
approximates f within 2 for the infinity norm. The proof follows.

heading: C PROOFS OF SECTION 4

heading: C.1 PROOF OF THEOREM 4.1: APPROXIMATING KOROBOV FUNCTIONS WITH DEEP NEURAL NETWORKS

text:
Let > 0. We construct a similar structure to the network defined in Theorem 3.1 by using the sparse grid approximation of Subsection 2.2. For a given n, let f (1)n be the projection of f in the approximation space V (1)n (defined in Subsection 2.2) and U (1) n (defined in equation 2) the set of indices (l, i) of basis functions present in V (1)n . Recall f (1) n can be uniquely decomposed as
f (1)n (x) = ∑
(l,i)∈U(1)n
vl,iφl,i(x).
where φl,i = ∏d j=1 φlj ,ij are the basis functions defined in Subsection 2.2. In the first layer, we compute exactly the piece-wise linear hat functions φlj ,ij , then in the next set of layers, we use the product-approximating neural network given by Proposition 4.2 to compute the basis functions φl,i = ∏d j=1 φlj ,ij (see Figure 3). The output layer computes the weighted sum∑
(l,i)∈U(1)n vl,iφl,i(x) and outputs f
(1) n . Because the approximation has arbitrary precision, we can
chose the network of Proposition 4.2 such that the resulting network f̂ verifies ‖f̂ − f (1)n ‖∞ ≤ /2. More precisely, as φlj ,ij is piece-wise linear with four pieces, we can compute it exactly with four neurons with ReLU activation on a single layer (Lemma B.1). Our first layer is composed of the union of all these ReLU neurons, for the d(2n − 1) indices lj , ij such that 1 ≤ j ≤ d, 1 ≤ lj ≤ n, 1 ≤ ij ≤ 2lj and ij is odd. Therefore, it contains at most d2n+2 neurons with ReLU activation. The second set of layers is composed of the union of product-approximating neural networks to compute φl,i for all (l, i) ∈ U (1)n . This set of layers contains dlog2 de layers with activation σ and at most |U (1)n | · 8d neurons. The output of these two sets of layers is an approximation of the basis functions φl,i with arbitrary precision. Consequently, the final output of the complete neural network is an approximation of f (1)n with arbitrary precision. Similarly to the proof of Theorem 3.1, we can chose the smallest n such that ‖f − f (1)n ‖∞ ≤ /2 (see equation 3 for details). Finally, the network has depth at most log2 d+ 2 and N neurons where
N = 8d|U (1)n | ∼ →0 25 · d5/2
8 d 2 (2 log 2) 3(d−1) 2 d! 3 2
· √ |f |2,∞ ( log 1 ) 3(d−1) 2 .
The parameters of the network depending on the function are exactly the coefficients vl,i of the sparse grid approximation. Hence, the network has O( − 12 (log 1 ) 3(d−1) 2 ) training parameters.

heading: D PROOFS OF SECTION 5

heading: D.1 PROOF OF THEOREM 5.2: NEAR-OPTIMALITY OF NEURAL NETWORKS FOR KOROBOV FUNCTIONS

text:
Our goal is to define an appropriate subspace XN+1 in order to get a good lower bound on the Bernstein width bN (K)X , defined in equation 5, which in turn provides a lower bound on the approximation error (Theorem 5.1).
To do so, we introduce the Deslaurier-Dubuc interpolet φ(L) : R → R. The construction of this function uses an interpolating scheme on binary rationals. First, φ(L) is defined on all integers φ(L)(k) = 1k=0 for k ∈ Z. Then, we define the function on half integers 2k+12 by fitting a polynomial of degree 2L− 1 interpolating the standard hat function φ at k−L+ 1, · · · , k+L. Iteratively, we define the interpolet on binary rationals of the form 2k+12j+1 from the value of the interpolet on rationals with denominator 2j . Specifically, let P (L)j,k be the unique polynomial of degree 2L interpolating φ(L) at points k ′
2j for k ′ ∈ {k − L+ 1, · · · , k + L}. We set φ(L) ( 2k + 1
2j+1
) := P
(L) j,k
( 2k + 1
2j
) .
For example, for L = 2 we get φ(2)( 2k+12j+1 ) := 9 16φ (2)( k2j ) + 9 16φ (2)(k+12j ) − 1 16φ (2)(k−22j ) − 1 16φ
(2)(k+32j ). This process defines the interpolet on binary rationals. We then extend the function to the real line by continuity. See Figure 6 for an illustration. Deslauriers & Dubuc (1989) proved that the regularity of the interpolet is an increasing function of L the degree of interpolation. We now prove results in the case L = 2.
Lemma D.1. The interpolet of degree 2, φ(2) is C2 and has support Supp ( φ(2) ) = [−3, 3].
Proof. See Appendix D.2.1.
We will now use the interpolet φ(2) to construct the subspace XN+1. Using the sparse grids approach, we can construct a hierarchical basis in X2,∞(Ω) using the interpolet φ(2) as mother function. In the remaining of the proof, we will write φ instead of φ(2) for simplicity, and use the notations and definitions related to sparse grids, introduced in Subsection 2.2. Because EN (K) is decreasing in N , it suffices to show the result for Nn when we define our space XN+1 to be exactly the approximating space V (1)n of sparse grids XNn+1 := V (1) n . The following equation establishes the relation between n and Nn. In the following, for simplicity, we will write N instead of Nn. N = dim(V (1)n )−1 = ∑
|l|1≤n+d−1
2|l|1−1−1 = n−1∑ i=0 2i−d ( d− 1 + i d− 1 ) −1 = 2n· ( nd−1 (d− 1)! +O(nd−2) ) .
First, let us give some properties about the subspace XN+1. Proposition D.2. Let u ∈ XN+1 and write it in decomposed form u = ∑ l,i vl,i · φl,i, where the sum is taken over all multi-indices corresponding to basis functions of XN+1. The coefficients vl,i can be computed in the following way.
vl,i =  d∏ j=1 Ilj ,ij u =: Il,iu where Ilj ,iju = u( ij 2j )− 9 16u( ij−1 2j )− 9 16u( ij+1 2j ) + 1 16u( ij−3 2j ) + 1 16u( ij+3 2j ). Here, Il,i denotes the d-dimensional stencil which gives a linear combination of values of u at 5d nodal points.
Proof. See Appendix D.2.2.
Note that the stencil representation of the coefficients gives directly |vl,i| ≤ 5d‖u‖∞. We are now ready to make our estimates. The goal is to compute sup{ρ : ρU(XN+1) ⊂ K}, which will lead to a bound on bN (K)X . To do so, it suffices to upper bound the Korobov norm by the L∞ norm for elements of XN+1. In fact, if Γd > 0 satisfies for all u ∈ U(XN+1), |u|X2,∞ ≤ Γd‖u‖∞, then bN (K)X ≥ 1/Γd.
Now take u ∈ XN+1 and let us write u = ∑ l,i vl,i · φl,i. Note that basis functions in the same hierarchical class Wl are almost disjoint. More precisely, at each point x ∈ Ω, at most 3d basis functions φl,i have non-zero contribution to u(x). Therefore, for any 0 ≤ α ≤ 2 · 1,
‖Dαu‖∞ ≤ ∑
|l|1≤n+d−1
3d max 1≤i≤2l−1, i odd |vl,i| · 2〈α,l〉‖Dαφ‖∞
= 60d|φ|X2,∞(Ω)‖u‖∞ · n−1∑ i=0 22i ( d− 1 + i d− 1 ) = 60d
(d− 1)! |φ|X2,∞(Ω) · 22n
( nd−1 +O(nd−2) ) ‖u‖∞.
Finally, denoting by Cd the constant 60 d (d−1)! |φ|X2,∞(Ω), we get for n sufficiently large
bN (K)X ≥ 1 2Cd · 1 22n · nd−1 .
Furthermore, recall N = 1(d−1)!2 n · nd−1 ·
( 1 +O ( 1 n )) . Therefore, n ∼ logNlog 2 , and 2
n ∼ (d − 1)!(log 2)d−1 · N
(logN)d−1 . Finally we obtain for some constant cd > 0,
bN (K)X ≥ cd 1
N2 (logN)d−1.
We conclude by analyzing the minimum number of parameters in order to get an -approximation of the Korobov unit ball K. Define n := min{n : 2Cd 1 22n·nd−1 ≤ }. This yields n ∼ 1 2 log 2 log 1 ,
and 2n ∼ √
2 Cd (2 log 2)d−1 1√ ·(log 1 ) d−1 2 . The number of needed parameters to obtain an approx-
imation K is therefore
N ∼ C̃d · 1√ ( log 1 ) d−1 2 ,
for some constant C̃d > 0.
Interestingly, the subspace XN+1 our proof uses to show the lower bound is essentially the same as the subspace we use to approximate Koborov functions in our proof of the upper bounds (Theorem 3.1, 4.1). The difference is in the choice of the interpolate φ to construct the basis functions, degree 1 for the former, and 2 for the later.

heading: D.2 MISSING PROOFS OF SUBSECTION D.1

heading: D.2.1 PROOF OF LEMMA D.1

text:
Lemma D.3. The interpolet of degree 2, φ(2) is C2 and has support Supp ( φ(2) ) = [−3, 3].
Proof. To analyze the regularity of the interpolet, we introduce the trigonometric polynomial P (2)(θ) := ∑ k∈Z φ(2) ( k 2 ) eikθ = 1 + 9 16 (eiθ + e−iθ)− 1 16 (e3iθ + e−3iθ).
We can write P (2)(θ) as
P (2)(θ) =
[ sin θ
sin ( θ 2 )]4 · S(θ), where S(θ) = 14 − 1 16 (e iθ + e−iθ) is a trigonometric polynomial of degree 1. Deslaurier and Dubuc
(Deslauriers & Dubuc, 1989, Theorem 7.11) showed that the interpolet φ(2) has regularity ⌊ − log rlog 2 ⌋ where r is the spectral radius of the matrix B := [sj−2k]−1≤j,k≤1 where sj are the coefficients of the trigonometric polynomial S(θ). In our case, matrix B writes
B = (−1/16 −1/16 0 0 1/4 0 0 −1/16 −1/16 ) ,
and has spectral radius r = 1/4. Therefore, the regularity of φ(2) is at least ⌊ − log rlog 2 ⌋ = 2. For the
support, one can check that more generally Supp(φ(L)) = [−2L+ 1, 2L− 1].

heading: D.2.2 PROOF OF PROPOSITION D.2

text:
Proposition D.4. Let u ∈ XN+1 and write it in decomposed form u = ∑ l,i vl,i · φl,i, where the sum is taken over all multi-indices corresponding to basis functions of XN+1. The coefficients vl,i can be computed in the following way.
vl,i =  d∏ j=1 Ilj ,ij u =: Il,iu where Ilj ,iju = u( ij 2j )− 9 16u( ij−1 2j )− 9 16u( ij+1 2j ) + 1 16u( ij−3 2j ) + 1 16u( ij+3 2j ). Here, Il,i denotes the d-dimensional stencil which gives a linear combination of values of u at 5d nodal points.
Proof. We start by looking at the 1-dimensional case. One can check that Il,iφl̃,̃i = 1l̃=l,̃i=i. Indeed, if l̃ > l of if l̃ = l and ĩ 6= i, then φl̃,̃i will be zero at the nodal values of Il,i. Further, if l̃ < l the iterative construction of φ gives directly.
φl̃,̃i
( i
2j
) = 9
16 φl̃,̃i
( i+ 1
2j
) + 9
16 φl̃,̃i
( i− 1
2j
) − 1
16 φl̃,̃i
( i+ 3
2j
) − 1
16 φl̃,̃i
( i− 3
2j
) .
Therefore, we obtain Il,iφl̃,̃i = 0. Finally, Il,iu = ∑ l̃,̃i vl̃.̃i · Il,iφl̃,̃i = vl,i · Il,iφl,i = vl,i. This proves the stencil representation of vl,i for dimension 1. Finally, using the tensor product approach of the stencil operator Il,i we can generalize the formula to general dimensions.