Learnability of convolutional neural networks for infinite dimensional input via mixed and anisotropic smoothness
Authors: Sho Okumoto
Taiji Suzuki
Venue: ICLR 2022 Spotlight (2022)

Abstract: Among a wide range of success of deep learning, convolutional neural networks have been extensively utilized in several tasks such as speech recognition, image processing, and natural language processing, which require inputs with large dimensions.
Several studies have investigated function estimation capability of deep learning, but most of them have assumed that the dimensionality of the input is much smaller than the sample size. 
However, for typical data in applications such as those handled by the convolutional neural networks described above, 
the dimensionality of inputs is relatively high or even infinite. 
In this paper, we investigate the approximation and estimation errors of the (dilated) convolutional neural networks when the input is infinite dimensional. 
Although the approximation and estimation errors of neural networks are affected by the curse of dimensionality in the existing analyses for typical function spaces such as the \Holder and Besov spaces, we show that, by considering anisotropic smoothness, they can alleviate exponential dependency on the dimensionality but they only depend on the smoothness of the target functions. 
Our theoretical analysis supports the great practical success of convolutional networks.  
Furthermore, we show that the dilated convolution is advantageous when the smoothness of the target function has a sparse structure.

Published as a conference paper at ICLR 2022
LEARNABILITY OF CONVOLUTIONAL NEURAL NET- WORKS FOR INFINITE DIMENSIONAL INPUT VIA MIXED AND ANISOTROPIC SMOOTHNESS
Sho Okumoto*:,, Taiji Suzuki
Graduate School Information Science and Technology, the University of Tokyo PRIKEN Center for Advanced Intelligence Project
1ebessuee0 gm com, 'tai Mhaijime si@mist.... to.oooo.ac..j
ABSTRACT
Among wide range of success of deep learning, convolutional neural networks have been extensively utilized in several tasks such as speech recognition, im- age processing, and natural language processing, which require inputs with large dimensions. Several studies have investigated function estimation capability of deep learning, but most of them have assumed that the dimensionality of the input is much smaller than the sample size, However, for typical data in applications such as those handled by the convolutional neural networks described above, the dimensionality of inputs is relatively high or even infinite. In this paper, we in- vestigate the approximation and estimation errors of the (dilated) convolutional neural networks when the input is infinite dimensional. Although the approxima- tion and estimation errors of neural networks are affected by the curse of dimen- sionality in the existing analyses for typical function spaces such the Hölder and Besov spaces, we show that, by considering anisotropic smoothness, they can alleviate exponential dependency on the dimensionality but they only depend on the smoothness of the target functions. Our theoretical analysis supports the great practical success of convolutional networks. Furthermore, show that the di- lated convolution is advantageous when the smoothness of the target function has sparse structure.
INTRODUCTION
Deep learning has shown high performance several tasks such as image recognition, speech recog- nition, and natural language processing. In particular, convolutional neural networks (CNNs) and dilated CNNs have been quite effective in tasks involving high-dimensional data (van den Oord et al., 2016; He et al., 2016; Simonyan & Zisserman, 2015; Yoon, 2014). However, many aspects of its thcoretical nature are still unclear while related thcoretical studies have attracted much atten- tion. Aside from the analysis of CNNs, one of the most fundamental issues in deep learning theories its function approximation and estimation capabilities. For example, it is well known that any continuous function with compact support can be approximated with arbitrary accuracy by two- layer fully connected neural network (Cybenko, 1989; Hornik, 1991). Moreover, the representation ability of deep learning to approximate a function in some function classes such as Hölder classes has also been extensively analyzed (Mhaskar & Micchelli, 1992; Mhaskar, 1993; Chui et al., 1994; Mhaskar, 1996: Pinkus, 1999; Yarotsky, 2017: Petersen Voigtlaender, 2017). In addition to the approximation ability. the estimation ability of deep learning for estimating function by a finite sample has also been extensively studied. For example, Schmidt-HHe Hieber (2020) derived the estima- tion error bound of deep learning with ReLU activation (Nair & Hinton, 2010; Glorot et al., 201 1) to estimate functions in the Hölder space and showed the rate of convergence achieves the (near) min- imax optimal rate. Suzuki (2019) derived approximation and estimation error rates of deep learning with ReLU activation for the Besov spaces, which were also shown to be (near) minimax optimal. Although the derived rates of convergence sionality of inputs is fixed and much smaller than the sample size. Indeed, the derived rates suffer from the curse of dimensionality. However, in practice, often encounter settings where the input
near optimal, these studies assumed that the dimen-

---

Published as a conference paper at ICLR 2022
dimensionality is larger than the sample size even infinite. For example, in image recognition and natural language processing, the dimensionality of inputs (images or texts) is very large, and they could be seen as almost infinite dimensional.
To address this issue, some researches considered a setting where the dimensionality of the support of the data distribution is low dimensional. Chen al. (2019b;a) considered a setting where data can be embedded in a low dimensional sub-manifold and derived the approximation error of func- tions that depends merely on the dimensionality of the sub-manifoll instead of that of the entire space. Nakada & Imaizumi (2020) also considered a similar setting, and showed that the estimation error is characterized by the Minkowski dimension of the support of the data distribution. Suzuki (2019) showed that, even if the data cannot be embedded in low dimensional manifold, anisotropic smoothness of the target function can mitigate the curse of dimensionality. Although these studies revealed that deep learning can avoid curse of dimensionality by utilizing some low dimensional structures of data and the target functions, it still remains unclear how deep learning performs for very high dimensional settings including infinite dimensional setting. See Table for summa- rized comparison to existing studies.
In terms of infinite dimensional inputs, there have been already several studies on approximation and estimation errors for non-deep-learning methods. For example, so called hyperbolic cross approx- imation has been considered to approximate a function in a tensor product space with support on [0, 1 (Dūng& & Griebel, 2016) 6) and a polynomial order approximation is possible for functions with mixed smoothness, that is, specific summability properties of the smoothness indices fulfilled. Ingster& & Stepanova (2011) 1) analyzed a Gaussian white noise model with an infinite dimensional in- put and showed that the estimation accuracy for signals on infinite dimensional anisotropic Sobolev spaces depends on the reciprocal sum of the smoothness per axis (see also Ingster & Stepanova (2006); Ingster & Suslina (2007); Ingster & Stepanova (2009)). Oliva et al. (2013; 2015) proposed methods to estimate a map where the input and output are functions or distributions, and derive the rate of convergence. Ferraty et al. (2007) analyzed the Nadaraya- Watson estimator when the inputs are functions, derived the convergence rate of the estimator, and gave the asymptotic confidence band in the context of functional data analysis (see Ling & Vicu (2018) as a comprehensive survey of the nonlinear functional data analysis literature). However, these researches are not for the deep learning and the benefit of deep learning for such situation has not been well characterized in the literature.
In this study, we analyze the approximation and estimation accuracy in a setting where the input is infinite dimensional, and derive their convergence rates. We assume that the true function has mixed and anisotropic smoothness, that is, the function has different smoothness toward different coordinate similarly to Düng & Griebel (2016); Ingster & Stepanova (2011). The intuition behind this setting is as follows: Considering a function which takes an image as an input, an image can be decomposed into different frequency components and usually function of images has less sen- sitivity on the high frequency components and more dependent on the low frequency components, which can be formulated as non- non-uniform smoothness toward each coordinate direction. By consid- ering such setting, we can show that the rate of convergence can avoid the curse of dimensionality and be of polynomial order. Our contribution can be summarized as follows:
1. We consider a learning problem in which the target function to be approximated or estimated can take infinite dimensional input and has mixed or anisotropic smoothness. We show that deep learning by fully connected neural networks can achieve approximation and estimation targer
2. Weesddeeeneee deeeneeentterne g nnnattun of the S funstion and indensndeay of sparse se dimenaione
and then we show that dilated CNNs can find appropriate variables and improve the rate of These convergence. This indicates that CNNs can capture a long lange dependence among the input. show that even when the dimension d' of the datá IS very large compared the number of observations n. or even when the input is infinite dimensional, order estimation error bound that depends only on the smoothness of the function class. This analysis partially explains the great success of CNNs in various applications with high dimensional inputs.
is possible to derive a polynomial
2 PROBLEM SETTING AND NOTATIONS
In this section, we prepare the notations and introduce the problem setting. Throughout this pa- per, we use the following notations. Let Ryo := {s E R : > 0}, and for a set I, let D := (181.....8s..... E D) (for example, R := ((5)) : st R (Vi 1,2,...))) -))) For
2

---

