Shallow and Deep Networks are Near-Optimal Approximators of Korobov Functions
Authors: Moise Blanchard
Mohammed Amine Bennouna
Venue: ICLR 2022 Poster (2022)

Abstract: 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.

Published as a conference paper at ICLR 2022
SHALLOW AND DEEP NETWORKS ARE NEAR- OPTIMAL APPROXIMATORS OF KOROBOV FUNCTIONS
Moise Blanchard
Amine Bennouna
Operations Research Center Massachusetts Institute of Technology Cambridge, MA, 02139 moi sebêmit edu
Operations Research Center
Massachusetts Institute of Technology Cambridge, MA, 02139 ami umineben@mit.ccm
ABSTRACT
In this paper, we analyze the number of neurons and training parameters that a neu- ral network needs 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 dimensional- ity. Our bounds hold for general activation functions, including ReLU. We further prove that these bounds nearly match the minimal number of parameters any con- tinuous function approximator needs to approximate Korobov functions, showing that neural networks are near-optimal function approximators.
INTRODUCTION
Neural networks have known tremendous success in many applications such as computer vision and pattern detection (Krizhevsky al.) 2017 Silver al.] (016). natural question is how to ex- plain their practical success theoretically. Neural networks are shown to be universal (Hornik al. 1989]: any Borellmeasurable function can be approximated arbitrarily well by neural network with sufficient number of neurons. Furthermore, universality holds for low as 1-hidden-layer neural network with reasonable activation functions. However, these results do not specify the needed number of neurons and parameters to train. If these numbers unreasonably high, the universality of neural networks would not explain their practical success.
We interested in evaluating the number of neurons and training parameters needed to approx- imate a given function within with a neural network. An interesting question is how do these numbers scale with e and the dimensionality of the problem, i.e., the number of variables, MMhskar (1996) showed that any function of the Sobolev space of order r and dimension d can be approxi- mated within with a 1-layer neural network with ( neurons and an infinitely differentiable activation function. This bound exhibits the curse of dimensionality: the number of neurons needed for e approoiimtiion 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.
Towards answering this question, Vore et al. (999) proved that any continuous function approx- imator (see Section 5) that approximates all Sobolev functions of order r and dimension within parameters. This result meets Mhaskar's bound and confirms that neural networks cannot escape the curse of dimensionality for the Sobolev space. A main question is then for which set of functions can neural networks break this curse of dimensionality.
needs at least ( - )
One way to cireumvent the curse of dimensionality is to restrict considerably the considered space of functions and focus on specific structures adapted to neural networks. For example, MMaskar et al. (016) showed that compositional functions with regularity can approximated within e with deep neural networks with O(d - neurons. Other structural constraints have been considered for compositions of functions (Kohler & Krzyžak 2016), piecewise smooth functions (Petersen & Voigtlaender 2018 Imaizumi & Fukumizu (019). or structures on the data space, e.g.. lying on manifold (Mhaskar [2000] Nakada & Imaizumi 2019; Schmidtt-iebee 2019). Approximation
bounds have also been obtained for the function approximation from data under smoothness con- straints (Kohler & Krzyžak 2005 Kohler & Mehnert 2011) 1) and specifically mixed smooth Besov

---

Another example Published as a conference paper at ICLR 2022
spaces which are known to circumvent the curse of dimensionality (Suzuki 2018
is the class of Sobolev functions of order d/a and dimension d for which Mhaskar's 's bound becomes O(e Recently, MMotannlll et al. (2019) considered bandlimited functions and showed that they can be approximated within e by deep networks with depth ( )) and O(e-2 ))²) neu- rons. WWenan et al.] (2019) showed that the closure of the space of 2-layer neural networks with specific 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 e with 2-layer networks with O(c_3 neurons. Similar line of work restrict the function space with spectral conditions, to write functions 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 inter- est is the space of multivariate functions of bounded second mixed derivatives, the Korobov space. This space is included in the Sobolev space but is reasonably large and general. The Korobov space presents two motivations. First, 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.T.. Second, Korobov spaces are practically useful for solving partial differential equations (Korobov 1959) and have been used for nigh-dimensional function approxi- mation (Zenger& & Hackbusch] [991] Zenger 1991). Recently, [Montnnlli & Du (2019) showed that
deep neural networks with depth Olog !) and O(c 1 (log :) 31 +1) neurons can approximate Korobov functions within lessening the curse of dimensionality for deep neural networks asymp- totically in e. While they used deep structures 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:
1. Representation power of shallow neural networks. We prove that any Korobov function can be approximated within e with a 2-layer neural network with ReLU activation function with +1)
(legg 4) +1) neurons and O 1 (log ) s(d-1) training parameters (Theorem 3.I. We further extend this result to a large class of commonly used activation functions (Theorem 3.4
Asymptotically in c, our bound can be written as (c-1--) for all > 0, and in that sense breaks the curse of dimensionality for shallow neural networks.
Representation power deep neural networks. We show that any function of the Korobov space can be approximated within with a deep neural network of depth [logg (d) + independent neurons and ( 1 (log 2) 3rd
of e, with non- non-linear C2 activation function, O(e (log 2) s(d
training parameters (Theorem 4.1 This result improves that of Montanelli & Du (219)) who con- structed an approximating neural network with larger depth O(log _ log d) -increasing with e- and
larger number of neurons O(E à (log 2) "id,") However, they used ReLU activation function.
3. Near-optimality of neural networks function approximators. Under the continuous func- tion approximators model introduced by Vore et al. (1899, we prove that any continuous func- tion approximator needs ( (log ! ) parameters to approximate Korobov functions within (Theorem (.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 they are near-optimal function approximators of the Korobov space.
Table 1 summarizes our new bounds and existing bounds on shallow and deep neural network ap- proximation power for the Korobov space, Sobolev space and bandlimited functions. Our proofs constructive and give explicit structures to construct such neural networks with ReLU and gen- eral activation functions. Our constructions rely on sparse grid approximation introduced by Zenger [199], and studied in detail in Bungartz (1992); (Bnggarz & 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 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 de- rive 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 Vore et al. (1989)
2

---

Published as a conference paper at ICLR 2022
The rest of the paper is structured follows. In Section 2 we formalize objective and introduce the sparse grids approach. In Section 3 (resp. 4. we prove our bounds on the number of neurons and training parameters for Korobov functions approximation with shallow (resp. deep) networks. Finally, we formalize in Section | the notion of optimal continuous function approximators and prove our novel near-optimality result.
Nb. training parameters
Space
Nh. of neurons
Depth
Activation o
Reference
1
e non-poly
Mhaskar 1996
c- (log 2) د
c $ (log !) "9
2
ReLU-like
This paper
3 (log) 1) 2
e i (log !) = a
2
Sigmoid-like
This paper
Wre
c log 1
c A log
(log !)
ReLU
Narotsky (2017]
Liang Snikant 2016
Bandlimited functions
(logg 2)²
20og 2)²
O(Oog A)*)
ReLU
Montanelli al. 2019
X2,0c
2logg 2) "1
3 (log 2)=m"""
(log log )
ReLU
Montanelli
2019
X
-- (logg (log
c- +log = [og, d] ++
C² non-linear
This paper
Table Approximation results for Sobolev WhP and Korobov X2,00 functions by shallow and deep networks. Number of neurons and training parameters are given in O notation.
2 PRELIMINARIES
In this work, we consider feed-forward neural networks, using a linear output neuron and a non- linear activation function σ IR R for the other neurons, such as the popular rectified unit (ReLU) (x) = max(2, 0), the sigmoid (x) = (1 + e e->)-1 or the Heaviside function (zz) (x20)- Let d 2 1 be the dimension of the input. We define a 1-hidden-layer network with N neurons as x + Ex= ( x + by), where wk E IRd by E R for i = 1..... .N, are parameters. A neural network with several hidden layers is obtained by feeding the outputs of given layer as inputs the next layer. We study the expressive power of neural networks, i.e., the ability to approximate a target function f Rd + R with few neurons possible, on the unit hyper-cube Ω [0, 1jd Another relevant metric is the number of parameters that need to be trained to approximate the function, i.e., the number of parameters of the approximating network (1z, wy and by) depending on the function to approximate. We will adopt _ norm as a measure of approximation error.
We now define some notations necessary to introduce our function spaces of interest, For an integer we denote C the space of one dimensional functions differentiable r times and with continu- ous derivatives. In our analysis, we consider functions f with bounded mixed derivatives. For
gial1 / multi-index E Nd, the derivative of order is D == 25; Bn z where |ax|1 Ei= lay]-
Two common function spaces in compact Q Ed are the Sobolev spaces WT)P((2) of functions having weak partial derivatives up to order r in LP()) and the Korobov spaces (92) of functions vanishing at the boundary and having weak mixed second derivatives up order r in (9)).
Wf) (ʃ E IP())) D E T,(()), S sr), X {f E IP()) flaa 0, f E L' (P)).. |a/ r).
where O2 denotes the boundary of Ω. |al1 = Σ lail and |a|x = sup la: are respec- tively the I and infinity norm. Note that Korobov spaces X are subsets of Sobolev spaces (P). For p = 0o, the usual norms on these spaces are given by
If ( = max | fllo, (flx jal:Sr
max |a
flbo:
For simplicity, will write |. 12,0c for Ixa... We focus our analysis on approximating func- tions on the Korobov space x2,00(S) (S) for which the curse of dimensionality is drastically lessened and we show that neural networks are optrmal Intuitively, a key difference compared to the Sobolev space is that Korobov functions do not have high frequency oscillations in all directions at a time. Such functions may require an exponential number of neurons Telgarsky (2016) and are one of the main difficulties for Sobolev space approximation, which therefore exhibits the curse of
3

---

Published as a conference paper at ICLR 2022
dimensionality Vore al. 1989). On the contrary, the Korobov space prohibits such behaviour by ensuring that functions can be differentiable on all dimensions together. Further discussions and concrete examples are given in Appendix A
2.1 THE CURSE OF DIMENSIONALITY
We adopt the point of view of asymptotic results (or equivalently, the number of neurons), which is a well-established setting in the neural networks representation power literature (Mhaskar) 1996 Bungartz & Griebel 2004 Yarotsky [0177] Montanelli & Du (019) and numerical analysis literature [Novak] 2006). In the rest of the paper, use O notation which hide constants in d. For each result, full dependencies in d are provided in appendix. Previous efforts to quantify the number of neurons needed to approximate large general class of functions, showed that neural networks and most classical functional approximation schemes exhibit the curse of dimensionality. For example, for Sobolev functions, Mhaskar proved the following approximation bound.
Theorem 2.1 (Mhaskar (1996)). Let p.r 2 1, and a R - R an infinitely differentiable activation function, non-polynomial on any interval of R. Let > 0 sufficiently small. For any E WT., there exists a shallow neural network with one hidden layer, activation function a, and OE 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 di- mension d. This curse is not due to poor performance of neural networks but rather to the choice of the Sobolev space. Vere et al. (1989) proved that any learning algorithm with continuous pa- rameters needs at least ( +) parameters to approximate the Sobolev space WMP, 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 whether there exists a reasonable and sufficiently large class of functions for which there is no inherent curse of dimensionality. Instead of the Sobolev space, we aim to add more regularity to overcome the curse of dimensionality while preserving a reasonably large space. The Korobov space X (1))-fuuctions with bounded mixed derivatives is natural candidate: it is known in the numerical analysis community as a reasonably large space where numerical ap- proximation methods can lessen the curse of dimensionality (Bungartz & Griebell 2004). Korobov
functions have been introduced for solving partial differential equations (Korobov) 1959 Smolyak,
1963), and have then been used extensively for high-dimensional function approximation (Zenger & Hackbusch| 1991: Bungartz & Griebel 2004). This space of functions is included in the Sobolev space, but still reasonably large the regularity condition concerns only second order derivatives. Two questions are of interest. First, how many neurons and training parameters a neural network needs to approximate any Korobov function within the - norm? Second, how do neural networks perform compared to the optimal theoretical rates for Korobov spaces?
2.2 SPARSE GRIDS AND HIERARCHICAL BASIS
In this subsection, we introduce sparse grids which will be key in our neural networks construc- tions. These were introduced by Zenger (199]) and extensively used for high-dimensional function approximation. We refer to Bungarrz & Griebel (2004) for thorough review of the topie.
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 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, simple choice for the building block Φ is the standard hat function (bx)= := (1 |z|)). 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 Deslauriers & Dubuc (1989) (which define rigorously later in proofs) the hat function ø which can be interpolet of order 1. These more elaborate mother functions enjoy more smoothness while essentially preserving the approximation power.
seen as the Deslaurier-Di
4

---

Published as a conference paper at ICLR 2022
Ø3,1
2
03.3
61,1
65.5
d2,3
63.7
W1
W₂
W3
Figure I: Hierarchical basis from the sparse grid construction using the hat function (1 - -1- D+
,d, it can be used to generate set Assume the mother function has support in 1-k; kj. For j 1,...,,,
of local functions &i [0, 1] - R for all 1 2 and S in S 2/ with support
25 2
as follows, (Iy. (x) = 6(2 iz), x E [0, 1]. We then define a basis of ddddimensional functions by taking the tensor product of these 1-dimensional functions. For all L, Nd with I 2 1 and 1 i 2 - 1 where 2 denotes (2 ..... 2'd), define 01,((z) == IT Pl (zz)) æ E Rd. For fixed E N4, we will consider the hierarchical increment space W1 which the subspace spanned by the functions {Ør, 1 1 < 2 1}. as illustrated in Figure
Wi span (dr, 1 s 2 1, ig odd for all dd.
Note that in the hierarchical increment W,, all basis functions have disjoint support. Also, Korobov functions (2)) can be expressed uniquely in this hierarchical basis. Precisely, there is a unique representation of u E x (12) as u(x) = Σt, (x)) where the sum is taken over all multi- indices 1 and 1 I functions are linearly independent. Notice that this sum is infinite, the objective is now to define finiteddimensional subspace of X2-P((D) that will serve as approximation space. Sparse grids use a carefully chosen subset of the hierarchical basis functions to construct the approximation space (1)
2 where all components of i are odd. In particular, all basis
Du, Sn+-d11 W₁. When e is the hat function, Bungartz and Griebel Bungartz Griebell 2004 showed that this choice of approximating space leads good approximating error.
Theorem 2.2 Bungartz& & Griebel (0044). Let f E X2,00 (St) and <(1) be the projection of f on the subspace V!! We have, flff - 1100 =0 (2-2n (0-2"nd=1) Furthermore, vL, denotes the coefficient
of oL. in the decomposition ((1) in Vi then we have the upper bound |ut,e] S 2-142 2//1 42-2 220
for all i E Nd with 14
L, 2 - where has odd components.
3 THE REPRESENTATION POWER OF SHALLOW NEURAL NETWORKS
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 2011). However, to the best of our knowledge, the question of whether shallow neural networks with fixed universal depth - independent of c 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 e > For all f E (2)) there exists a neural network with layers, ReLU activation, ( ) -==="=="" 3id=1)+ neurons, and O 2log 3id-1), training parameters that approximates f within e for the infinity norm.
In order to prove Theorem 3.1
we construct the approximating neural network explicitly. The first step construct a neural network architecture with two layers and Old log () neurons that approximates the product function p x E [0, 1]d - IIm xa within c for all c 0. Proposition 3.2. For all
there exists neural network with depth 2, ReLU activation and Odd log ?) neurons, that approximates the product function p x E [0. 1]a I Ta within e for the infinity norm.
Sketch of proof The proof builds upon the observation that p(æ) exp x.). We construct an approximating 2-layer neural network where the first layer approximates log x, for
1 < i & d, and the second layer approximates the exponential. We illustrate the construction in
5

---

Published as a conference paper at ICLR 2022
31
22
(dte 6 log
log 11
log 22
log
O(e 2 log
exp
I
Figure 2: Shallow neural network with ReLU activation implementing the product function II Ta within c infinity norm. The network has O c- log !) neurons on the first layer and O log !) neurons the second layer.
Figure More precisely, fix c > 0. Consider the function he x E [0, - max(log log c)- We approximate h, within with a piece-wise affine function with Oddee log () pieces, then represent this piece-wise affine function with single layer neural network he with the same number of neurons as the number of pieces (Lemma B.I Appendix B.I). This 1-layer network then has ||, he lc I 5. The first layer of our final network is the union of copies of h.: one for each dimension i, approximating log z;. Similarly, consider the exponential 9 I E R_ + e". We construct a 1-layer neural network 9. with O(e log !) neurons with ||g - 80 S 6. This will serve as second layer. Formally, the constructed network P. is p. = ge EE= (x:))) This 2-layer neural network has Odde log !) neurons and verifies I| pll0o S..
We use this result to prove Theorem 3.1 and show that we can approximate any Korobov function x2.00 (1. within with 2-layer neural network of O(e à (log !) =)),")))) neurons. Consider the sparse grid construction of the approximating space (!(1) using the standard hat function as mother function to create the hierarchical basis Wr (introduced in Section (.2).. The key idea is to construct shallow neural network approximating the sparse grid approximation and then the result of Theorem 2.2 to derive the approximation error. Let fn be the projection f on the
subspace v-(1) defined in Section 2.2 f( can be written as ((1) (xx) ((.))) (
where U,(!) contains the indices (1. basis functions present (1) We can use Theorem 2.2
and choose n carefully such that f( approximates f within c for L norm. The goal is now to approximate f!!) with shallow neural network. Note that the basis functions can be written as a product of univariate functions Φτ,; = 11 &1g,iy. We can therefore use a similar structure to the product approximation of Proposition 3.2 approximate the basis functions. Specifically, the first layer approximate the d(2" - 1) = ( (log - terms log Φi,.,, necessary to construct the basis functions (2(1) and a second layer to approximate the exponential in order to obtain approximations of the ((2"nd11) O(e i (log s(d-1) basis functions of (=()). We provide
detailed figure illustrating the construction, Figure S in Appendix B.3
The shallow network that we constructed in Theorem 3.1 uses the ReLU activation function. We extend this result to larger class of activation functions which include commonly used ones.
Definition 3.3. A sigmoid-lin activation function R + IR is non non-decreasing function having finite limits in 30. A ReLU-like activation function a R - R is a function having horizontal asymptote in -c i.e. is bounded in IR,, and an affine (non-horizontal) asymptole in +oo, i.e. there exists > 0 such that (xx) br bounded R
Most common activation functions fall into these classes. Examples of sigmoid-like activations in- clude Heaviside, logistic, tanh, aretan and softsign activations, while ReLU-like activations include ReLU, ISRLU, ELU and soft-plus activations. We extend Theorem 3.1 to all these activations.

---

Published as a conference paper at ICLR 2022
Theorem 3.4. For any approximation tolerance a neural network with depth 2 and Oc 2 (log. 2
0. and for any f x2 there exists training parameters that approximates f
3id-11 11
within e for the infinity norm, with O (
3id
(resp. O log(
9(-=)) neurons
for Rel.U-like (resp. sigmoid-like, activation.
We note that these results can further be extended more general Korobov spaces X Indeed, the main dependence of our neural network architectures in the parameters r and arise from sparse grid approximation. Bungartz& & Griebel (2004) show that results similar to Theorem can be extended to various values of т, p and different eπror norms with similar sparse grid construction. For instance, we can use these results combined with our proposed architecture to show that the Korobov space X can be approximated in infinite norm by neural networks with O(e (log }) = (d-1) training parameters and same number of neurons up to a polynomial factor in 6.
THE REPRESENTATION POWER OF DEEP NEURAL NETWORKS
Montanelli & Du (219)) used the sparse grid approach construct deep neural networks with ReLU activation, approximating Korobov functions with O( - (log !) Wd-1i) +1) neurons, and depth (log 2) for the - norm. We improve this bound for deep neural networks with C² non- linear activation functions. We prove that we only need O (log 1)
"(d")) neurons and fixed
depth, independent of e, to approximate the unit ball of the Korobov space within in the - norm.
Theorem 4.1. Let E C2 be non-linear activation function. Let >>> O. For any function X2. (I2), there exists a neural network of depth [log, d. + with ReLU activation on the first layer and activation function for the next layers, O Olo=à(log? 2) ato-"))
neurons, and Occ->(log) 1) training parameters approximating f within for the infinity norm.
Compared to the bound of shallow networks in Theorem 3.1 the number of neurons for deep net- works is lower by factor (VVE), while the number of training parameters is the same. Hence, deep neural networks are more efficient than shallow neural network in the sense that shallow networks need more "inactive" neurons reach the same approximation power, but have the same number of parameters. This gap in the number of "inactive" neurons can be consequent in practice, as we may know exactly which neurons train and which neurons fix.
This new bound on the number of parameters and neurons matches the approximation power of sparse grids. In fact, sparse grids use O(e-à (log +) " parameters (weights of basis functions) to approximate Korobov functions within e. Our construction in Theorem shows that deep neural networks with fixed depth in e can fully encode sparse grids approximators. Neural networks are therefore more powerful function approximators. In particular, any sparse grid approximation using (c)()) parameters, can be represented exactly by neural network using (N(()) neurons.
The deep approximating network (see Figure 3 has a very similar structure to our construction of an approximating shallow network of Theorem 3.1 The main difference lies the approximation of the product function. Instead of using a 2-layer neural network, we now use deep network. The following result shows that deep neural networks can represent exactly the product function.
Proposition 4.2 (Lin et al. (017)). Appendix A). Let be C2 non linear activation function. For any approximation error c > O, there exists a neural network with [log, d. hidden layers and activation o, using at most 8d neurons arranged binary tree network that approximates the product function I 24 on [0, 1ld 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 independent the approximation precision e, 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 [Ln et al.) (2017). however, the question of whether could approximate the product with shallow network and a polynomial number of neurons, remained open. In Proposition 3.2 we answer positively to this question by constructing an c-approximating neural network of depth 2 with ReLU activation and
Odt - log !) neurons. Using the same ideas in Theorem 3.4 can generalize this result to

---

Published as a conference paper at ICLR 2022
O (log 2)
=
functions Pi (rz)
21
22
2d
0009
8ooo cooo
(1,((1)
Ruea I(21) o a 2,,2n ((0))
P11
[log2
Pt.s
(5))
f(x))
1 O( (log )
Id-11)
basis functions 0z,6
Figure 3: Deep neural network approximating a Korobov function / E (2) within c. The complete network has O(e (log )
add neurons and depth [loge df +
obtain e-approximating neural network of depth 2 with Od log 2) neurons for ReLU-like activation, or ( log )) neurons for sigmoid-like activation.
NEURAL NETWORKS ARE NEAR-OPTIMAL FUNCTION APPROXIMATORS
In the previous sections, proved upper bounds on the number of neurons and training parameters needed by deep and shallow neural networks to approximate the Korobov space X x². (12). We now investigate how good is the performance of neural networks function approximators. We prove a lower bound on the number of parameters needed by any continuous function approximator approximate the Korobov space. In particular, neural networks, deep and shallow, will 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 De Vore al. (1989).
For any Banach space X-c.g.. a function space-and subset K C. X' of elements to approximate, define continuous function approximator with N parameters K > N together with reconstruction scheme which is N-dimensional manifold M, R.N + X. For any element f K, the approximation given is My(((f)): the parametrization is derived continuously from the function f and then given input the reconstruction manifold that outputs an approximation function in X. The error of this function approximator is defined as My (K)x := sup |/ M (a(f)) The best function approximator for space K minimizes this error. The minimal error for space is given by
continuous parametrization
(K(K) min EN,,,Mx (K)x.
a,My
In other terms, a continuous function approximator with N parameters cannot hope to approximate K better than within F (K)x- A class of function approximators is set function approximators with given structure. For example, neural networks with continuous parametrizations of function approximators where the number of parameters the number of training parameters. We say that 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 approximate functions in K within e matches asymptotically, within a constant, the least number of parameters N needed to satisfy Ex (x())x S e. The norm considered in the approximation of the functions of K the norm associated to the space X. De et al. (1989) showed that this minimum error E (K)x is lower bounded by the Bernstein width of the subset K C X, defined as
class
by (K)xxx sup sup(p: (XNN)+1) K}. X
8

---

for elements of Published as a conference paper at ICLR 2022
where the outer sup is taken over all N + + dimensional linear sub-spaces of X, and UY) denotes the unit ball of for any linear subspace Y of X'
Theorem 5.1 (De et al. 1989). Let a Banach space and K C C. Ev(K)x 2 (x())x.
We prove a lower bound on the least number of parameters any class of continuous function approx- imators needs to approximate functions of the Korobov space.
Theorem 5.2. Take X = _ (12) and K = {f E (2) : Iflx2 S 1 the unit ball of
the Korobov space. Then, there exists > 0 with (x(K)x 2 Na (log N) Equivalently, for > 0, continuous function approximator approximating within e in L norm uses at least O (log 2) +) parameters.
Sketch of proof We seek an appropriate subspace XN+1 in order to get lower bound the Bernstein width (K)x, which in turn provides a lower bound on the approximation enror (Theorem To do so, we use the Deslaurier- Dubuc interpolet of degree 2, g( (see Figure which is C2. Using the sparse grids approach, we construct a hierarchical basis in x (S2) using ei as mother function and define X as the approximation space Vi(a) Here n is chosen such that the dimension of (i(1) is roughly N + 1. The goal is to estimate sup(p= pU(XN+1) C K], which will lead to a bound on (x).)x.. To do so, we upper bound the Korobov norm by the - XN+1. For any function E XN+1 we can write Σi, U2 ÔL, Using stencil representation of the coefficients Vi we are able to obtain an upper bound [u] x2,x I Ta]|u//oo where Ta O(22nna-1) Then, by (K)xx 2 1/Ta which yields the desired bound.
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 e: O(e (log ) 3:4-1i (Theorem 3.1 and Theorem 4.1p. It exhibits the same exponential dependence in with base log _ and the same main dependence on of e 1. Note that the upper and lower bound constructions in Theorem 3. and
be rewritten as O(c-1/2-6) for all 5 > 0. Moreover, Theorem[4.1] are continuous, which comes directly from the continuity of the sparse grid parameters (see bound on Ut, in Theorem [.2 Our bounds prove therefore that deep and shallow neural networks are near optimal classes of function approximators for the Korobov space. Interestingly, the subspace XN+1 our proof uses 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 [nd 4. The difference is the choice of the interpolate di to construct the basis functions, degree 2 for the former (which provides needed regularity for the proof), and 1 for the later.
6 CONCLUSION AND DISCUSSION
We proved new upper and lower bounds the number of neurons and training parameters needed by shallow and deep neural networks to approximate Korobov functions. Our work shows that shallow and deep networks not only lessen the curse of dimensionality but are also near-optimal.
Our work suggests several extensions. First, it would be very interesting to see if our proposed theoretical near-optimal architectures have 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 class of functions with given number of neurons and param- eters. Second, our upper bounds (Theorem 3.T and 4.1p nearly match our lower bounds (Theorem 5.2 on the least number of training parameters needed to approximate the Korobov space. We wonder if it is possible to close the gap between these bounds and hence prove neural network's optimality, e.g., one could prove that sparse grids are optimal function approximators by improv- ing our lower bound to match sparse grid number of parameters O(E à (log 4) 3id-1) ). Finally, we showed the near-optimality of neural networks among the set of continuous function approximators. would be interesting to explore lower bounds (analog to Theorem 5.2 when considering larger sets of function approximators, e.g., discontinuous function approximators. Could some discontinuous neural network construction break the curse of dimensionality for the Sobolev space? The question is then whether neural networks are still near-optimal in these larger sets of function approximators.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors are grateful to Tomaso Poggio and the MIT 6.520 course teaching staff for several discussions, remarks and comments that were useful to this work.
REFERENCES
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14()):115-133, 1994.
Hans-Joachim Bungartz. Dünne Gitter und deren Anwendung bei der adaptiven Lösung der dreidi- mensionalen Drisson-Gleichung Technische Universität München, 1992.
Hans-Joachim Bungartz and Michael Griebel. Sparse grids. Acta numerica, 13(1):147-269, 2004.
Gilles Deslauriers and Serge Dubuc. Symmetric iterative interpolation processes. In Constructive approximation, pp. 68. Springer, 1989.
Ronald A Vore Ralph Howard, and Charles Micchelli. Optimal nonlinear approximation. Manuscripta mathematica, 63(4):469 478, 1989.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural networks, 2(5):359-366, 1989.
Masaaki Imaizumi and Kenji Fukumizu. Deep neural networks learn non-smooth functions effec- tively. In The 22nd international conference on artificial intelligence and statistics, pp. 869-878. PMLR, 2019.
Jason M Klusowski and Andrew R Barron. Risk bounds for high-dimensional ridge function com- binations including neural networks. arXiv preprint arXiv: 2016.
Jason M Klusowski and Andrew Barron. Approximation by combinations of relu and squared relu ridge functions with 11 and 10 controls. IEEE Transactions on Information Theory, 64(12): 7649-76560 2018
Michael Kohler and Adam Krzyžak. Adaptive regression estimation with multilayer feedforward neural networks. Nonparametric Statistics, 17(8):891-91) 2005.
Michael Kohler and Adam Krzyzak. Nonparametric regression based on hierarchical interaction models. IEEE Transactions Information Theory, 6320):162- 2016.
Michael Kohler and Jens Mehnert. Analysis of the rate of convergence of least squares neural network regression estimates in case of measurement errors. Neural Networks, 24(3):273-279 2011.
NM Korobov. Approximate solution of integral equations. Doklady Akademüi Nauk SSSR, 128(2): 235-238, 1959.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Communications of the ACM, 60(6):84-99) 90, 2017.
Shiyu Liang and Rayadurgam Srikant. Why deep neural networks for function approximation? arXiv preprint arXiv: 1610.04161, 2016.
Henry W Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work so well? Journal of Statistical Physics, 168(6)): 1223-1122212: 1247, 2017.
Hrushikesh N Mhaskar. Neural networks for optimal approximation of smooth and analytic func- tions. Neural computation, 8(1):164-177, 1996.
Hrushikesh N Mhaskar. Eignets for function approximation on manifolds. Applied and Computa- fional Harmonic Analysis, 29(1):63-87, 2010.
10

---

Published as a conference paper at ICLR 2022
Hrushikesh N Mhaskar, Qianli Liao, and Tomaso Poggio. Learning functions: when is deep better 2016.
than shallow. arXiv preprint
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.
Hadrien Montanelli, Haizhao Yang, and Qiang Du. Deep ReLU networks overcome the curse of dimensionality for bandlimited functions. arXiv preprint arXiv:1903.00735, 2019.
Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and estimation of deep neural network with intrinsic dimensionality. 2019.
Erich Novak. Deterministic and stochastic error bounds in numerical analysis. 2006.
Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Networks, 108:296-330, 2018.
Johannes Schmidt-Hieber. Deep ReLU network approximation of functions on manifold. arXiv preprint arXiv: 1900.0000000 00695, 2019.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):4844489, 2016.
Sergei Abramovich Smolyak. Quadrature and interpolation formulas for tensor products of certain classes of functions. In Doklady Akademii Nauk, volume 148, pp. 1042-1045, Russian Academy of Sciences, 1963.
Taiji Suzuki. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality, arXiv preprint arXiv:1810.08033 2018.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pp- 1517-1539. PMLR, 2016.
Weinan, Chao Ma, and Lei Wu. Barron spaces and the compositional function spaces for neural network models. arXiv preprint arXiv:1906.08039 2019.
Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103-114, 2017.
Ch Zenger and W Hackbusch. Parallel algorithms for partial differential equations. In Notes Numerical Fluid Mechanics, volume 31, pp. 241-251. Vieweg. 1991.
Christoph Zenger. Sparse grids. Parallel Algorithms for Partial Differential Equations, 31, 1991.
APPENDIX
A ON KOROBOV FUNCTIONS
In this section, further discuss Korobov functions (2.) Korobov functions enjoy more smoothness than Sobolev functions: smoothness for (22 is measured in terms of mixed deriva- lives of order two. Korobov functions X2.((1) can be differentiated twice in each coordinates simultaneously. while Sobolev W2-P(S) functions can only be differentiated twice in total. For example, in two dimensions, for function be Korobov is required have
0s Øʃ 821 8 0 0S
05
04S
TP((),
0x Oxz Pri Paz' Oxz Pxidxz" Prprr 8 x R while for f to be Sobolev it requires only
oʃ 0s 0 84 OS
(l))
On Ozg" pr, Pxz' dz

---

Published as a conference paper at ICLR 2022
The former can be seen from |al I 2 and the latter from |a] I 2 in the definition of XX))(() and W?))(
We provide intuition on why Korobov functions are casier to approximate. One of the key difficulties in approximating Sobolev functions are possible high frequency oscillations which may require exponential number of neurons (Telgarsky 2016). For instance, consider functions which have similar structure to W Wnn....) (defined in Subsection 2.2): for any smooth basis function & with support the unit cube (see Figure 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 2- This corresponds exactly to the construction of W(n....)) which uses the product hat function on each dimension as basis function 6. This function space can have strong oscillations in all directions time. The Korobov space prohibits such behavior by ensuring that functions can be differenti- ated twice on each dimension, simultaneously. As a result, functions cannot oscillate in all directions 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 re- stricted 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 hard constraint of cutting high frequencies, the Korobov space asks for smoothness conditions which do not prohibit high frequencies but rather impose 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 vi(") which we used 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 (2(1) is defined as
V
W₂.
Intuitively, this approximation space introduces "budget" of oscillations for all dimensions through the constraint Dd 4 S n + As a result, dilations of the basis function can only occur in restricted set of directions at time, which ensures that the Korobov norm stays bounded.
B PROOFS OF SECTION 3
B.1 APPROXIMATING THE PRODUCT FUNCTION
In this subsection, we construct neural network architecture with two layers and Old log !) neurons that approximates the product function p a E [0, 1] - I 24 within e for all e 0, which proves Proposition 3.2] We first prove 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 pieces is repre- sentable 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 (011)). We recall the proof for completeness. Let .i .... S #m 1 be the subdivision of the piece-wise affine function f. We a neural network of the form
m-1
s(x) f(x1)
Σ
wx(x xx)+ wo x)
where wi is the slope of f on the piece S 11, wi the slope of f on the piece x2).
wkk [(x+11) (x)
- wi (2 2.4)
P4+1 26
for k = 1, ... 2, and wm-1 3 - - mm- Wk where é is the slope of f on the piece 2 Fm-1- Notice that f and coincide on all Øg for 1 < S m 1. Furthermore, g has same slope as f on each pieces, therefore, g y=
12

---

Published as a conference paper at ICLR 2022
We can approximate univariate right continuous functions by piece-wise affine functions, and then use Lemma B.I to represent them by shallow neural networks. The following lemma shows that O(e neurons sufficient to represent increasing right-continuous function with shallow neural network.
Lemma B.2. Let f d) be right-continuont increasing function where an interval, and let e > O. There exists a shallow neural network with ReLU activation, with d= neurons on single layer, that approximates f within for the infinity norm.
d=م Define subdivision of the image interval S y1 ... S Um d where Proof. Let
yh = c ke for ,,...,,, Note that this subdivision contains exactly [d=] pieces. Now define subdivision of T, 22 S S Fm by
24 == sup E I, S W
for h: 1, ........................ This subdivision stills has d=cc pieces. We now construct approximation
function f on as the continuous piece-wise affine function on the subdivision 21 S .... S Imm such that f(xx)) for all 1 S k < m and f is constant before æ and after Im (see Figure 4 Let I.
If x S ø1, because f is increasing and right-continnous, e f(z) f(z1)( v1 cc Therefore [f(x) [x)) (f(x) (c + c)l s.
If xy x S TR+1s we have yk < f(x) S f(xx+1) S yk+1- Further note that yk S
f(x) S yk+1- Therefore [f(x) f(x) S yk++ - =
If fm x. then Um < { S d. Again, (f(x) f(x)) = 15(x) - ym S d ym Se.
Therefore ||ʃ fl S We can now use Lemma B. to end the proof.
y
ym
1/2
c]
8/
6 = y0
350
Zm
Figure 4: Approximation of right-continuous increasing function (blue) in interval [c, d] within by piece- wise linear function (red) with ععم pieces. The approximation is constructed using regular subdivision the y axis of step and constructing a linear approximation the pre-image of each part of the subdivision.
the function to approximate has some regularity, the number neurons needed for approximation can be significantly reduced. In the following lemma, we show that O(e $ neurons are sufficient approximate C univariate function with shallow neural network.
13

---

Published as a conference paper at ICLR 2022
Lemma B.3. Let f [a. - [c, C2, and let e >> O. There exists a shallow neural network with ReLU activation, with //r min(J (I +1 ()( (b a) /) neurons on a single layer, where p(J,e) 6) - as e + O, that approximates I within e 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 truncated log function, which we will use in the construction of our neural network approximating the product.
sufficiently small and ê > O. Consider the truncated logarithm function log: [6, 1] R. There exists shallow neural network with ReLU activation, with E log 3 neurons on a single layer, that approximates f within e for the infinity norm.
Corollary B.4. Let
Proof. See Appendix B.2.2
We are now ready construct a neural network approximating the product function and prove Proposition 3.2 The proof builds upon on the observation that I T = e log æx). We construct
approximating 2-layer neural network where the first layer computes log x, for 1 1 i S d, and the second layer computes the exponential. We illustrate the construction of the proof in Figure
Proof of Proposition 3.2
Fix e >> 0. Consider the function he x [0, 1] H max(logæ, æ, loge)
[log e, 0]. Using Corollary B.4 there exists neural network he [0. 1] + [loge, 0] with 1 + [ log neurons on a single layer such that ||,r - helloo S á. Indeed, one can take the e-approximation of h2 x [] log x [log e, Oj. then extend this function to [0, e] with constant equal to log The resulting piece-wise affine function has one additional segment corre- sponding to additional neuron in the approximating function. Similarly, consider the exponential g x E R_ + e" E [0, 1]. Because is tight-continuout increasing, we can use Lemma B.3 to con-
struct a neural network 9. IR_ - [o, 1] with 1 Vzc log neurons on a single layer such that ||g loc < e. Indeed, again one can take the e-approximation of g. : [log e, 0] e [0, 1], then extend this function to (-o0, log c] with a constant equal to The corresponding neural net- work has additional neuron. We construct our final neural network o: (see Figure
Ehe (a)(
$. -e
Note that &. can be represented as a 2-layer neural network: the first layer is composed of the union
of the 1+ + log 2 neurons composing each of the 1-layer neural networks hi x E [0, 1] +
hh (x:)) E R for each dimension E (1,..., d). The second layer is composed of the 1 + neurons of ge. Hence, the constructed neural network é. has Odd log !) neurons. Let now analyze the approximation error. Let æ E [0, 1]d. For the sake of brevity, denote ý = > h (z,) and y Ei log( We have,
1 log
v2c
d
(x)(x) - -px) s 10.(z) - exp(())+|exxp))
+ exp((i exp(v)) $ <e + II x eep(( - v) - 1/,
2m1
where we used the fact that (x) - exp(i)) = lge - 9(0) - 1l9. glooo S.
First suppose that æ 2 In this case, for all i E (L..., df we have (z.) log(z;)) = 1he
he (x:)) S. Then, lØ-y] < e. Consequently, (w)) p(=))))(111 S e+max(le= |/,e (1) < 3e, for
e <> 0 sufficiently small. Without loss of generality now suppose x1 S <. Then ÿ S (1(211) < log
so by definition of ge, we have 0 < (x))) ( < exp(loge) Also. 0 - p(x) < so finally ().())) p(z)) Se.
14

---

Published as a conference paper at ICLR 2022
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. with O( log [1) neurons and 9e with ( neurons. Therefore. the corresponding neural network would approximate the product p with O log 2) neurons.
B.2 MISSING PROOFS OF SECTION B.1
B.2.1 PROOF OF LEMMA B.3
Proof. Similarly the proof of Lemma B.2 the goal is to approximate by piece-wise affine function f defined a subdivision 3i S 21 S ... Fm Im++1 b such that f and coincide on 20..... 2m+1- We first analyse the error induced by linear approximation of the function on each piece. Let z [u, 2] for u, E I. Using the mean value theorem, there exists Oz [u, xr such that f(x) f(u) = f'aa)
u) and Br E [ar, o) such that f(v) f(x) (3) z). Combining these two equalities, we get,
f(x) f() - (x - w) 5(v) f(u) (v (f(()) f(u)) (a -
4 (x u) u) (3x) -f((()) fh= (I)(
(x - u)(v - x)
Hence,
f(v) f(u) u (x u)(v x)) Sh (")())tt
[x) f(u) (x u)
v
We now apply this result to bound the approximation error on each pieces of the subdivision. Let k E [m]. Recall f linear on the subdivision [ xx+1] and ((xx) = f(xx) and f((++1) =
( Hence, for all E [æg, #k41), f(x) f(xx) + (x - 2x) M(02+1)- Using Equation #2+1-2
equation with u Fg and v Tk+1, we get,
Sor f"
Ilf fll $
sup xE =e
(x - (x-xx) xx)(1 x)
xR+1 I
1N+T [S"(1)
[3k+1 - rx)
< (x++1 J. 2 Ilo" [0x.221))
yields an e-approximation of with Therefore, using regular subdivision with step V 7
2x
(b- /11""
pieces.
V2c
We now show that for any >> 0, there exists an c-approximation of f with at most SV Pd
V2 (1 +
pieces. To do so, we use the fact that the upper Riemann sum for v converges to the integral since v is continuous [a, b). First define partition X, Xx b of (a, b) such that
the upper Riemann sum R( (()")) on this subdivision satisfies R(VJ") S (1 + p/2) VTT. Now 2c
define on each interval T of the partition a regular subdivision with step / T as before. Finally,
consider the subdivision union of all these subdivisions, and construct the approximation f on this final subdivision. By construction, || - flloo S because the inequality holds on each piece of the subdivision. Further, the number of pieces is
K
(X++1 Xi) x. VI" R(VF") + + < [v
Σ 1+
(1 + 1):
V2e
V2e
/2e
2=0
for small enough. Using Lemma
B.I complete the proof.
15

---

Published as a conference paper at ICLR 2022
d(2" 1) OiE (log ) +) functions oi,, (zz)
21
32
ad
Oldec log
log 01.1 (x1)
log On.2
log 111)
log Pon."" - (202)
log 2n -1 (20a)
Ole
log
(x)
, (z²)
fwx)
(
O(E (log] )
Md 1)
basis functions dz.
Figure 5: Shallow neural network with ReLU activation approximating a Korobov function f 22 (52) within in infinity norm. The network has O(<='(log ?) "4" neurons on the first layer
3(d-1) () neurons on the second layer.
and O (log ))
B.2.2 PROOF OF COROLLARY B.4
Proof. In view of Lemma B.3 the goal is to show that we can remove the dependence of p(f e) in This essentially comes from the fact that the upper Riemann sum behaves well for approximating log. Consider the subdivision == I x1 S
& Im+1 1 with = L log ! where == log(1 + 2 such that 2a = á for = 0, ..... m
Denote the corresponding piece-wise affine approximation. Similarly to the proof of Lemma B.3 for k = m,. 1,
(E 1)
log - -00oooo S (Jx+1 - 110
Se.
The proof follows.
B.3 PROOF OF THEOREM 3.1 APPROXIMATING THE KOROBOV SPACE 22
In this subsection, we prove Theorem 3.1 and show that we can approximate any Korobov function
f x2 (12) within with 2-layer neural network of O(E (log 2) -)",,,,) neurons. We illustrate the construction in Figure(3. Our proof combines the constructed network approximating the product function and a decomposition of f as sum of separable functions, i.e. a decomposition of the form
K
d
f(x)
II
(I,),
Vo E [0.
Consider the sparse grid construction of the approximating space (i(1) using the standard hat func-
tion mother function to create the hierarchical basis Wi (introduced in Section 2.2). We recall that
the approximation space defined as ()(1) == A [1 Sn+d-1 Wi. We will construct neural network approximating the sparse grid approximation and then use the result of Theorem 2.2 derive the approximation error. Figure gives illustration of the construction.
Let ((( be the projection of on the subspace (2(1) f(() can be written as
(x)
Σ (x))
(L.))EU))
16

---

Published as a conference paper at ICLR 2022
where ( contains the indices (1, i) of basis functions present in V i.e.
- (11,)), In 1, 2 11 2 odd for all 1 1 d}.
(2)
Throughout the proof, we explicitly construct neural network that uses this decomposition to ap- proximate f( We then use Theorem 2.2 and choose n carefully such that f& approximates within for - norm. Note that the basis functions can be written as a product of univariate functions ti, = I== Ö1zي We can therefore use the product approximation of Proposition 3.2 to approximate the basis functions. Specifically, we will use one layer approximate the terms log وy and a second layer to approximate the exponential.
We now present in detail the construction of the first layer. First, recall that Φig, is a piece-wise affine function with subdivision 0 I 4-1 b 2 2
I
4+1
S Define the error term ē 20/
24
We consider a symmetric subdivision of the interval
1-1-2 2
25 We define it as follows:
1-1+8 Fo 2 S œ1 S ... S Im+1= 25 S Im+22
S
S 22m+2
4+1-/
where m 25
log
: and co == log(1 + /2//d). such that
2k = is - 1 + glog keo
0 S k S m,
2
2g iz + 1 clog 2+ 22m+2-
m + 2 < S 2m + 2.
24
Note that with this definition, the terms log mg i,) form a regular sequence with step cp- We now construct the piece- wise affine function . on the subdivision Zo S ... S 22m+2 which co- incides with log or on To. #2m++2 and is constant on [0, zoo and [22m+ 1]. By Lemma B.1 this function can be represented by 1-layer neural network with as much neurons as the number of
pieces of 9. i.e. at most 2 3d
? log 2/ neurons for sufficiently small. A similar proof to that of Corol-
lary B.4 shows that 9 approximates max(log Φt log(E/3)) within ě/(3d) for the infinity norm. We This construction compute in parallel, =/dds)-approoimaaiioo of max(log oi,,,, (Iz)), log é) for all S j S d, and S 1 S n, S ij S 2 where i, odd. These are exactly the 1 1-dimensional functions that we will need, in order to compute the d-dimensional function basis of the approxima- tion space V)( There are d(2" 1) such univariate functions, therefore our first layer contains at most 2 A log neurons.
3d
We now turn to the second layer. The result of the first two layers will be e/3-approximations of Φ1,1 for all iI, E U.!). Recall that U(! contains the indices for the functions forming a basis of the approximation space " To do so, for each indexes (1, U:!") we construct a 1 1-layer neural network approximating the function exp, which will compute an approximation of cxp( +
". The approximation of exp constructed in the same way as for Lemma B.3 Consider
regular subdivision of the interval (log(?/3), 0) with step /2(r/3), i.e. Ti = log(2/3)
S x1 <
< Im S Tm+1 = where m = [v
3 22 log such that 2g = log ē + kv 0 < k S m.
Construct the piece-wise affine function h on the subdivision 20
S Im+1 which coincides with exp on To. 11 and is constant on (-00, mn). Lemma B.3 shows that h approximates cxp 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. + [V
3 log The second layer is
the union of 1-layer neural networks approximating exp within e/3, for each indexes (1, (1) 22 log neurons. As shown in Bungartz & [1+
Therefore, the second layer contains (u(
Griebel 2004
n-1 1 ( = 2¹. d (d-1+)) 1+ = (-1)d+2"
1-1
n + d - 1)
1) (-2)d-1-i 2n. nd-1 (d (d-1)) + 0((d-2)
d -
i
0=0
1=00
17

---

Published as a conference paper at ICLR 2022
Therefore, the second layer has (2n x"1
(d-1jt ē log neurons. Finally, the output layer computes
the weighted sum of the basis functions approximate fi) Denote by fil the corresponding function of the constructed neural network (see Figure 5), i.e.
d Eo(zy)
A = E
o1 h (LI))US))
Let us analyze the approximation error of neural network. The proof of Proposition 3.2 shows that the output of the two first layers h -===0(3)) approximates Φ1,1 within é. Therefore, we
obtain
11 Pi loe I 3 (iieevs |m.il. We now use approximation bounds from Theorem 2.2
on S.
2. 2.1. 8d
|l 11 S 1 1l + 1 ac I
22
f2 (1.))
where
d d 1+)
Σ lunal S 1f Σ 2-
S 11,,000
d -
(Li))E
120
Let us now take min n:
2 A(d, n) S 2 Then, using the above incquality shows
82
that the neural network ( approximates within for the infinity norm. the number of neurons in each layer of this network. Note that
We will now estimate
1
1,,,0 e
ne
log
and 2 S 8 (2 (2 2) d- (d 1)13
log
(1 + 0(1).
log
(3)
We the above estimates show that the constructed neural network has at most N₁ (resp- N₂) neurons on the first (resp. second) layer where
8v6d
1f
1
N1 82 (2log 2)
log
- d!
3(d
4
1f
1
N2 -o 22/2 2)
log
d!
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 the weighs vi, of the sparse grid decomposition. This number 0 n d-11) = O(E (log )) 3(4-1)
is [0:
B.4 PROOF OF THEOREM 3.4 GENERALIZATION TO GENERAL. ACTIVATION FUNCTIONS
We start by formalizing the intuition that a sigmoid-lie like (resp. ReLU-like) function is a function that resembles the Heaviside (resp. ReLU) function by zooming out along the (resp. and y) axis.
Lemma B.6. Let be sigmoid-like activation with limit (resp. b) in (resp.+oc). For any 8 O and error tolerance
0, there exists a scaling M 0 such that x a(dzz) b-a
approximates the Heaviside function within e outside of (-8, 8) for the infinity norm. Furthermore, this function has values in [0. 1).
Let be a ReLU-like activation with asymptote b
+00. For any 8 > and error tolerance o(Mz) approximates the ReLU function within e Mb
E <>> 0, there exists a scaling M such that - for the infinity norm.
18

---

Published as a conference paper at ICLR 2022
Proof. Let 8, 0 and a sigmoid-like activation with limit (resp. b) in -oo (resp. +o0). There exists 2g > sufficiently large such that (b-a) ( a I for x I -20 and (b-a)lo(x)) (x) b| S e
for x 2 2o. It now suffices to take M == z to obtain the desired result.
Now let be a ReLU-like activation with oblique asymptote bz +oo where b > 0. Let M such
that | - Mbc for x
< 0 and [0(x)) - bbx S Mbe for x 2 0. One can check that [
Mb S for
x S 0, and
(M2)) 2 - for x 2
Mb
Using this approximation. we reduce the analysis of sigmoid-like (resp. ReLU-like) activations to the case of Heaviside (resp ReLU) activation prove the desired theorem.
Proof of Theorem 3.4 We start by the class of ReI.U-like activations. Let be ReLUUlike activation function. Cemma|B.6]shove that one can approximate arbitrarily well the ReI.U activation with 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 + e(Mz)
Mb with no additional neuron nor parameter. Because the approximation continuous, we can take M > O arbitrarily large in order to approximate ff 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 Lemma B.3 are not valid for general sigmoid-like like activations in particular the Heaviside we can obtain an analog to Lemma [.2 as Lemma B.7 given in the Appendix B.4.1] This results is an increased number of neurons. order to approximate target function f E 22 (S2), 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 Φi,, in the
we use Lemma B.7 Therefore, 12d log a neurons are needed to compute ě/(3 (3)-
first layer. Instead of using Corollary B.4
= of max(log .t. log(E/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- appooiproi of the exponential on R_ with 6 neurons for the second layer. As result, the first layer contains at most 2 3d log 1/ neurons for sufficiently small, and the second layer contains
U neurons. Using the same estimates in the proof of Theorem 3.1 shows that the constructed neural network has at most N₁ (resp. N2) neurons on the first (resp. second) layer where
3.2 1/2
1
N1 c
log
85
(2log 2)
- d!
3id
24 db
N₂ 8
log
(2log 2)
3d-1)
d!
This ends the proof.
B.4.1 PROOF LEMMA B.7
Lemma B.7. Let a be a sigmoid-like activation. Let f I I [c, d] be a right-continuous in- creasing function where T is an interval, and let > 0. There exists shallow neural network with activation a, with at most dec neurons on a single layer, that approximates I within for the infinity norm.
Proof. The proof is analog that of Lemma B.2 Let [-= We define regular subdivision of the image interval c < y1 < < Vm & d where c + ke for k = 1,..., m, then using the monotony of f. we can define subdivision of I, 31 S ... S Im such that 24 == II < ). Let us first construct an approximation neural network f with the Heaviside activation. Consider
f(xx = yn +
Σ
Iz + x4+1 2 20)
x
2
1=1
19

---

Published as a conference paper at ICLR 2022
Let [c, d] and & such that [atk #x+1]. We have by monotony ys f(æ) 3k+1 and yh y1 + (k -k- 1)e S f (x) y1 ke yk++1 Hence, f approximates within e infinity norm. Let å < minicIl..., (Zi+1 z/)/4 4 and a general sigmoid-like activation with limits in -oc and b in +00. Take M given by Lemma B.7 such that a(Ma) approximates the Heaviside function within 1/m outside of (-8, 6) and has values in [0. 1]. Using the same arguments as above, the function
b-a
m-
Mx. M
f(x) = y +
b
approximates f within 2e for the infinity norm. The proof follows.
C PROOFS OF SECTION 4
C.1 PROOF OF THEOREM 4.1 APPROXIMATING KOROBOV FUNCTIONS WITH DEEP NEURAL NETWORKS
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% be the projection of f in the approximation space Vy(2) (defined Subsection 2.2) and U (defined in equation 2 the set of indices (t, i) of basis functions present in Vi(2) Recall f((?) can be uniquely decomposed as
1
Σ (1.))1.(x).
(LI))
where Φr, II وiy,úg are the basis functions defined Subsection 2.2 In the first layer, we compute exactly the piece-wise linear hat functions Φ then in the next set of layers, we use the product-approximatig neural network given by Proposition sis functions Ó,, m م'ييا (see Figure
to compute the ba- 3). The output layer computes the weighted sum E( (x) and outputs f(()) Because the approximation has arbitrary precision,
chose the network of Proposition 4.2 such that the resulting network f verifies ||. 1 1--"" I1x0 S e/2.
More precisely, di is piece-wise linear with four pieces, neurons with ReLUU activation on a single layer (Leema B.... Our first layer composed of the union of all these ReLU neurons, for the d(2" 1) indices L,,2, such that 1 S j S d, 1 L S n, 1 iz < 2 and ij is odd. Therefore, it contains at most d2 neurons with ReLU activation. The second set of layers is composed of the union of product-approxiinting neural networks to compute Φ1. for all (L, E (1) This set of layers contains [log, d] layers with activation and at most |0 8d neurons. The output of these two sets of layers is an approximation of the basis functions Φ1, with arbitrary precision. Consequently, the final output of the complete neural network is an approximation of S with arbitrary precision. Similarly to the proof of Theorem 3.1 we can chose the smallest n such that ||f - f S e/2 (see equation for details). Finally, the network has depth at most log, d + 2 and N neurons where
compute exactly with four
25 5//2
V f12,0 e
3(d-1)
N = 8d U(
logg
+00
88
log 2)
The parameters of the network depending on the function are exactly the coefficients Vh of the sparse grid approximation. Hence, the network has O( (log training parameters.
3dd-1)
20

---

Published as a conference paper at ICLR 2022
((
-3
-2
2
(
-3
2
(3)
-3
-2
-1
0
1
2 3
Figure 6: Deslaurier-Dutee interpolets of degree 1, and 3.
D PROOFS OF SECTION 5
D.1 PROOF OF THROREM 5.2 NEAR-OPTIMALITY OF NEURAL NETWORKS FOR KOROBOV
FUNCTIONS
Our goal is to define an appropriate subspace XN+1 in order to get good lower bound on the Bernstein width by xx) defined in equation which in turn provides a lower bound on the ap- proximation error (Theorem 5.1)
To do so, we introduce the Deslaurier- interpolet eLL) IR + IR. The construction of this function uses an interpolating scheme on binary rationals. First, ((4) is defined on all integers (k)) = 1 for k E Z. Then, we define the function on half integers 2 by fitting a polyno- mial of degree 2L 1 interpolating the standard hat function & at k:
1, -, k+ + L. Iteratively, 2:11 from the value of the interpolet on ratio-
we define the interpolet on binary rationals of the form 2k+1
nals with denominator 23. Specifically, let p(L) be the unique polynomial of degree 2L interpolating
((2)) at points K' for k' E (k - 1, L}. We set
(LL
2k +
== p(L) j.k:
2k 2k +1 27
2/+1
For example, for L
get (2) 2k+1)
16
(
(002( 16 ((2)(())))))))
I 16 k+3). (*+))) This process defines the interpolet on binary rationals. We then extend the func- tion to the real line by continuity. See Figure [ for an illustration. Deslauriers & Dubuc (1989)
16
proved that the regularity of the interpolet is an increasing function L the degree of interpolation.
We now prove results in the case L -- 2.
Lemma D.I. The interpolet of degree (12) is C² and has support Supp (σ(2) 31-3.3
Proof. See Appendix D.2.1
We will now use the interpolet (f2) to construct the subspace XN+1. Using the sparse grids ap- proach, we can construct hierarchical basis in x2)) using the interpolet gf(2) as mother func- tion. In the remaining of the proof, we will write é instead of d( for simplicity, and use the notations and definitions related to sparse grids, introduced in Subsection 2.2] Because y (K) is decreasing in N, it suffices to show the result for N,, when we define our space XN+1 to be exactly
the approximating space (1(1) of sparse grids XN,+1 = (1(1) The following equation establishes the relation between and N,, In the following, for simplicity, we will write N instead of N..
1+1 -1 2". ( dnd-1
N = 1=dimm (i)m((())-11==
Σ
211-1 = Σ
(dd-1)) + 0(n42))
d -
S
2=0
21

---

Published as a conference paper at ICLR 2022
First, let give some properties about the subspace XN+1-
Proposition D.2. Let E XN+1 and write it in decomposed form - Eve UL U1 where the sum is taken over all multi-indices corresponding to basis functions of X XN+1. The coefficients uL can be computed in the following way.
11 11g.5s u = 1,7
01
where 11,,,,== - (l(==(())) u(())
9
u(
( + te ut( x
+ to u 2 Here, I denotes the
T6
To
d-dimensional stencil which gives linear combination of values of u at 5" nodal points.
Proof. See Appendix D.2.2
Note that the stencil representation of the coefficients gives directly |r,al S 5 55]]// We are now ready to make our estimates. The goal is to compute sup(p: pU C K), which will lead to a bound on (x(x)xx. To do so, it suffices to upper bound the Korobov norm by the - norm for elements of XN+1. In fact, if I'a > 0 satisfies for all u E U(N++1), |u|x2.> Lallulllo then by x 2 1/Ta-
Now take XN+1 and let write = Et, Ut 01.s. Note that basis functions in the same hicrarchical class Wi are almost disjoint. More precisely, at each point æ E Qt at most 3 basis functions 01,i have non-zero contribution to u(x). Therefore, for any 0 S S 2.1. 1.
DD z
Σ
3d
|ur,al 22(0.) Dr*
max 15i52 1---11 fodd
Sn---d-1
n-1 Σ
d d11+t)
100|o| (ayleu
2
d d-1
60
(d - 1)! x1]x)
22n (n + O(n |/
Finally, denoting by Ca the constant
(d- |6) (2) we get for sufficiently large
60d
by (k(K)x 2 2Ca 22n nd-1"
Furthermore, recall N
(d-1). 2 n1 d-1 (1 0 (+)) Therefore,
los N Tog
and 2 (d
N 1)!(log 2)d (log N)
Finally obtain for some constant ca >> O,
by (K)x 2 cd N2 (log N)d-1
We conclude by analyzing the minimum number of parameters in order get e-approximation of the Korobov unit ball K. Define n, := min(n: C, ب S e). This yields nı, 2log log !.
and 2n V (2 2)d-1
T =T The number of needed parameters obtain an e approx-
Ve-llog
imation K is therefore
1 Ve
No Ōa
log
for constant Č. > 0.
Interestingly, the subspace XN+1 our proof uses to show the lower bound is essentially the same as the subspace
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.
22

---

Published as a conference paper at ICLR 2022
D.2 MISSING PROOFS OF SUBSECTION D.I
D.2.1 PROOF OF LEMMA D1
Lemma D.3. The interpolet of degree 2, 2 is C² and has support Supp (Φ(2) = [-3, 3].
Proof. To analyze the regularity of the interpolet, we introduce the trigonometric polynomial
k
(0) = Σ
((2)
jko + (e te t-i0)
(c 310
+ t 3:0)
2
16
16
KEZ
We can write (0) as
sin S(0),
(0) = sin
where 5(0) -
} 1n (e 10) is trigonometric polynomial of degree 1. Deslaurier and Dubuc
Deslauriers & Dubuc 1989 Theorem 7.11) showed that the interpolet ((2) has regularity log
log
where is the spectral radius of the matrix B [s)-2x] -15JA51 where sj the coefficients of the trigonometric polynomial S()). In our case, matrix writes
- 1/16
-/16
B
0
1/4
0
0 - 1/16
-1/16/
and has spectral radius 1/4. Therefore, the regularity of (5(2) is at least
log log 2 2. For the
support, check that more generally Supp(o(L) [-22L 1, 1].
D.2.2 PROOF OF PROPOSITION D.2
Proposition D.4. Let XN+1 and write it in decomposed form Σt, U1 01 where the sum is taken over all multi-indics corresponding to basis functions of X The coefficients u1 can be computed in the following way.
u I,.
where u1 = u( 1o u
16 ul 15+3) Here, It denotes the d-dimensional stencil which gives linear combination of values of at 5 nodal points.
16 ul 15+1
10 ul 3
I
Proof. We start by looking the 1-dimensional case. One can check that I1,011,3 1i-1,==-- Indeed, if > I of if ī = and f i, then Φ7,; will be zero at the nodal values of 4 Further, if < l the iterative construction of & gives directly.
9
+
i
i i+3 3
0
27
16 Pii
20
16
PE
20
16
2
16
015
2
Therefore, we obtain 11,07, = O. Finally, 4 = Σ1 U7. 41007. = U1 11,001 = Ut This
proves the stencil representation of v1, for dimension 1. Finally, using the tensor product approach of the stencil operator Jt, generalize the formula general dimensions.
23


Reviews:
[{"review_id": "hJT3VMWMHe1", "reviewer": "Reviewer_X13n", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n-in-depth study of Korobov function approximations\n-several new ideas/gadgets on how to represent such functions with NNs\n\n\nWeaknesses:\n-unclear presentation in several places: how do the bounds break the curse of dimensionality as stated in bullet point 1? \n-lack of motivation: Korobov functions seem like an interesting object for study, however this falls outside the community's \"standard\" knowledge, so the reviewer would expect much better explanation for why one should care for these functions in the context of Machine Learning or so. For example, the Conclusion states: \"This work therefore contributes to understanding the practical success of neural networks theoretically\" --> How is this the conclusion? Are Korobov functions prevalent in practice? The bounds in Th. 4.1 also seem to suggest that increasing depth from 2 to logd only shaves an sqrt{\\eps} factor which does not seem so significant, even though the depth increased substantially.\n\n\nQ: Why do the authors claim that they break the curse of dimensionality (e.g., page 2 bullet point 1?)? There is a strong dependence on d, right? What am I missing?", "summary_of_the_paper": "This paper studies approximation capabilities of neural networks for the purpose of approximating Korobov functions which are multivariate functions of bounded second mixed derivatives.\n\nThe 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.\n\nThis gives a complete picture for how Korobov functions behave wrt to function approximation with shallow or deep nets.\n\n", "summary_of_the_review": "Except several relatively minor issues with presentation and clarification of the results, the reviewer thinks this paper to be a good paper on the topic of approximating Korobov functions. More work is needed for presentation of the paper, and fixing a few things here and there (see above as well)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WkzOq_VWxeq", "reviewer": "Reviewer_G4AZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is nicely written, and the theoretical results are well explained. I believe the results are correct and sound, albeit I did not check every detail in the proof.\n\nI feel it should be good to discuss whether it is possible to consider higher-order mixed derivatives in Korobov spaces, for example, $X^{3, \\infty}$. On the other hand, extending to bounded $L^p$ derivatives with $p < \\infty$ can be interesting. Frankly speaking, I think the extension relies on if there are function approximation guarantees similar to Theorem 2.2 in the paper.\n\nCompared to Sobolev spaces, we see the approximation of Korobov functions is free of the curse of data dimensionality. My impression is that there should be some low-dimensional structures in Korobov space allowing the circumvention. The authors explains why Korobov is easier to approximate in Appendix A, while I think some high-level remarks should be placed in Section 2.\n\nThe authors may want to discuss more related works on efficient approximation theories of neural networks. There are works considering either structures in function spaces, e.g., Besov functions with dominated mixed smoothness, or structures in data space, e.g., manifold data. These works all demonstrate that the size of neural networks in function approximation does not suffer from the curse of data dimensionality.\n\n=========================================================================\n\nThanks for authors' detailed response. The generalization to $L_p$ norm guarantees is interesting. I am glad to hold a positive opinion on this paper.\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "I am positive on the paper, due to its clarity and technical depth. I think the paper can be rated a 7, yet there is no rating between 6 and 8. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "JBhvNc_VQLf", "reviewer": "Reviewer_bQiP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found paper to be very well written and easy to follow. The authors provide simple constructive proofs of the theorems, whose high-level ideas are well explained in the main text.\n\nThe discussion about the difference between Korobov and Sobolev spaces (Appendix A) is greatly appreciated. You mentioned there, that functions in Sobolev spaces can have more oscillations in various dimensions, and this can be the reason why they seem to be harder to approximate. It would be interesting to have a similar discussion to compare the Korobov space with the space of bandlimited function, which seem to avoid the curse of dimensionality. In particular, what do we intuitively gain in terms of expression power when extending the space of function from bandlimited functions to Korobov space ?\n\nOne question that would be interesting for practical purpose: By increasing the weights of the NN, one can approximate a function with any Korobov norm. In the proposed construction, what is the maximal weight magnitude that is used (in terms of dimension, accuracy and target function's Korobov norm) ? If the weight magnitude is restricted to a certain value, is it possible to design with a modified construction that account for such a constraint, and how does the number of required neurons/parameters would be affected. This question is of interest especially in scenarios where NNs are trained using weight decay or other regularisation.\n\n\nMinor:\nPages 23-28 contain the formatting instruction which are of minor interest...\nP.11 Sobolov\np.17 This proves the bound on the number of neutrons.", "summary_of_the_paper": "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.\n\nFor 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.\n\nFinally, 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}.\n\n[1] Hadrien Montanelli, Haizhao Yang, and Qiang Du. Deep ReLU networks overcome the curse of dimensionality for bandlimited functions", "summary_of_the_review": "This paper is well written, and provides good theoretical insights about the representation power of both shallow and deep neural networks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "0Ck5EGvQ50", "reviewer": "Reviewer_nqre", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n#### Strengths\n1. The paper gives matching upper bound and lower bound for the $X^{2, \\infty}$ space. \n\n#### Weakness\n1. The space seems far away from the practice of deep learning, and the contribution is mainly theoretical.\n    * The bound still has dependency on $(\\log \\epsilon^{-1})^{O(d)}$, which is still exponential. (Note that $\\log \\epsilon^{-1}$ is about the number of bits to represent a float point number with $\\epsilon$ accuracy.) This makes it less motivated to study this function space.\n    * The approximation issue is not the main concern in deep learning theory. Deep neural network merits not only because they are universal function approximators, but also, and more importantly, they can be efficiently trained and can generalize well. The optimization and generalization issues are the main concerns, for which this paper does not provide much insight.\n    * This paper looks tangential to the community of ICLR. Maybe this paper is more suitable to venues in applied math or numerical analysis?\n2. The technical novelty is rather limited, and the techniques looks to be rather limited to this specific problem of approximating Koborov space.\n    * The upper bound construction seems to be based on a simple interpolation argument. It is strange why the previous paper (Montanelli & Du, 2019) did not achieve this bound. Maybe the authors could highlight the main technical challenges?\n    * The techniques in this paper seem to be ad-hoc for the Korobov space and do not provide much insight for the \n3. The authors should remove Appendices E-K when finalizing their paper.", "summary_of_the_paper": "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. ", "summary_of_the_review": "\nBecause of concerns in the significance and technical novelty in this paper, I would recommend weak reject.\n\n**After Rebuttal:** Thank the authors again for a detailed reply. The authors have addressed my main concerns. I would like to raise my recommendation to weak accept and increase the correctness and novelty scores, and confidence. I suggest the authors to incorporate their answers, especially 1.(a) and 2.(a), in their next revision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors theoretically analyze the approximation of Korobov
functions by neural networks, obtaining upper and nearly matching
lower bounds, for shallow and deep networks, with different activation
functions.  The bounds are stronger than what can be proved for the
more commonly studied Sobolev functions.  But Korobov functions are a
natural and fairly wide class of functions.  This work makes a
substantial step forward in clarifying what kind of functions are
especially amenable to representation by neural networks.  The
reviewers also appreciated the clarity of the writing.
Decision: Accept (Poster)