Published as a conference paper at ICLR 2022
Table I: Comparison of this work and existing work theoretical analyses of deep learning for high
dimensional data. a = (a=);== is a smoothness parameter, ā := (2==1 9;
)--)),1-_ , U (1/p - 1/2)++
01 aa and D the dimensionality of low dimensional structure. anisotropic smooth (d < n)
Function class mixed smooth (d < n)
low-dim data
Author
Suzuki (2019)
Suzuki & Nitanda (2021)
Nakadu & Imaizumi (2020):
Schmidt: Hieher (2019) Chen et al. (2019b:a)
Rate
(n/ In/log(1) (n) (1)n))ddd"-) नf.
Function class
mixed smooth = oc)
anisotropic smooth (d 00)
Author
This work
This work
2181
2ta
Rate
2001 -0/4
2(a-))41
E R let supp(s) = {i E N: + 0J. Let NØ ELE (NU (0)) supp(!) < oo) and define Z and IR@ in the same way. Furthermore, for E TR let 2 == 2 s1 For L. E N. let [L] = (1...., L.. For a E IR, let [a] be the largest integer less than or equal to a.
2.1 REGRESSION PROBLEM WITH INFINITE DIMENSIONAL PREDICTOR
In this paper, we consider a regression problem where the predictor (input) is infinite dimensional. Let A be the uniform probability measure on ([0, 1]. ( 1))) where B[ 1)) is the Borel o-field
on [0, 1]. and let A be the product measure of À on ((0, 1 [0 )) where B(O0, 1) is the product o-algebra generated by the cylindric sets Ozga(z E 1 Ij E B₃} for d 1, 1.2.... and B₁ E [ 0 I]). Let Px be probability measure defined on the measurable space (10, 1100,,[[00,___________000 1] that is absolutely continuous to X and its Radon-Nikodyn derivative satisfies -xx= 1 ([)])_)) oo'. Then, suppose that there exists true function f [0, 1] R, and consider the following nonparametric regression problem with an infinite dimensional input:
Y (X) +
where X is a random variable taking its value on [0. 1| and obeys the distribution Px introduced above, and & is a observation noise generated from ((0, a²) (a normal distribution with mean 0 and variance x² > 0). Let P be the joint distribution of X and Y obeying the regression model.
What we investigate in the following is (i) how efficiently we can approximate the true function f by neural network, and (ii) how accurately deep learning can estimate the true function fo from observations D, (X,, y:) where 9:) are i.i.d. observations from the model. As a performance measure, we employ the mean squared error |lf f Ep((f(X) - (X))), which can be seen the excess risk of the predictive error (xx,))-r((((X) - Y) associated with the squared loss (i.e., [] fo = E(x,r)- - Y) 1 (xxx)))((((()) - Y)
E [(x(x)x[[(((X) Y) inf meeasurable
Y)
2.2 MIXED AND ANISOTROPIC SMOOTHNESS ON INFINITE DIMENSIONAL VARIABLES
Here, we introduce function class in which suppose the true function f is included. For a given
v2 (2x
(4 0),
1 E Z define vh, [0. 1] + IR as (
2 sin (2 (1x)
(4 > 0), for xr E [0, 1]. and
(4 = 0),
define (X) : II vr, (x;)) for X = (o E m0 Let ( 1 == {f: [f + fa.1a (2xx)) (x) < x) equipped with the inner product (f.g) = [. [(z)g( for f.g E (00 1) Then, (vi)uzzz forms a complete orthonormal system of ( 1 that
is, f E (20 1 can be expanded as f(X) = Σie (f. (X) (see Ingster & Stepanova (2011) for example). For E No. let 5.(s) : R + R be 8.()()=
Σ
LE25 12 1
'This is rather strong assumption. We can omit this if we take 0 = 1 and p for F However, don't pursue this direction in this study.
3

---

Published as a conference paper at ICLR 2022
which can be seen as the frequency component of f of frequency [4|] = 2 toward each coordinate.
We also define I| = (Jo. Iff'd>)) 1/p
for 2 1. Then, we define a function space with a
general smoothness configuration as follows.
Definition 1 (Function class with y-smoothness). For given 7 No + R2o which is monoton-
ically non-decreasing with respect to each coordinate. For 2 1, 0 2 1, we define the y-smooth space as
F. (1011100)
E 1E70
(J.iii ( Σ
10 1/0 <x0).
SEND
equipped with the norm |lf ||f (Eeeng 20m(()) (1.(()) 1/9
p.a). Remind that 6, represents the frequency component associated with the frequency (2*) and then the norm of the y-smooth space imposes weight 2*x(#) on each frequency component associated with s. In that sense, 7(s) controls the weight of each frequency component and accordingly function in the space can have different smoothness toward different coordinates. As special case of yss), we investigate the following ones in this paper. We can see that finite dimensional analysis can be easily reduced to a special case the infinite dimensional analysis (see Appendix A). In that sense, our analysis generalizes existing finite dimensional analyses.
In the following, Tho (10, 11 is abbreviated to Fy and its unit ball is denoted by U(F)
Definition 2 (Mixed smoothness and anisotropic smoothness). Given monotonically non- decreasing sequence a = (m:) RR we define the mixed smoothness as
(mixed smoothness)
((s) = (a, (a, s),
where (a. s) := Ei= 3. and define the anisotropic smoothness as (anisotropic smoothness)
7(s) = max(a,s; E N).
Each component a, of a = (a.) represents the smoothness of the function with respect to the variable z;. Since we assumed (a+) is monotonically non-decreasing, function in the space has higher smoothness toward the coordinate z; with higher index i. In other words, the function f in the space is less sensitive to the variable x; with larger index i. For example, in computer vision tasks, we may suppose 2; with a large index corresponds to a higher frequency component of the input image, and then the function is less sensitive such high frequency components and more sensitive to low-frequency "global" information. This can be seen as an infinite dimensional variant of the mixed smooth Besov space (Schmeisser, 1987: Sickel & Ullrich, 2009) and the anisotropic Besov space (Nikol skii, 1975; Vybiral, 2006; Triebel, 2011) 1) (see Appendix C for detailed discussions). In our theoretical analysis, we will assume that the true target function fo is included in the 7-smooth function space.
Assumption 3. The target function satisfies fo E UFF p.0) with p 2 1 and 2 1, and |l S By for a fixed constant B₁ > 0, where the smoothness 7 is either the mixed smoothness or the anisotropic smoothness.
3 RELATION TO EXISTING WORK
A function space with the mixed smoothness in finite dimensional setting be found in Schmeisser (1987); Sickel & Ullrich (2009), in which the mixed smooth Besov space is defined. The approximation and estimation errors of deep neural networks for the mixed smooth Besov space were analyzed by Suzuki (2019) for special setting of a = ... Odt, and an approximation error analysis for 0₁
ag was given by Montanelli & Du (2019) using sparse- garsee-rriddd technique. The mathematical properties of the anisotropic Besov space with finite dimensional input were ana- lyzed in Nikol's skii (1975): Vybiral (2006): Triebel (2011). The statistical analysis on the anisotropic Besov space can be dated back to Ibragimov & Khas' minskii (1984) and they derived the minimax
Note that, since the number of nonzero components of & Ng is finite, the summation always converges. For the reason, the maximum in the anisotropic smoothness is also attained by some finite index i.
4

---

Published as a conference paper at ICLR 2022
optimal rate for density estimation where the density is in anisotropic Besov space. Nyssbaum (1983; 1987) also analyzed a nonparametric regression problem on an anisotropic Besov space. The approximation and estimation error bounds by deep neural networks for composition functions in anisotropic Besove spaces and superiority of deep learning compared to the kernel methods are shown by Suzuki & Nitanda (2021). However, all of these studies are about finite dimensional input and it is far from trivial to generalize it to the infinite dimensional setting.
Our analysis for the 7-smooth function space closely related to Ingster & Stepanova (2011) 1) in which the anisotropic Sobolev space defined by F= W == {s E (2, 1| E
f āz," 1
оo is analyzed. They also derived a similar convergence rate to ours for non-deep learning estimator for a Gaussian white noise model. In the literature of the functional data analysis, the Nadaraya- Watson estimator for functional input has been extensively studied (Ferraty et al. (2007) and Ling & Vieu (2018) for comprehensive survey). If we apply the bound given the literature to our setting, the learning rate can be 1/poly- log(n) which is much slower than our analysis. This is because their analysis does not make use of y-smoothness. See Appendix C for more details.
Kohler & Langer (2020) analyzed CNNs in setting where the target function has hierarchical max-pooling structure each layer of which is sufficiently smooth. On the other hand, our y-smooth function class imposes smoothness more directly learning ability of CNNs with ResNet structure in a classification task where the data are distributed on ciw-dimeniional manifold and established a rate which only depends the dimensionality of the low dimensional manifold. However, the input should be distributed on a low dimensional manifold, while our analysis allows its support be infinite dimensional. Estimation errors low dimensional structure also have been studied in Yang & Dunson (2016); Bickel & Li (2007); (2019); Chen et al. (2019b).
the target function. Liu et al. (2021) analyzed
Nakada & Imaizumi (2020);
4 DEFINITION OF A DILATED CONVOLUTIONAL NEURAL NETWORK
In this section, we introduce the neural network model that we investigate in this paper. Let L E N be the depth of the network and dg (i I,..., L + 1) be the width of the i-th layer in the network where we set dL+11 = 1. Then, the fully connected neural network (FNN) can be given by (A + bL.) .... (Am(-) + b,) .... (AAæ + b1) where A, 1d b, E Rd and (ar)) = max (z. 0} is the ReLU activation function that is applied dlement-wise. The set of FNN with depth T. E N, maximum width W E N. norm bound > O, and sparsity level S E N is defined
by
(Ann()) (Am)) bb. o.... (Am()) + b.) o- (Aix bi) (L, -
I 11 + S S, max de S w
(=I..... 11 V lbblloo S B,
max
1=1
where ||- -loo the maximum absolute value among the elements of vector or matrix?, and || llo is the number of non-zero elements of a vector or matrix.
Next, we define the (dilated) CNNs. Let C N be the number of channels and CC { (#I.... size C E N and an interval h E N, then define the dilated convolution w * X' E R. for an infinite- sequence of vectors X' (
24 E RC.. Suppose that RCW'' is filter with width W E N, channel
C' as (w KG. X')² Din Σj=1 Wis= When h 1, it is called a normal convolution. Moreover, given a filter F E CB'''XxxW with (C")- multiple channel outputs, we define its corresponding convlution CONvA,F RCx0 + gC'''xo xoo as
Fi, *h X' :
CX')
For. Kn X'
Then, the dilated CNN can be defined as follows (its illustration can be found in Figure 1).
We define a V max(a,,b b} and b :== min(a, b) for a, b e R.
5

---

Published as a conference paper at ICLR 2022
Definition 4 (Dilated CNN). For given L', W E N. suppose that are given fil- ters Fi E 1BC--x0ixW' with the number of channels C₁ N (1 [L7] with B,S,, then a neural network given by f(X) = [FNN o wony .Far o Conv o .... ConvI,F, o xx), called a dilated CNN*, where gENN is assumed to be applied in an element-wise manner to the infinite sequence. The set of dilated CNNs with the same number of channels Cj = C² (2 S VI S L') in all layers but C1 = is denoted by
C = and an FNN JENN E
B', B',',",W', W C², L.W.S, = ( Conv 1.F o...o COnVI,F, o xx,;
R RERO'XO'WW (12 Fi FRE'IIX 11 B', ØENN (L,,W,
For simplicity, the set of dilated CNNs is abbreviated to P when there is no ambiguity about the parameter configuration. When L' 1, coincides with set of regular CNNs. In our anal- ysis, it is sufficient to consider an dilated CNN with a constant number of channels throughout all layers (Gr = C (VI E [T'])). To evaluate the estimation accuracy, it important to as- sume the functions in the set is bounded in terms of the Log -norm. For that purpose. sider an dilated CNN clipped by a bound B₁ > defined as P(B,, L', B', B', (f(X) - (-B, v (B, [(X))) :f E P(L', , B', W', L,W,W, B)}. Remark 5. In the definition of the dilated CNN, we do impose ReLU activation. However, since ReLU activation can realize linear function for a bounded input and thus our analysis can be straightforwardly applied even if there nonlinear ReLU activation. Moreover, this paper mainly focuses on ID ID-convouttion, but it can be generalized to 2D-convolution. See Appendix I for the detailed discussions in which it is shown that 7-smoothness over wavelet decomposition of an inpul image achieves the same rate of convergence as in ID-convolution.
APPROXIMATION AND ESTIMATION ERRORS OF DEEP LEARNING
In this section, we give our main result about the approximation and estimation errors of FNNs and dilated CNNs when the true function fo is in the 7-smooth function class.
5.1 APPROXIMATION ERROR ANALYSIS BY FULLY CONNECTED NEURAL NETWORKS
Here, we present the approximation error analysis of FNNs for a general smoothness Y not restricted to the mixed/anisotropic smoothness. For given T and the smoothness y No + R>o, define
T(T,7) == (i N: Fs E No;, 8 + 0, 7(8) < T)
and then the following quantities play an important role in our approximation error analysis. Definition 6 (Axial complexity and frequency direction complexity). The axial complexity is de- fined by dmax (T) 7) = [T(T, Moreover, the frequency direction complexity is defined by Fmax 7) eg +( max4eN 8t.
The axial complexity is used to evaluate how many components need to be extracted from a given infinite-dimensional sequence X E R achieve particular approximation error, and the fre- quency complexity characterizes up to which frequency we require to approximate a target function with particular error. Let
1 )
a(7) supseNe
E 7(3)
G(T, == EVENg (0)) 2",
where (x)) == max (a, 0}. Then, general approximation error theory for FNNs can be obtained as follows.
Theorem (Approximation error for the 7-smooth space by FNNs). Assume that Y, o : No - Rso satisfy
(s)s < 7(s), va(>) < 1, va(7') < 1,
'Here, employ h W for the k-th layer convolution. This structure is useful to show its feature extraction ability in Section 5.3.

---

Published as a conference paper at ICLR 2022
and the target function f Fp. (p 2 1, 0 2 1) to be approximated satisfies lifl By for
constant By E Ry For arbitrary T > O, we les tuple (dmax, J G) be
(dmaxs fmax G) = (dmaxx Smase (7), (7), G(T,)) (0maax(7))) fmase m (T)), ((T,))
(1 0 1 2),
(2 < 0):
and with some positive constants K, K' depending only By. we let
I 2K max (dlmax T2, (log G)², log Jmax),
W 21 21dmax G,
S = 1-1744Kdd L max {dlmsss T2, (log G)², log fmax) G,
B = (V2)d Amax K"
Then, there exists an FNN fr E $(L, S. B) with dinax dimensional input that takes (1I) E 1jmme as input such that I Ar ((I))SE)(I,)) for X = (m:) E [0, satisfies
10.
+
R given by (X) =
2 2-1 M1
(1 0 s 2),
f S 2-(1-
(ETSrC)) 20 200001111)))))) 1/2-1/0
(2 ().
According to this theorem, the derived approximation error can be achieved by FNNs if the required dmax components of the input X is extracted. This theorem clarifies how the decay rate of the frequency components of the target function affects the approximation accuracy. Since the approxi- mation accuracy is determined by (dmaxx fmax, G), it is not directly affected by the dimensionality but is characterized merely by the smoothness parameter y. Intuitively. T > 0 controls the approxi- mation accuracy and simultaneously controls up to which frequency is used for the approximation. Specifically, the difficulty of the approximation is determined by the number of bases required that characterized by the number of Ng with 7(s) < T, and the maximum frequency required for the approximation is also important for the analysis. The bound is proven by evaluating an approx- imation error of a trigonometric polynomial approximation of f E FF.e and showing that we can construct a neural network that approximates a trigonometric polynomial with certain accuracy.
5.2 SMOOTHNESS WITH POLYNOMIAL ORDER INCREASE
Here, derive concrete convergence rate for CNNs in setting where y is mixed or anisotropic smoothness and the smoothness parameter a = (a:) [o is polynomially increasing. In this setting, we just need use only one layer CNN. Deeper CNN layers will be used in the next section (Section 5.3) to perform adaptive feature extraction from wide range of inputs.
Assumption 8. There exists 0 < q < ao such that the smoothness parameter (a:) satisfies a, = 2(19). We also assume a1 < 02 for the mixed smoothness setting.
This assumption impose that the target function should be sufficiently smooth with respect to higher order indices. Under this setting, we show the approximation and estimation errors as follows. First, the approximation error by the CNNs can be evaluated as follows.
Theorem 9 ( (Approximation error bound under smoothness with polynomial order increase). Sup- pose that Assumptions 3 and 8 hold, then we have the following approximation error bounds:
1. Mixed smoothness (1(() = s)): Suppose that v/a1 <1 1. Then, for arbitrary T > 0, there exists a configuration of the network structure, T'' 1, B' = 1, W Tú, C'~ and
LTTT) maxx T [2) WT(
11 1 - 41
-(a-9))
T22
I
(I ~ (IE (1- 11-2 -mn--
T max {Tē, T2 ] T 2 BT) ~ (V2)r²,
such that there exists an dilated CNN f E P W', LI(T), (I)), satis- fying the following approximation error:
If'' f2 S (1=
2. Anisotropic smoothness (7(s) = max;(a;s:))
}): Let ā (Eiz a ---- and suppose 0 < à and v < ā, then there exists a network structure setting L' = 1, B' = 1. W WT,,', C ~ T and
La (T(T) max (r,,T2) T S2(T)~T max (Tt,T9]2719, (v22))
7

---

Published as a conference paper at ICLR 2022
such that there exists an dilated CNN f' P(L', W. C2,22 Wa()) B2(T)) satis- fying the following approximation error: || 2
The proof can be found in Appendix E. From this theorem, we can see that the number of layers, the width, the number of parameters, and the size of the parameters are both determined by T and the smoothness parameter a. Moreover, in Theorem 7, the approximation error was derived assuming that the appropriate index set T(T, 7) was provided. On the other hand, in Theorem 9, we do not make such an assumption because the CNNs can automatically extract the required index (TT.
Next, we consider the estimation error of these models in the regression problem (Eq. (I)). Suppose that we are given n observations D, = (x;, following the model (I). We consider the em- pirical risk minimization estimator (ERM estimator) in the model P that is given by any minimizer of the empirical risk:
1
f E argmin JEP
- y;)
i=1
As we have stated above, we employ the mean squared error f as performance measure.
Since ff depends on the training data Dn. we take expectation with respect to Dr: Ep=[llf s Ioll == - r Then, the following theorem holds.
Theorem 10 (Estimation enror under smoothness with polynomial order increase). Suppose that Assumptions 3 and hold, then we have the following estimation error bounds:
1. Mixed smoothness (r(s) (),s)): If v/a1 1, then by setting the network structure L' 1, B' 1, W (logn)s, C² (logn)s and (L, W, S, B) (Li (T), W (T))), ST))), (,(T),,((T)) for T 3(a1-of+1 log2(1) (n), the ERM estimator f in P(B,, Ll B', C", L, W, B) achieves 2(a)-v) 2(41-03+1 (log n) +2 max{(log n)+, (log ")
Ep - 191 f & IL - -(a--a1)
)-))
"
2. Anisotropic smoothness (7(5) = max; (ax:))) Under the same setting, if v < ā, by setting the network structure as L' 1, B' = 1, W" (logn)², O" (logn)² and (L, W. S, B) = (L2(T), W2(T), S2(T), B2(T)) for T 26-o)+I (ng,(n). the ERM estimator J in ( 12 B', C", I., W,S, B) achieves
Epm Ep- [II - -f aid oiT (logn) 2 +2 max (logn) n) (logn)*).
The proof can be found in Appendix F. This theorem shows that even if the dimension of the in- put data is infinite, for a function with particular smoothness, CNNs can achieve a dimension- independent convergence rate which is a polynomial order, that is, it can avoid the curse of dimen- sionality by utilizing the increasing smoothness. We can see that the derived convergence rate is a direct extension of finite dimensional one. Actually, if == 0, the rate for the anisotropic smoothness matches that of the finite dimensional one (Suzuki & Nitanda, 2021) up to poly-log order which is known minimax optimal. Therefore, CNNs can achieve the optimal rate up poly-log order at least when v = 0. As for the mixed smoothness, a finite dimensional version was analyzed (Suzuki, 2019) and similar rate was derived. However, analysis assumes d1 < a2 and a; 2(19) and thus obtained completely dimensionality independent bound while the bound by Suzuki (2019) depends on d in the exponent of the poly-log order.
5.3 SMOOTHNESS WITH SPARSITY
Next, we relax the assumption a; = 2(19) and consider a situation where there is kind of sparse structure in a. As we have seen in the previous section, under the assumption that the coordi- nates with large indices are not important, polynomial-order convergence rate depending only on the smoothness can be achieved by the ordinary CNNs. In this section, we show that similar rates can be achieved by using dilated CNNs even when does not satisfy the polynomial order increase if a has sparsity. For that purpose, we first define the sparsity of the smoothness.
Definition 11 (Weak fo-norm of smoothness). Given a = (a:) E RSS which is not necessarily monotonically increasing, consider the sorted sequence 0 dig S 0is S... in the ascending order. Then, define its weak (9 (9-norm for q 00 as ||a| Iut = sup, jaa,
8

---

Published as a conference paper at ICLR 2022
This kind of sparsity inducing norm were introduced and discussed previously in Donoho (1993); Donoho et al. (1996); Yang & Barron (1999) to quantify sparsity of coefficients of basis expansions. We notice that, if ||a||uto is small, almost all a,s very large and there only few indices that are small, which means sparseness. If the smoothness parameter a has a small weak (9-norm, then say that the functions with such smoothness has small number of important coordinate directions. Therefore, it is expected that we can approximate such a function efficiently by neural network. In this section, we analyze the approximation and estimation errors under the condition of sparse smoothness.
Assumption 12. a (a:);=1 satisfies ||alluts I for 0 < q < and a; S2(log i).
Note that this assumption relaxes the condition o, = ((19) in Assumption 8 to a, = 2(1og i)- Instead, imposes the sparsity ||a||ado I 1. Under this assumption, we obtain the following ap- proximation error bound.
Theorem 13 (Approximation error bound for sparse smoothness). Suppose that Assumptions 3 and 12 hold, then we have the following approximation error bounds for any T >> 1:
1. Mixed smoothness (7(s) (a, s)): Suppose that v/ais 1, then there exist a set of network structure parameters satisfying*
~ T, B' =1, ='=3, C2 T.,
such that there exists an dilated CNN f' E P(L' N., W,''""CCCCCWWWWWW..... (IT), Bi()) satis- fying - 1 S 2 -01-2,y1
2. Anisotropic smoothness (7(s) max; (axx((asi))) Suppose that O â and
then there
exist a set of network structure parameters satisfying L' ~ T. B' ~ 1, W = 3, C' ~ T such that there exists dilated CNN f' P(L,, B', W C, (T(), S2 B2(T)) satisfying Ilf 10 S (1--a/A
We can see that this approximation error bound gives the same bound as Theorem 9 under a re- laxed condition Assumption 12 with sparse smoothness. The only difference is the setting of the convolution part (L', W", C") and other parts are same as Theorem find the important indices that are relatively non-smooth compared with other indices. Thanks to the structure of dilated convolution, it can find such indices from a long range of index set: {i E N : = O(3*)) }} (see Figure for illustration of feature extraction by CNNs). Accordingly, we also have the following estimation error bound.
This difference required
Theorem 14 (Estimation еπто for sparse smoothness). Suppose that Assumptions 3 and 12 hold, W' 3, C' (logn)² and (L, W, S, B) as in Theorem
then by setting L' log n, B' the ERM estimator the class of dilated CNNs can achieve the same convergence rate of the estimation error as Theorem 10.
The proof can be found in Appendix G. These theorems show that for polynomially increasing smoothness, ordinary CNNs can perform optimal coordinate selection, while for sparse smoothness, dilated CNNs play an important role in coordinate selection. This theorem shows that, when extract- ing data with long-term dependence, convergence rates that avoid dependence on dimensionality can be achieved by using dilated CNNs.
CONCLUSION
In this study, we gave condition the smoothness of the function space as one of the situations in which the curse of dimensionality can be avoided when the input is ultra-high dimensional (n < d) infinite dimensional (d 20). This study showed that the smoothness of the target function plays an essential role in characterizing the estimation error bound. Especially, when the smoothness pa- rameter (a, ) grows up as the index increase, we can obtain polynomial order convergence rate even if the input is infinite dimensional. Future plans include, for example, considering situation where the smoothness depends on each input location, and extending the definition of F so that it captures more realistic situations.
p.o
'The choice W" 3 is not strict requirement. can be replaced by an arbitrary integer H with H
9

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENT
This study was partially supported by JSPS KAKENHI (18H03201), Japan Digital Design and JST CREST.
REFERENCES
Bickel and B. Li. Local polynomial regression on unknown manifolds. In Complex datasets and inverse problems, pp. 177-186, Institute of Mathematical Statistics, 2007.
M. Chen, H. Jiang, W. Liao, and T. Zhao. Nonparametric regression on low-dimensional manifolds using deep ReLU networks, arXiv e-prints, art. arXiv:1908.01844 Aug 2019a.
M. Chen, Jiang, W. Liao, and T. Zhao. Efficient approximation of deep ReLU networks for functions on low dimensional manifolds. In Advances in Neural Information Processing Systems, volume 32, pp. 8174-8184, 2019b.
C. Chui, X. Li, and H. Mhaskar. Neural networks for localized approximation. Mathematics of Computation, 63(208):607-66) 623, 1994.
G. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals, and Systems, 2(4):303-314, 1989.
I. Daubechies. Ten lectures on wavelets. Society for Industrial and Applied Mathematics, 1992.
D. L. Donoho. Unconditional bases are optimal bases for data compression and for statistical esti- mation. Applied and computational harmonic analysis, 1(1):100-115, 1993.
D. L. Donoho, M. Johnstone, G. Kerkyacharian, and D. Picard. Density estimation by wavelet thresholding. The Annals of Statistics, 24(2)5008-339 1996.
D. Düng and M. Griebel. Hyperbolic cross approximation in infinite dimensions. Journal of Com- plexity, 33:55-88, 2016.
D. Dung, V. Temlyakov, and T. Ullrich. Hyperbolic Cross Approximation. Springer International Publishing. 2018.
Ferraty, A. Mas, and P. Vieu. Nonparametric regression on functional data: inference and practical aspects. Australian & New Zealand Journal of Statistics, 49(3):267-286, 2007.
X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectifier neural networks. In Proceedings of the 14th International Conference on Artificial Intelligence and Staristics, volume 15 of Proceedings of Machine Learning Research, pp. 315-323, 2011.
S. Hayakawa and T. Suzuki. On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks, 123:343-361, 2020.
K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition, pp- 770-778, 2016.
K. Homik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2): 251-257, 1991.
I. Ibragimov and R. Khas' minskii. More on the estimation of distribution densities. Journal of Soviet Mathematics, 25(3):11555 11651165, 1984.
Y. Ingster and N. Stepanova. On estimation and detection of infinite-variable function. Journal of Mathematical Sciences, 139(())6548-6561, 2006.
Y. Ingster and N. Stepanova. Estimation and detection of functions from weighted tensor product spaces. Mathematical Methods of Statistics, 18:310-340, 2009.
Y. Ingster and N. Stepanova. Estimation and detection functions from anisotropic sobolev classes. Electronic Journal of Statisties, 5:484-506, 2011.
10

---

Published as a conference paper at ICLR 2022
Y. Ingster and I. Suslina. Estimation and detection of high-variable functions from sloan- wožniakowski space. Mathematical Methods of Statistics, 16:318-355 3,3, 2007.
M. Kohler and S. Langer. Statistical theory for image classification using deep convolutional neural networks with cross-entropy loss. arXiv preprint arXiv:2011.13600 2020.
N. Ling and P. Vieu, Nonparametric modelling for functional data: selected survey and tracks for future. Statistics, 52(4):934-949, 2018.
H. Liu, M. Chen, I. Zhao, and W. Liao. Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp.
PMLR, 2021.
P. Lizorkin and S. Nikol Nkii. Function spaces of mixed smoothness from the decomposition point of view. Proceedings of the Steklov Institute of Mathematics, 187:163-18, 1990.
H. N. Mhaskar. Neural networks for optimal approximation of smooth and analytic functions. Neural Computation, 8(1):164-177, 1996.
H. N. Mhaskar and A. Micchelli. Approximation by superposition sigmoidal and radial basis functions. Advances in Applied mathematics, 13(3):350-37,, 1992.
H. N. Mhaskar. Approximation properties of a multilayered feedforward artificial neural network. Advances in Computational Mathematics, (())661-80, 1993.
H. Montanelli and Q. Du. New error bounds for deep relu networks using sparse grids. SIAM Journal on Mathematics of Data Science, 1(1):78-92, 2019.
V. Nair and G. E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceed- ings of the 27th International Conference on Machine Learning, pp. 807-814, 2010.
R. Nakada and M. Imaizumi. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. Journal Machine Learning Research, 21(174):1-38, 2020.
R. Nessel and G. Wilmes. Nikolskii-type inequalities for trigonometric polynomials and entire functions of exponential type. Journal of the Australian Mathematical Society, 25(1):7-18, 1978.
S. M. Nikol skii. Approximation of functions of several variables and imbedding theorems, volume 205. Springer-Verlag Berlin Heidelberg, 1975.
M. Nyssbaum. Optimal filtration of a function of many variables white gaussian noise. Problems of Information Transmission, 19:23-29, 1983.
M. Nyssbaum. Nonparametric estimation of a regression function that smooth in domain in R* Theory of Probability & Its Applications, (1(1):088111) 1987.
J. Oliva, B. Póczos, and J. Schneider. Distribution distribution regression. In Proceedings of the International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 1049- 2013.
Oliva, W. Neiswanger, Póezos, E. Xing, H. Trac, S. Ho, and Schneider. Fast function to function regression. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pp. 717- 725, 2015.
D. Perekrestenko, P. Grohs, D. Elbrächter, and H. Bölcskei. The universal approximation power of finite-width deep ReLU networks. CoRR, haw/18866.1122, 2018.
P. Petersen and F. Voigtlaender. Optimal approximation of piecewise smooth functions using deep ReLU neural networks. arXiv preprint 4709 2017.
A. Pinkus. Approximation theory of the mlp model neural networks. Acta Numerica, 8:143-195, 1999.
11

---

Published as a conference paper at ICLR 2022
H.-J. Schmeisser. An unconditional basis in periodic spaces with dominating mixed smoothness properties. Analysis Mathematica, 13(2):153-168, 1987.
J. Schmidt-Hieber. Deep ReLU network approximation of functions on manifold. arXiv preprint UrXiv:/908.000 2019.
Schmidt-Hiehees Nonparametrie regression using deep neural networks with ReLU activation function. The Annals of Statistics, 48(4):1875-1897, 2020.
W. Sickel and T. Ullrich. Tensor products of Sobolev-Besov spaces and applications approxima- tion from the hyperbolic cross. Journal of Approximation Theory, 161(2):748-786) 2009.
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recogni- tion. In International Conference on Learning Representations, 2015.
Suzuki. Adaptivity of deep ReLU network for learning Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representa- lions, 2019.
T. Suzuki and A. Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. In Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021. to appear.
V. Temlyakov. Approximation of functions with bounded mixed difference by trigonometric poly- nomials, and the widths of some classes of functions. Mathematics of the USSR-Izvestiya, 20(1): 173-187, 1983.
H. Triebel. Entropy numbers in function spaces with mixed integrability. Revista matemática com- plutense, 24(1):169-188) 2011.
A. van den Oord, S. Dieleman, H. Zen, K. Simonyan, O. Vinyals, A. Graves, N. Kalchbrenner, A. W. Senior, and K. Kavukcuoglu. Wavenet: A generative model for raw audio. CoRR, abs/1609.03499 2016.
A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes: With Applica- tions to Statisties. Springer, New York, 1996.
Vybiral. Function spaces with dominating mixed smoothness. Dissertationes Math. (Rozprawy Mat.), 436:3-73, 2006.
S. Yanchenko. Approximation of the Nikol'skii skii-Beoov functional classes by entire functions of special form. Carpathian Mathematical Publications, 12(1):148 -56,, 2020.
Y. Yang and A. Barron. anformation-theorriie determination of minimax rates of convergence. The Annals of Statistics, 2765):1564-1599 1999.
Y. Yang and B. Dunson. Bayesian manifold regression. The Annals of Statistics, 44(2):876-905. 2016.
D. Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Nenworks, 94: 103-114, 2017.
K. Yoon. Convolutional neural networks for sentence classification. In Proceedings of the Confer- ence on Empirical Methods in Natural Language Processing, pp. 1746-1751, 2014.
12

---

Published as a conference paper at ICLR 2022
Appendix
NOTATION LISTS
Table 2: Notation list
notation
definition
n
sample size
(X,, Vb)
i-th observation (X;: input, yı! output) training data
Dn (Xi,
fo
the true function
-a;))
smoothness with respect to each coordinate
(s))
frequency with respect each coordinate trigonometric orthonormal basis functions
(X) =
I 14, (1:))
6,0)
basis function expansion of f for E zg such that [2 s 14 <
2
11:122
L2-norm with respect to the uniform distribution (lfll2 ==
111lex
I2-norm with respect to Px (lfllrx (Rxx)(((X))))
F [0, )
7-smooth function class
7(8)
penalty on each frequency component mixed smoothness anisotropic smoothness
7(8) (a,s)
7(8) max max(a,8;iiEN)
ReLU activation function
(,,,
set fully connected networks with depth L, width W, sparsity level S, norm bound B set of dilated CNNs with depth L', filter width W channel size C" accompanied with FNN in (L, W,S, B)
P(L', B', W. C,W,W,
I(T,7)
the set of features contributing frequency component s with 7(s) T [I(T, r)]: axial complexity
dmax (T, 7)
fmax(2 (T,7)
max 7()ST maxieN s; frequency direction complexity
( -
a(>) (TT,))
- SuPsENS 7(5)
EvEN:: 77s)<TT 2
A CONNECTION TO FINITE DIMENSIONAL INPUT SETTING
We easily that the analysis in paper can be directly applied setting where the input is finite dimensional (say, d-dimensional). Let
Ja = {s E No s; = 0 (i d 1....)}
and suppose that (ss) : No0 - R>o foo} satisfies 7ss) oo (s E Ja) and r(s) (s $ Ja). If we set
F (1.. = {1- f= Σ ( Σ 207(0) (8.())11)) <0,, 0 & Ja)
1/0
1E7
sEJa
then by the condition 6,(f) = 0 (4s & Ja). f E Fr (10, 1) is independent of (z+ (z;)iza:
[(I Wd, 34+1 .., , "y,... = [(11, . F - ..411....... ,/...),,
for any (2:) E [0, 10 and of E [0.1] (i = d + 1, 22 2...... Then, for E F...a 1)0) we may define
fa(xi,...xxa) f(a,,... F,, O,...),
13

---

Published as a conference paper at ICLR 2022
and it holds that f fl fall2- Hence, by the same argument the proof of Theorem 7, we have the same bound for F
p.8.a ( (0,11 )) Thus, the same statement as Theorem 7 holds for the y-smooth functions on [0, 1j This shows that the difficulty of the approximation depends only on the smoothness (ss) and independent of the dimensionality d. In particular, we can establish the bound even for >
B ANALYSIS OF ESTIMATION ERROR BY CONVOLUTIONAL NEURAL NETWORK
In this section, we discuss approximation and estimation errors by CNNs and dilated CNNs. In Theorem 7, we considered approximating function in F by FNNs. According to the analysis, the index required to achieve the derived approximation error bound is determined by T(T, 7). and only the coordinates corresponding to the index set [[T, ?) in X should be taken as input. However, in practice, it is not given which index is required as input, and it should be estimated from the data. In this section, we show that, under certain conditions, is possible to find the required indices from the data by using CNN and dilated CNN type architectures. We also show that these architectures can achieve a favorable approximation and estimation errors for functions mixed and anisotropic smooth spaces that depends the smoothness of the function classes.
C RELATIONSHIP TO EXISTING FUNCTION SPACES
In this section, we discuss the relationship between the space p.9. its finite dimensional counter -art and some related function classes
C.I MIXED SMOOTHNESS
First, we introduce a finite dimensional counter part of or function space with mixed smoothness (Schmeisser, 1987; Sickel & Ullrich, 2009), where the domain of the input is [0, 1] Definition 15 (Mixed smooth modulus of smoothness). For E N and R3o let
( () + jh)
(x E [0, + rh [0,
(otherwise),
be the r-th order discrete differentiation for function f 10 TR. By applying this discrete differential operator to each coordinate of a subset C (1,..., ,d], the mixed discrete differential operator for a step length h E I& and the order parameter No is defined
A = Ah; (flar..................
()) =
A LEEE
(f),
for x E 13a Then, the modulus of mixed smoothness is defined by w W., == sup
(f)
fort E R& and 1 S p. where || is the Ly norm with respect the Lebesgue measure on [0, 1]
Then, based on this modulus mixed smoothness, we can define the mixed smooth Besov space as follows.
Definition 16 (Mixed smooth Besov space), Let S. S s0. For a given smoothness parameter E R& let r; = [a,1 + (2 [d] and define the seminorm | IM as
{ (Jnetann [[Ilico (7 w. (f,t)² supiejo,aa (IIsee t, () w (
1/4
de I.ee. to
(1 S q < o0),
MlMBaS
(g = 20).
Then define the norm of the mixed smooth Besov space
[f = 11 +
E oC (C.....)))
14

---

Published as a conference paper at ICLR 2022
that the mixed smooth Besov space is given by M M. [[9) Il Bl <c)..
If [²(
The mixed smooth Besov space defined above can be seen as the finite dimensional counter part of our space with mixed smoothness y.. Here, for E N let
6,(5)=
Σ
12 JEL <2%
where th : [0, 1] is defined in the same way as in the infinite dimensional setting and f
T,2(10, 1) Then, it is known that
1/9
Ee GENG
fIMBE
holds for < < (see Section 3.3 of Dung al. (2018), Yanchenko (2020); Lizorkin & Nikol'skii (1990) and references therein). Therefore, the mixed frequency space can be viewed an extension of the finitediimeniional mixed smooth Besov space the infinite dimensional one. Approximation and estimation abilities of deep learning with ReLU activation for the true function the fnite-dimensional mixed smooth Besov space was investigated by Suzuki (2019) Ogg They showed that deep learning can achieve the (near) minimax optimal rate this setting and the mixed smoothness alleviates the curse of dimensionality.
when
C.2 ANISOTROPIC SMOOTHNESS
Ingster Stepanova (2006) considered general function class representated by
Fe = f E ((0
Σ (f. < oo LEZS
for a given sequence e = (a)) with E R. This class includes our 7-smooth space with p
0 2. In particular, Ingster Stepanova (2011) 1) analyzed an estimation problem when (ci)tezg is given by
& =
Σ 1=1
(2m 20;
for monotonically increasing sequence a = )a:); = RS It can be shown that, in this setting, Fo is specifically given by the following anisotropic Soboley classe:
{ $ f L2
Σ
ga: d
F. = W =
This characterization highlights the intuition of the anisotropic smoothness, i.e., we assume the functions ʃ F. have different smoothness (a,) with respect to each coordinate Hi. Here, by noticing that ( 11 (J, o1) we have that
|| 1lvg
Σ 12
2
Σ
Σ
&f. v))
SEN
i0 24 S14/<2%
Σ N
max iEN
(2m22 11)2a)
Σ
(f.41)²
122 1011/<2
Σ
2 max 10 1000
Σ
(f,
1E2g 22 1414/<2
Σ
2 max(a:s:) 1000
[f 11..1
SEN
15

---

Published as a conference paper at ICLR 2022
for (ss) max; fa,s:) Therefore, we see that the unit ball of the anisotropic Sobolev space Wi included in the unit ball of F222- Hence, our bounds in the following also give bounds for the anisotropic Sobolev space.
Suzuki & Nitanda (2021) also analyzed approximation and estimation error bounds of deep learning with the ReLU activation for the anisotropic Besov spaces defined finite dimensional space [0, 1] (Nikol' skii,, 1975; Vybiral, 2006; Triebel, 2011).
D PROOF OF THEOREM
We can see that dg can be decomposed as
(z)
E 2 21 <2.
e* exp(2tTi(kxx))
for C₁ C and the imaginary number i. Thus, when 1 $ p 2, from Theorem of Nessel & Wilmes (1978), we have that
(1,(1))2 S 16
where v = ( - })++ and n 2" E s. Furthermore, for < p. from the Cauchy- Sehhh- inequality, we obtain
[|0(2f)12 = J1.11= dd
2/8 (MAN 1d
1-2/p
(1 VOL
8.(1)Pax
Therefore, Eq. (4) holds all over the range of 1 S p < oo.
To show the approximation error in the assertion of the theorem, consider approximating f by Rf( defined as
RT) - Eeero (.()) (1 (1<0<2),
( 5.(f) (e()))))))
(2< 6).
Then, further approximate (f( by fully connected neural network. For that purpose, first
analyze the approximation error ||ʃ Rr(lll by Ry(f). This can be evaluated in the following lemma.
Lemma 17. Under the same setting Theorem 7, we have that
{ 2 (1
(1 5 0 < 2),
(r-Rl(f S 2- [TSY() 2 (1 1-2/9
(0 2).
Proof. We show the inequality for the settings 1 15 and separately.
1. Approximation error || (f)ll) by Rf( for 1 1 < 2: Using the orthogonality of 6, between different have
|| -- (IlS R (1)
8/2
Σ
18,2
(5)
Σ
(2 (.(()))p)) (1/0/211)
SEN TT)(s)
Σ
(T((s)
16

---

Published as a conference paper at ICLR 2022
where Eq. (4) is used to show Eq. (5). Then, for N6 with T (s). using the assumption E. I vo(()) < 1, we have that v 7(8)
2"5 v 2 < 2(va-1)
Then, applying this inequality to Eq. (6), we obtain
Σ TSn(s)
(2
(2 $2 $2-
20001 Σ
(216))166())11b)
TST(s)
2 0(1=a |1
2. Approximation error |f - Rr(f)ll2 by Rı for 2 < A:
Using again the orthogonality of 6, (f) between different s, we obtain
|lf RT(f)l
Σ (S)
(
and
Σ TSY())
10,00)13
Σ (2 (0.(0pp)p
T5)((s)
Σ
(s)
Then, using the assumption va' < 1 for a' = a(r'), we obtain 20 S 2(va' S
2(va' Applying this inequality to Eq. (7), we obtain
Σ TS+(())
(+) 16.(f)lp)
2 2-22(1- 20122111)))
Σ
(0) (16.(f))p))
(S+(s)
Then, by using Cauchy-Seue Sehchr- inequality, we obtain
2 2-2(1- 2(1-va Σ
(2)(0))0))))( (101)<(()22(01166(0])]) (6,(())l,))
TS+((a)
2/0
(1-2/0)
Σ (2)))0->(0) 2/(1 2/(1-2/0)
2 221-(1vv '
(276))16)(1)11))
(S+((s)
TSY(()
1-2/0
< 2 22-2(1-va') 21-1'
2 (76)
11f113 33.0"
TSY(ss
Next, consider approximating Rr by a neural network. We show it only for S. 0 S 2, but the same argument be applied for 2 0. Theorem 4.1 in Perekrestenko al. (2018) asserts that there exist constants C1, C2 > 0 such that, for
1 T===C Ci ==((1103]
1)² + log (Smax)
=a=
there exists neural network J. Φ(L3. 21, C2. 21 that can approximate v/,
11,., 8. 11== S.
17

---

Published as a conference paper at ICLR 2022
Moreover, since 1/ E 12 v2],
faxx--v2. min v2, }} -111l11.((0.. Sc.
Since, we can write
max min| [v2,z=]] (((x) - 71 v2) (--)(-x) + +n(=x v2)
for E IR, it holds that max m/n }1 ( +2 21, max(C2, v2), 21 (L + 2)).
(2,44, v2, and then
that
By using these facts, we can construct the neural network that takes value in [-v2, v2]. In the following, let
Vr. max{ min Lg = Ci ((100s ")²
log (Fmax) + 2.
Since we need to approximate trigonometric polynomial, we need (approximately) realize mul- tiplications by neural networks. By Proposition 3 of Yarotsky (2017), using
3dmax
Lx
log
+5)
Dog dmaax
Wx = -ddmax Sx = T.x W
and constant Bx O, there exists neural network ox (L Wx, Bx, Sx) that satisfies
dinace
Zz
Se
i=1
(1 1,11
Since di, S 2 is satisfied, we know that
w Vimaa
diace
Φx
Se
V2
2
V2
L ([0,1]=))
Dramas V2
dmax
(V2)dmox
dmnx Φx
4
11,
122
mmax
E.
(9)
2
(00110))
Here, note that Eq. (8) yields that
dmax
dmnx
II
1/.
(
dinax
Danac
danii
th
j=0
ビ=ナ+2
((0.))))
dmace
dmaa
(Weyer - wlst.)
jm0
iml
j+
([0,1]p
dmaae
2
dmax
p
I
1/ (10.))))))
< 2
Amax
dmaxe.
Then, by using triangle inequality and Eq. (9), we know that
denaxe
(v2) Jmna Ox
thu
V2"
i=1
((01)0)))
S Vllamax 2
demxx
dmax
( dimax txx
II
1/.
2
x
(V Manax (druxx 1)c.
18

---

Published as a conference paper at ICLR 2022
Therefore, if we set
Vi V2'....
Vildmax
RI(f)== Σ Σ (v2) dmaa (f. vi)ox
v2
(()()
where J(s) = (1 E 20
12a & |4,1 < 2 }. we obtain that
Rr RT 1.- (1-1,))
Σ
(V2)duox (f.t)) Øx
Le
1
/2
V2
22
v2
mmxx
SENO (7()) <T (EJ(s)
100 (1
1,1]dmax
s BTG (22 (dmax + 1)c,
where used the fact (f, vh) |lfll2 By in the last inequality. Hence, if we put
2-1 (v2)dmas dmas Byldmax + 1))(T,7))
(10)
then we have that
Ilf Rrll $ ff - Rrll + [| Rr-le= -(111=
$ (2- +((T)111/1
2 (1-vayT
(150 2),
where Q(T) = 2- YT
2 2 (1 1-2/0
Noting that
(0 2).
2 2-T & Q(T), we have that || RTll Q(T)
PM
Finally, we evaluate the network size to achieve this approximation error. Since Ry is the linear combination of neural network Φx
by putting
L L3 + Lx +1,
W 21dmax G(T,
S (21 + Lx W + 1)G(T,
B = max((v22)dmm By, Bx C2),
we have that Rr E (L,, W,S, B). Substituting Eq. (10) to Lx and Lgg we can evaluate as
1 !) + log(fmax) +2
L C₁
log
C1 (Tlogg 2 + dmax log v2 + log S(y, T) + log By loog dmax + 1) log fiax
Ca (6 max B,, log 21) [ (maxfffa T2, (log S(y, ()) .log fmax: 21)
and
Jdmmxx
Lx
log
+5
[og d
3dmaxx
log 5 + log 2 ] [lg d
max
log
M max (log By, log 5)7 Imax (dmux:
T, log G(T, 7)], [lg dmax]
Therefore, if we set K max [6 (log B,, log 531, it holds that
C1 max (log By log 21)² }. then
< 2K max (chaxx T2, (log G(T, log fmax)
19

---

Published as a conference paper at ICLR 2022
and thus we also have
s (21x L + L 1))
s 2K + 36d max { {dmax: , (log G(T, 7))² log fmax) G(T,T)
s 4 x Kdd max max de T (log G(T, ?))², log f n).
For the setting of < 0, we can prove the bound by the same procedure. Thus, we obtain the assertion.
E PROOF OF THEOREM 9
Before we prove Theorem 9, we show the following lemma. The following lemma is inspired by Lemma 1.2 of Temlyakov (1983).
Lemma 18. Suppose that (a:) and a' (a/))= are positive monotonically non-decreasing
sequences such that S 01 = 0f and
II
< 00,
2-2-- Ble < OC,
2 (a, 01]
2=
for a positive constant 3 > O. Then we have the following inequalities:
Σ
2 ((,,))
< (1
21-2299)-
II 1=
2-2T ST
2
(21)
2 Blas ag)
NENT :0' 2T
and
20
Σ
2 58
2T.
(22)
2 (a:
s <<
Proof. First, note that
Σ
2 8(,,))
SEN :(a
2T
Σ 2 881
Σ
2- 2: 4:8;
x
=1=0
(o1) EN:: E d/222
Σ
2 8 2:30
Σ
- 8s1
2
(23)
(0)) ENT E. <
IfT satisfies Li d/8; < T. then we have that
2-3T Dee disc
Σ
Bsi
2- 3
EN (0) Eie a/5;
Thus, the second term of the right hand side of Eq. (23) can be evaluated
2 ST (1 9-1
Σ
(M)) EN d.sT
Next, we evaluate the first term of the right hand side of Eq. (23). We see that
2 B8l (1 -1-27 -1
81 0
20

---

Published as a conference paper at ICLR 2022
and
Σ
2- -i 415
(0 C Diz
2- 2i- (0:00020-) -E
( E Et d/22
$2-97 ST
E
2 2 --
2 2i 4/422
Thus the first term of the right hand side of Eq. (23) can be bounded by
2 2- 97
2-
Σ
2- (2
(o:) ENJ 2122d/22
Hence, by noticing that
Σ 2-
II
2 B(ar-a))s
2 B(a, a.)
i=2
===0
and combining the evaluations above, Eq. (23) yields that
8
Σ
2- 2 6T (1 2
21-
2 0(a, 2- -0.
.END :/a 22
which yields the first inequality.
Next, show the second inequality. We decompose defined as
2T EveN <T 2 as Σt Io where I is
Σ
2
seNg st (s(a,)
Here, for $1ST T, we can evaluate I as
4
2
Σ
22 2(((a))
EN a (s
< 222
Σ
2
12a.
SEN Ig
Since 2 1, we have 0j - 2a; - (i 2 1) and thus by Eq. (21) with aj = aı (Vi N) N) and 8 = 1, have
Σ
2 E (2a: <
Σ
2 (0,))
Σ
2 (a,,)
sENg :t- (S(''s))
00
< 4
2
2 (a. -1
1=2
where we used the first assertion (21) in the last inequality. Therefore, can obtain
I 2
Σ
2 1 (2a;-1)8; <
II
1
2
(a
a1)
+EN (c,
1=
Now using this bound, we can verify that
Σ
2 58
8
1
T Σ 2
2
(1)
SEÑ: <T
i=2
1=0
20
1
<
2
2
01
1=
which yields the second assertion (22).
21

---

Published as a conference paper at ICLR 2022
Now, ready show Theorem 9. First, give the proof in the setting of 7(s) (a, s).
Proof for mixed smoothness (7(() = {a, 8)). 18 yields
First, we consider the setting 1 < < 2. Lemma
G(T,n)=
Σ
2
Σ
2
I
8
2
7
(24)
(0,
*ENg 1 an
I
2
"1
01
Moreover, we can easily see that
-i=l
1
a sup SEN
(a, s) a1
because a is positive monotonically non-decreasing sequence. By the assumption = S2(19),
dmax
T1// Smax T T
satisfied. Now, by using the filter E Cxxxww with the width W dmax the number of output channels C' dmax and the number of input channels C" = 1 given by
= {
(i = j),
Wi
(i + j),
for i E [dmax]] we can see that
31
(Convi,,o =
Ddmax
By Theorem if we set
L 2K max
Tá _22
1
W 21
2
-an
i=2
1 -
41
T max {Tē, T2
(2,,re227 2
S 1764K
111- 21
2
(V2) dmaa K'
where K, K' > 0 are constants, for any function e U(F(a.))), there exists a neural network p.0
Ri E (L, W, B) such that
F(X) = (r, Rdmax)
satisfies
11f' -fll2 < 22-(1-=1)
Since f(() (Rr o Conv ww (x)) we can see that 8 is a dilated CNN: f e P(L, B', W", C, B, where
1, B' and W = = dmax-
Next, consider the setting 2 < 0. Let ai 21 and for 8 02
(which is positive by the we set de for 1. Then,
assumption d2 > a1) and constant u that satisfies 2 < u < 2 26 at
al < a/2 < ... is satisfied, that is, (a() a positive monotonically increasing sequence. Moreover, by the assumption a; 2(19), it holds that, for all c > 0.
30
II
< 00.
(25)
2
41
22

---

Published as a conference paper at ICLR 2022
By noticing that -(a]-
( 1) ai S
oi where we used u > 2, we also have that
01
Σ
20-2 (a' aa,=)
E
2 0-2 (0/a1,5)
.ENG" (2)
E (2a' 222
Moreover, since we have verified Eq. (25), we can apply Lemma 18 the right hand side of this inequality and it can be further bounded as
Σ
2 2 (a/a1s))
22 T
6 (2a ()
that if define the set of CNN P by the same argument as the case of 1 S 0 < 2, for all f E UF p,9), there exists dilated CNN f' E P such that
By setting 7((s) (a', and using Theorem 7,
If flle 2 (1-vo(1')) (2 1/22//11110 =2 2(1 2(1-2))7
satisfied, where we used a<>') =
2. by the definition of a'. Here, as in Eq. (24), we have that
G( 58
II
1
2
I
1
2
i=2
2
Therefore, by resetting T < 2T, we obtain the same result as in S 0 $ 2.
Proof for anisotropic smoothness (7(s) = max/ max/fa;s; (a.s:)o) Here, we consider the setting of mixed smoothness ((s) max;(a;si); We note that
Σ 8i sup, sup, (a:s;}
Σ 8 sup, {a,s:}
a<>) sup .
S sup SERS,
2i=1 8;
00
sup T>U omaa, [a:8:)=T}
sup
T
The condition sup,(a;s:) < T is equivalent to the condition that 8; I T. for all i E N, the right hand side can be further bounded as
a(>) <
Therefore, in the setting of < S 2, Theorem 7 with a Di a2
yields that
(f) fll2 s 2- 2-1--aa) (2-00-600(11
Since holds that
Σ
2 < i=1
Σ 8,=0
2%
R EE
EEN
<T
G(T,)) < 22 satisfied. By noticing that is positive monotonically increasing sequence with polynomial order growth, the same argument as in the setting of 7(s) = (a, s) can be applied. Then, obtain the assertion.
F PROOF OF THEOREM 10
The estimation enror can be derived by evaluating the bias and variance trade-off. The bias can be evaluated by the approximation error which has been analyzed in the previous sections, and the variance can be characterized by the complexity of the model. As a measure of complexity of the model, we utilize the covering number of the model (van der Vaart & Wellner, 1996).
23

---

Published as a conference paper at ICLR 2022
Definition 19 (Covering number). For norm space F equipped with norm || ||. the e-covering number (F,,,, e, Il) the minimum number of balls with radius e (measured by the norm to cover the norm space F:
NFF 6, l| I)) == inf E N: :
F", VFEF, [ II
fll S <).
The covering number of the model of the dilated CNNs can be evaluated in the following lemma. Lemma 20. The log-covering number of the set of the dilated CNNs P(L', B', ,','', L, L,W,B,B. B, can be bounded as
log (og,(P,88))) 8, -1b0) (5+ LL' V (ILBBVI[[VV)CCW)
8
Proof. The assertion can be shown by evaluating how strongly small perturbation of parameters can deviate the function. For w RC¹ xw" and h E N, we have that
||w *4 X w' */2 X 00 I (I( w') * |l I W'Cllw w' woloololl |o
|| *4 X *h X'Il 0c I W' W'C'|| ["llw]loo IX Xolooo
Therefore, for F, F' E RC''""Xxx"" xW" we have
|Convv,F X Conva, X 1000
max sE(C"]
(F *h X) - (Ff *h X
W'C'
max iE|C")
| Fr..!lloo) ||
W'C
F'Il |
(26)
[[Convs, X Conva,
X
max ,E(C")
[.B.,.. X) - (Pin.: X'II
W'C"
max 11 ||X -X'lxx (E(C")
W' X'
(27)
Here, for CNNs f. such that
f(X) Convwa/.F, .Fz, .... Convw" ..... COnvI,E, X,
s(X) Conv .rz. .... Conv Convi,E X,
we define
Ax))(x)= Conv -1 .... Convi, o X, (X') Convw.' Fr Conv FL.,, o X',
where (x)) = By (X) = X. By using these notation and the triangle inequality, we can that it holds that
lx g( |lx
Σ (B(g)) Convwa, A(()(X) -Bi(g) Conv FF (x))
Hence, by applying the inequalities (27) and (26), we can see that
1 - (oX))ggX\1lee S LL((C 1x
max 114
max s L''WW'''
Fi Filloo
I....!
Now, for fENN L(L, W, S), we have
[x)NN(*) SFNN(x') (BW) -or--all 2211
24

---

Published as a conference paper at ICLR 2022
and thus we also have
INNNN o S(X) - fINN o xx S L'(BW)
max I=I...
||
Filloo.
On the other hands, JENN: (T, W, B) be represented
fFNN(x) (ALn(-) + br) 0 ..... (Am ) + bi) o...........................oo ....... (Aix + b1), JENN (x) (A'in(-) + br) o...o (Afm(-) bl) ........ (A1x + bj).
Then, by noticing that [x( I (W''))', the same argument Lemma 3 of Suzuki (2019)
yields that,
max max {1IAr Ailloo, 1bb bílloo3 s 6, l=I....
(28)
then the Loo distance between the composite functions JENN g and gENN g be bounded
[FNN g(X) - gENN (X)]l S SLL(WC))) [(B 1)(W+1))
+ 1)3
Since the triangle inequality yields
[[)N og(()) FNNo) & (ENNN//())-FNNG((()))1111VXV -NN' -
by combining these inequalities, under the condition (28) and max F - Filloc S 5, we obtain
I - PNN
s (W''B") +8L(W'C') ((B 1)(++11))
Therefore, by noticing that the number of combinations of non-zero parameter configurations in L(L. W, S) bounded by (W r.5 we can again utilize the same argument as Lemma 3 of Suzuki (2019) to we obtain
LL'(B' 1)BV W(W
log Ng,N(P,,.11 (P (8++))++++)
Using a covering number bound a model, a standard analysis of the ERM estimator gives the following bound on its estimation error.
Lemma (Theorem 2.6 of Hayakawa Suzuki (2020); Schmidt- (2020)). Let J be any
ERM estimator that takes its value in model F C L ([0, 11))) Suppose that there exists constant 0 such that 1 F and [|fll| S F for any f E F. Then for any 8
satisfying N(F, 6, llxx) 2 3, it holds that
inf llf - 1 +C ((F 0, (FF (lac) + +0(=+)))
Epm [1I 111
fer
where C a universal constans.
Since have assumed Px is absolutely continuous to the Lebesgue measure x and dAx |lac 0o, II. Ilxx in the right hand side can be replaced by || ll2 with a constant factor multiplication. Now, are ready to show Theorem 10.
25

---

W' T Published as a conference paper at ICLR 2022
Proof of Theorem 10
First, consider the setting of y(s) (aa s). By Theorem 9, by setting
L' =, [0 91l
B'=1, 11
C' Tú,
L max
T T
W.
T
1=2
41
30
1
T max {rå, (ra,
S
-0
2
41
B ~ (V2)TT
have that, for any fe UFFp..) p.)))) there exists dilated CNN f E P(L, B' W C², I, W,B,B, such that
Il 1 < 2012((///
Moreover, by Lemma 20, the covering number of P can be bounded as
log (A(P,6, (1
- (a:-a1) II
2 T max { (rá, T log
T 8
1 - 2
21
Here, under the assumption | S By, we can also obtain that there exists f L', B', W", L,, L, W, evaluation log (N(P, 6, ll z log (N(P, 6, [loo)). Therefore, by Lemma 21, the ERM esti- mator f taking its value in P(B,, L', B', W C, W, B) satisfies
B) such that ||ʃ - -f S 2-2(1-v/e))T and covering number
E Epm ao-1llf- f IPax
11
2 T
max - log(F)
X 2 2( 2 " YT
+ BB} + o²
+ 8(BB +o).
Thus, by taking 7" to satisfy 2 T
= 2(n of and letting =
1 n. we obtain that
Epm
<
I[
n Zeo TTT
(logn) + mlog() (log ")"
-a,-01)
2
2
"1
which yields the first assertion.
Next, we consider the setting of y max; fa,sf. We again apply Theorem so that, by setting
L' = 1,
B' =
W' ~ To,
C' C'~ T
L max [Ti, 12]
W W~ T42T///a
S~ T max
{ T [Tē 2T/a
B~ Tv
26

---

Published as a conference paper at ICLR 2022
have that, for any fo UFFp)) p.o)) there exists dilated CNN f E P(L' B', C² W,W,W.S) such that
Il -
Therefore, by the same argument as the setting of mix smoothness, we can verify
Ep. |l| f1l
2iá-u) z(a=))+T --
(log n) maxx(logn) 8 (log ")
which yields the second assertion.
G PROOFS OF THEOREMS 13 AND 14
First, we prove the following lemma.
Lemma 22. Let X (x:) Re. For any sequence (Figs....; Fig. satisfying ij S HL with arbitrary integer H > 1 and is < i2 <...< iN, there exists dilated CNN where the number of layers is L', the width of filters is H. the number of channels each layer is N and the filters Wi E R NNNNH (2 22 T) and W1 E RNN in each layer satisfy |[Willoo S 1 1..... L')
such that
(Eir,..., T (Conv HU-1. .... ConV ..... Conv1,w, o ox)
Proof. Let
A((X) = Conv #1 w. ....o Convi,w: X.
First, we let (W1)s.5 = if (ix - mod T) = - 1 and (Wi)k.J = 0 otherwise, for & E [N] and
j E [T). Then, for each & [N]. there exists (1)
4 E [HL such that A (X) 11 Fig
indeed, 2k can be obtained as b [li+ 1)/ HJ + 1. In the following, we recursively define Wi ................................
((1)
(1) and & for 1 = 2, ......,L' L' so that
A k.1 -1) = Fia (I: E [M]
(29)
is satisfied. We remark that this is satisfied for | = 2. Suppose that, for l, we have Wi and o that satisfy the condition (29). If we define
(x) =
E Nx00
for i E N, then we have that
(ConVH'..., Ai(X)) (11)))+44111111
(Wi41)aa (X)
(Wi+1)N #1 A'.,
Therefore, by letting i (1+1) (1+1) [(:!0) - 1)/HJ + (i.e., the integer such that (1(0 (++1)
1)H + < to <
k (11)) H) and setting W1+1 so that (W1+))s5 = 1 if (i - mod T) =
j-1 and (W41)kk (At+((); R. 1111)11444441 = Iú, for all E [N] holds for + 1. Therefore, by the inductive
otherwise (k [N] and j [T], we
that the condition (29)
argument, we have that
(x = (x (
because 1h satisfies 0 < (L) 1 (i 1)/HL' which yields 4 assumption is < HL.
for all & E [N] by the
A pictorial illustration of the proof of Lemma 22 with = W', N = C' and L' = 2 is given in Figure 1.
27

---

Published as a conference paper at ICLR 2022
FNN
Layer 2
Layer 1
C
Layer 0
W
3
Figure 1: Illustration of how important features are extracted by the dilated convolution. The colored circles indicate the important features (Zi....,TTg))
Proofs of Theorems 13 and 14.
Let (i be the sequence of indices that yields a; < 0i <.. for the given positive sequence (a:) We only give the proof for the mixed smoothness setting 7(8) (u,s). s). As for the anisotropic smoothness setting, same reasoning can be applied.
Since ||a||ane < 1 is satisfied by the assumption, we have 0iş 2 j for all j E N. Therefore, we can verify that for all T O, it holds that
I(T,7) = {i: 3s e N 8 #00 (a,s) S T}
{il:l
Hence, can see that dmax T fmax T by their definitions. Since a; I(logi), there exists a constant Q > 0 such that
2 log í
for E [N]. Then, a, & ST,iSexp exp (8) satisfied. By using Lemma 22 with dmaxs we construct the dilated convolutional structure
Conv
3 [
Convi,w, X
that extracts all of the elements in (I, 7). In particular, for fully connected neural network Pr with d dimensional input, we have that
pr Conv 11
Convi,w, X R I(T,,)))
(32)
that is, the convolutional neural network the right hand side depends only on the elements in 7(T,7).
28

---

Published as a conference paper at ICLR 2022
On the other hand, by Lemma 18, have that
Σ
2 =
Σ
2
(a,
:
81,
1
2
2
(ai-ai))
1
Therefore, by Theorem 7, we set
max }, 21
T12
(os -
ifi
1
S
max
T T T2
B ~ v2"
1911 1 2
there exists neural network Ry E L(L, W, B) such that f(X) Rr((æ : E (TT,))
satisfies
1/' - 2 22-00---11
(35)
Therefore, by combining Eq. (32) and Eq. (35), we can set
L' T
~ T, w' =3 C' C²= B' =1
and (I, W,S, B) above that there exists / P(L', C" I, W, B) such that
IIf fll2 < -2 )
This yields the proof of Theorem 13.
The remaining proof for the estimation error (Theorem 14) can be done in the manner that of Theorem 10, which yields Theorem 14.
H NUMERICAL EXPERIMENTS
H.1 THE EXPERIMENT OF DIMENSION INDEPENDENCE
-
p-12
2.0
2.0
4.0
4.0
estimation error
0.04
0.04
0.02
0.02
0.00
0.00
100
dimension
dimension
Figure 2: Smoothness with polynomial order in- crease
Figure 3: Smoothness with sparsity
In this section, we verify the dimension independence of CNNs by numerical experiments using functions with anisotropic smoothness. The experiments were conducted in the following settings:
29

---

Published as a conference paper at ICLR 2022
1. Smoothness with Polynomial order increase: We consider the following function as the true function:
fx) =
cos (2TT.)),
2
where P, d E N are parameters. Data generation model: = (x; (i= (i=....., n²).
Parameter settings: The trained model: CNN with the kernel width W = 10, the number of channels C' = 10, and the depth L' 1.
128, p = 1.2, 2.0, 3.0, 4.0, 5.0, d = 100, 200, 500, 1000.
2. Smoothness with sparse structure:
We consider the following function as the true function:
[d/10]
1
Σ
II cos (2T3100);
25
where p, are parameters. Data generation model: y = (x;) (i= I...., n.)
Parameter setting: 128, p 1.2, 2.0, 3.0, 4.0, 5.0, d d= 100, 200, 500, 1000.
The trained model: Dilated CNN with the depth L' = 3 layers, the kernel width W = 3, and the number of channels C' 10.
In each experiment, we estimated f from observations (x; Dr) using CNN or dilated CNN. The results are shown in Figure 2 and Figure 3. These results show that for the same p, we don't see any deterioration of the estimation error by increasing the dimensionality d of the input. These results are consistent with the fact that the thcoretical upper bound dimension independent and depends only on smoothness. Moreover, in the setting of sparse smoothness, we again observe that the estimation error is dimension-indepeedder by using dilated CNN, which is also consistent with theoretical findings.
I EXTENSION 2D CONVOLUTION
Here, present that similar argument be applied to 2D convolution for image in- puts. For that purpose, we consider a quite simple setting where the true function f has a mixed/anisotropic smoothness with respect the wavelet coefficients of the input image. More precisely, suppose that the input image X has size N x N where N = 2 for an integer
K (X E [0, 1J and let ( 3(N/2*)² for k K be the wavelet coefficient at the level k. Then, we assume the true function is 7-smooth with respect to the wavelet coefficients (01.1, 01,2,.... N/322222 0221....., (2,,(N222) N/. aK,1) E N Usually, N2 is large and a standard analysis suffers from the curse of dimensionality.
The construction of wavelet coefficients as follows (see Daubechies (1992) for more details). The wavelet transform is obtained based on pair of wavelet filter yo RN and scaling filter v E N We assume this pair of filters are given. For u E R& and E MR, let
MIUMa
M2X
2 U
UM, U1
UM, UMda
and for x, E M. let
Mi Ma
(x. v) =
Fi.j
1=1
The level & wavelet and scaling bases are obtained by
-4-1
2 2k-1
= Σ
(6=1,...,N// 1/22-11.
3
Pi4 1))/21)
Pi+0
1=1
1=1
30

---

Published as a conference paper at ICLR 2022
We apply a shift operation on these basis functions as
N/26-1 (((c)) )) = (0 ((i-1+2--11 mod (N1/2=1)]+11,; im1
(k)
E N
1, N/2*),
and we define (b(5s)) in the same way. Using these filter, we can calculate the wavelet coefficients in an inductive manner. At the first level, we obtain
d (10(..)) @ (0l.)) x)
(1.1)
(i,j E [N/2]),
(1.2) (1p(2.)) 2 (000))
(i.j E [N/2]),
a
(1.3) (1 @ (((1))
(i.j E [N/2]),
a (1,4) (v11.) @ &000), x)
(i.j e [N/2]).
Let (2222) = [a
(1.)
ji for q = 1,2,3,4. 4. At the k-th level, we assume that we have already have (q E [4]) Then, the k-th level coefficients can be obtained by
1.9) E N/
(k.1) (g0(k1)) @ p(i))) 101-1.1) (i.j E [N/2*]),
(R.2) ((0(k.1) @ ( (11)
(i, E [N/2*1),
(k.3) (Bblhi)) @ (((N)), A(
(i,j E (N/2*1),
d
(k.4) = (cbllet)) @ ( (1 (i.j E (N/2*1).
ai
(a (k.0)) )ag for q = 1,2,3,4. Then, we obtain the wavelet coefficient as in a recursive manner that represents strength of each fre- quency component of the input image at each location j. We assume that the true function f is 7-smooth with respect to this coefficient (more precisely its vectorization vec(A(X)) E RA3). Assumption 23. The true function fo :RNNN - N is 7-smooth with respect to vec(A(X)) The smoothness satisfies the sparsity (Assumption 12). Moreover, we also assume Assumptions is satisfied.
We again let (k..)
A(X) = (A A(k,3), A(k,4)) k=
From now on, we construct 2D-CNN structure extract variables in I(T,?) from vxc(A(X)). Suppose that the support of &p and e are included in the first H components, then the inner product appeared above are executable just in local H H region. For example, the Haar wavelet has H 2. Therefore, the inner product to extract the coefficients can be realized by the standard convolution operation in CNNs.
From now on, we employ the same notations used in the proof of Theorems 13 and 14, We T > 0 be any positive real. We define (dmax: fmax, G) as in Theorem If we can show that CNN can extract variables included in I(T, 7), then we can apply the same argument to Theorems 13 and 14.
Let the number of channels of of 2D convolution be C = dmax + for is = =....., K and C. = 1. For each layer & E [K- 1]. we will define filter W E RCx 1xl1xHl where H₃ = min(HI NN/2*.. J. Let (X) E RCxxN/2*> xN/2 be the output from the k-th layer of the CNN. Then, (x) is updated by the following convolution with the interval h = 2: Ao(X) = X and
H4
Hy
Ck-1
Ax = Σ
Σ
AR-1 1n 1)0 (.(
mish (q E Ck. i E [N/2*1),
where, by convention, we let Ak-1 (X)s = A mod -/2 mod N/2 for i and j which are out of the range {I...., 1/2
Next, we show that an appropriately defined filter can extract 7(T,7). First, we let part of (A) as follows to extract (k.1.1) (().2) (R.3) ((kr4)):
(x( 1,1,;; 11:HH X P1:HH
(x(k)
2,1,; 11.Hz X Vi.He
w²(k)
3,1.s. 1.I 2 11.
(A(A) 4,1.a = HI.HH @ 1h.H..
31

---

Published as a conference paper at ICLR 2022
where 24:5' (2i, ,tt1...,,,;;; "V) for a vector
Second, for 2 2. we extract the "important coefficients" included in [[T, frrm (A(4-1.2), 1.21, A ,((k-1))) that are already extracted the last layer. For that purpose, let W(k) jighhih 1 for 2 S q v 4, 2 5 and (1 E [2] if A contains the (j - 4) ele- ment of 7) at its (i )-h component. Otherwise, let W Jight O.
Finally, we extract the important coefficients included in AA-1 for q 2 5. For 5 S q S N, let 5. = 1 for 2 and 11. E [2] Ax-1 11X) contains the (j - 4)-th element of (TT,)) at its (11: component. Otherwise, we let W j.g,i..22 O.
Since the interval of convolution h 2, the size of Ax is CK x x which can be seen as "vector." By the construction above, it contains all coefficients included in I(T,7). Therefore, by feeding X vec(Ax (X)) FNN R2 considered in the proof of Theorems 13 and 14, obtain the same approximation and estimation error bounds as those theorems under Assumption 23. Here, note that the number of parameters the CNN constructed above has the same order as the DDsittation thanks. Thus, we obtain the same convergence rate as Theorems 13 and 14.
32


Reviews:
[{"review_id": "uPJyzaXayr6", "reviewer": "Reviewer_okX4", "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": "I appreciate the rigor of the theoretical framework but admit that I have not been able to check the proofs, and therefore will comment at a heuristic level below. The notations are a bit heavy, and I would suggest that the authors consider reducing the notations in the main text, adding more discussions on comparing the error rates obtained in the different settings and by the different works, adding more intuitions for the proofs and assumptions, as well as perhaps adding a pictorial illustration of the dilated CNN model. Otherwise it can be difficult to grasp the gist of the theoretical results. \n\nI am mainly curious about the implication of the assumption that the function has higher smoothness toward coordinates with larger indices (up to rearranging the indices). As the authors point out, this holds if the input corresponds to the Fourier coefficients and the target function is less sensitive to the higher-frequency components. However, this is not how we typically think about CNNs for image classification, where the convolutions are applied to the spatial domain rather than the frequency domain. Therefore, while the proposed model is interesting, I am not quite sure how helpful the theoretical guarantees for this scenario is for our understanding of FNNs or CNNs in actual applications. For example, I am not sure that the claim \"our theoretical analysis supports the great practical success of convolutional networks\" in the abstract is sufficiently convincing.\n\nThe claims that CNNs are able to “automatically extract the required index I(T, $\\gamma$)” (on page 8) and “find the important indices that are relatively non-smooth compared with other indices” (on page 9) are intriguing, and I wonder if the authors could provide some further intuitive explanations behind these statements as well as about why dilation is important heuristically.\n\nSome possible typos:\n1) Page 5 top, \"be back\" -> \"be dated back\"\n2) In Definition 4, if $W'$ is a number, what do ${W'}^{L'-1}, ..., {W'}^{l-1}$ mean? \n3) Page 6 before Remark 5, \"an dilated\" -> \"a dilated\"\n4) Page 7 before Theorem 9, \"sufficiently smoothness\" -> \"sufficiently smooth\"\n5) Page 9 in Theorem 9, \"there exits\" -> \"there exists\"\n6) Page 8 before Section 5.3, \"As fro\" -> \"As for\"\n7) Page 9 before Section 6, \"learning rates\" -> \"error rates\" ?", "summary_of_the_paper": "This paper studies the approximation and estimation errors of using neural networks (NNs) to fit functions on infinite-dimensional inputs that admit smoothness constraints. The authors first prove upper bounds on the approximation errors achieved by fully-connected neural networks (FNNs) that rely on certain smoothness measures of the target function, then derive more explicit bounds for using (1D diluted) convolutional neural networks (CNNs) to fit target functions that has smoothness with polynomial order increase, and finally extended the smoothness assumption to a form of sparsity constraint.", "summary_of_the_review": "This paper provides an interesting theoretical analysis on the ability of FNNs and (a type of) CNNs to fit functions on infinite-dimensional inputs that are smooth in certain senses, though how the results may relate to the actual usage of neural networks is not completely obvious in my opinion.", "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": "h5F3_d3pkF", "reviewer": "Reviewer_iiDe", "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 find the paper very interesting and novel, in that it explores adaptivity of convolutional architectures to useful smoothness structure in the target, providing dimension-independent rates which may hold even for infinite-dimensional signals.\nI am thus in favor of acceptance. Nevertheless, the paper is quite dense with notation, and I believe the clarity and presentation of the paper could be significantly improved:\n\n* the definition of gamma-smoothness was a bit hard to digest, and would benefit from more intuition, perhaps relating to penalizing derivatives, if appropriate.\n\n* the motivation about being more/less sensitive to high vs low frequencies in an image could be discussed further. In particular, the authors suggest that the $x_i$ for large $i$ could correspond to higher frequencies, but in practice these probably just correspond do different spatial locations of pixels. In this sense, the final result showing adaptivity to different orderings of $a_i$ for dilated CNNs is much more compelling than the previous ones.\n\n* more comments on the requirements for the network architectures would be helpful, since they are quite heavy to read in the current presentation. For instance, it would be helpful to mention in the beginning of section 5.2 that the CNNs only use *one* convolutional layer here. In Definition 4, it would be helpful to make a remark that you're choosing h = W', and why.\n\n* generally, more intuition on the results and their proofs, particularly why CNNs enable the adaptivity they do, would be helpful. More discussions after the main theorems, e.g. on limitations of FNNs and benefits of CNNs, would be welcome as well.\n\nA question: would using strided convolutions (with stride = filter size) instead of dilated convolutions also allow for similar adaptivity?\n\nMinor remarks:\n- Table 1: what is meant by $d \\ll n$? do such rates only hold asymptotically?\n- Table 1: notation-wise, using $\\tilde a$ to denote its inverse would perhaps make more sense?\n- Section C.1 contains a \"Comment: Needs more precise references\"", "summary_of_the_paper": "The paper studies non-parametric regression for functions defined on infinite-dimensional input data (such as signals in $\\ell^2$), using fully-connected networks or dilated convolutional networks (in the CNN case, convolutional layers are followed by a fully-connected network).\nThe authors consider certain smoothness classes similar to mixed or anisotropic smoothness but extended to infinite-dimensional input data, which requires per-coordinate smoothness orders ($a_i$ in Definition 2) that are non-decreasing or increasing with some rate.\nFor such classes, the authors obtain rates that only depend on $a_1$ for the mixed smoothness case, or $\\sum_i a_i^{-1}$ for the anisotropic case, for the ERM under certain classes of FNNs or CNNs. Notably, CNNs avoid the need to selecting specific finite subsets of variables as inputs (needed by FNNs), and dilated CNNs additionally allow some adaptivity to sparsity in the $a_i$, in particular, by avoiding dependence on the specific order of the $a_i$ (the growth condition is on the sorted values instead of the unsorted ones for the non-dilated case with a single convolutional layer).", "summary_of_the_review": "A good paper tackling an interesting question, namely studying adaptivity of convolutional architectures to certain function spaces.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "elGRF4kP4uO", "reviewer": "Reviewer_DfK7", "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": "The paper investigated the approximation error and estimation error of convolutional neural networks in the function spaces with mixed smoothness and anisotropic smoothness. It was shown that the convergence rates are determined by the smoothness of the target functions and independent of input dimension under mild conditions, which theoretically supports the practical success of convolutional neural networks and provides insights on how to avoid the curse of dimensionality by deep learning methods. These results are novel and of interest. I have some minor concerns as follows.\n\n1. Are the obtained rates also minimax optimal when $1\\leq p<2$?\n\n2. Is it possible to extend the theoretical results (Theorems 9 and 10) to the case when $L'$ depends on $T$ and $L_1$ (or $L_2$) is fixed?\n", "summary_of_the_paper": "The paper proves novel dimension-independent bounds for both approximation and estimation by convolutional neural networks when the input is infinite-dimensional and the target function has mixed and anisotropic smoothness. Moreover, the authors show the advantages of dilated convolution when the smoothness of the target function has a sparse structure.", "summary_of_the_review": "Overall, the paper is well-written and technically sound. The results should be of great interest to the theoretical deep learning community.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LIjm7OrQ-0e", "reviewer": "Reviewer_BeQE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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 setting with an infinite dimensional input space is a very interesting topic and is closely related to distribution regression. The rates of approximation and estimation for least squares regression by deep ReLU neural networks given in the paper are nice contributions to the theoretical study of deep learning. I recommend the paper to be accepted. \n\nThe authors might discuss the following issues:\n\n1. It would help the readers if the authors can point out the connection between the topic discussed in the paper and distribution regression. Though the setting with an infinite dimensional input space is valuable for describing some learning problems, it would improve the usage of the results if the implementation of deep neural networks in this setting could be discussed. \n\n2. For CNNs, the authors propose only linear maps for the convolutional layers without activation and argue in Remark 5 that their analysis can be applied straightforwardly when ReLU is used. This is arguable and the authors might give more details. To my opinion, the rates of approximation and learning in the paper are derived mainly by using the last fully connected layer. \n\n3. A theory for approximation and learning by 1-D CNNs with vector input spaces has been developed recently. The authors should mention some of the existing results in this development. \n\n", "summary_of_the_paper": "The authors consider approximation and learning by deep neural networks in the setting with an infinite dimensional input space. They provide nice rates for approximating and learning functions with mixed or anisotropic smoothness. The networks studied in the paper include fully connected ReLU networks and those generated by linear convolutional layers followed by a fully connected layer. ", "summary_of_the_review": "The setting with an infinite dimensional input space is very interesting. The rates of approximation and estimation by deep ReLU neural networks given in the paper are nice. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies the approximation and estimation errors of using neural networks (NNs) to fit functions on infinite-dimensional inputs that admit smoothness constraints. By considering a certain notion of anisotropic smoothness, the authors show that convolutional neural networks avoid the curse of dimensionality. 
 
Reviewers all agreed that this is a strong submission, tackling a core question in the mathematics of DL, namely developing functional spaces that are compatible with efficient learning in high-dimensional structured data. The AC thus recommends acceptance.
Decision: Accept (Spotlight)