LEARNABILITY OF CONVOLUTIONAL NEURAL NET- WORKS FOR INFINITE DIMENSIONAL INPUT VIA MIXED AND ANISOTROPIC SMOOTHNESS
Year: 2021

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 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, we show that the dilated convolution is advantageous when the smoothness of the target function has a sparse structure.

heading: 1 INTRODUCTION
text: Deep learning has shown high performance in several tasks such as image recognition, speech recognition, 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 theoretical nature are still unclear while related theoretical studies have attracted much attention. Aside from the analysis of CNNs, one of the most fundamental issues in deep learning theories is 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 a twolayer 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 Hö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 a function by a finite sample has also been extensively studied. For example, Schmidt-Hieber (2020) derived the estimation error bound of deep learning with ReLU activation (Nair & Hinton, 2010; Glorot et al., 2011) to estimate functions in the Hölder space and showed the rate of convergence achieves the (near) minimax 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 are near optimal, these studies assumed that the dimensionality of inputs is fixed and much smaller than the sample size. Indeed, the derived rates suffer from the curse of dimensionality. However, in practice, we often encounter settings where the input dimensionality is larger than the sample size or 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 et al. (2019b;a) considered a setting where data can be embedded in a low dimensional sub-manifold and derived the approximation error of functions that depends merely on the dimensionality of the sub-manifold 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 a 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 an infinite dimensional setting. See Table 1 for a summarized 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 approximation has been considered to approximate a function in a tensor product space with support on [0, 1]∞ (Dũng & Griebel, 2016) and a polynomial order approximation is possible for functions with mixed smoothness, that is, specific summability properties of the smoothness indices are fulfilled. Ingster & Stepanova (2011) analyzed a Gaussian white noise model with an infinite dimensional input 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 & Vieu (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 Dũ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 a function of images has less sensitivity on the high frequency components and more dependent on the low frequency components, which can be formulated as non-uniform smoothness toward each coordinate direction. By considering such a 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 an infinite dimensional input and has mixed or anisotropic smoothness. Then, we show that deep learning by fully connected neural networks can achieve approximation and estimation errors that depend only on smoothness of the target function and are independent of the dimensionality.
2. We also consider a setting where the smoothness of the target function has a sparse structure, and then we show that dilated CNNs can find appropriate variables and improve the rate of convergence. This indicates that CNNs can capture a long range dependence among the input.
These results show that even when the dimension d of the data is very large compared to the number of observations n, or even when the input is infinite dimensional, it is possible to derive a polynomial 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.

heading: 2 PROBLEM SETTING AND NOTATIONS
text: In this section, we prepare the notations and introduce the problem setting. Throughout this paper, we use the following notations. Let R>0 := {s ∈ R : s > 0}, and for a set D, let D∞ := {(s1, . . . , si, . . . ) : si ∈ D} (for example, R∞ := {(si)∞i=1 : si ∈ R (∀i = 1, 2, . . . )}). For
s ∈ R∞, let supp(s) = {i ∈ N : si 6= 0}. Let N∞0 := {l ∈ (N ∪ {0})∞ : supp(l) <∞} and define Z∞0 and R∞0 in the same way. Furthermore, for s ∈ R∞0 , let 2s := 2 ∑∞ i=1 si . For L ∈ N, let [L] = {1, . . . , L}. For a ∈ R, let bac be the largest integer less than or equal to a.

heading: 2.1 REGRESSION PROBLEM WITH INFINITE DIMENSIONAL PREDICTOR
text: In this paper, we consider a regression problem where the predictor (input) is infinite dimensional. Let λ be the uniform probability measure on ([0, 1],B([0, 1])) where B([0, 1]) is the Borel σ-field on [0, 1], and let λ∞ be the product measure of λ on ([0, 1]∞,B([0, 1]∞)) where B([0, 1]∞) is the product σ-algebra generated by the cylindric sets ∩j≤d{x ∈ [0, 1]∞ : xj ∈ Bj} for d = 1, 2, . . . and Bj ∈ B([0, 1]). Let PX be a probability measure defined on the measurable space ([0, 1]∞,B([0, 1]∞)) that is absolutely continuous to λ∞ and its Radon-Nikodym derivative satisfies ‖ dPXdλ∞ ‖L∞([0,1]∞) < ∞
1. Then, suppose that there exists a true function fo : [0, 1]∞ → R, and consider the following nonparametric regression problem with an infinite dimensional input:
Y = fo(X) + ξ, (1)
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 N(0, σ2) (a normal distribution with mean 0 and variance σ2 > 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 fo by a neural network, and (ii) how accurately deep learning can estimate the true function fo from n observations Dn = (Xi, yi)ni=1 where (Xi, yi) n i=1 are i.i.d. observations from the model. As a performance measure, we employ the mean squared error ‖f − fo‖2PX := EP [(f(X)− f o(X))2], which can be seen as the excess risk of the predictive error E(X,Y )∼P [(f(X)−Y )2] associated with the squared loss (i.e., ‖f − fo‖2PX = E(X,Y )∼P [(f(X) − Y )
2] − E(X,Y )∼P [(fo(X) − Y )2] = E(X,Y )∼P [(f(X)− Y )2]− inff :measurable E(X,Y )∼P [(f(X)− Y )2]).

heading: 2.2 MIXED AND ANISOTROPIC SMOOTHNESS ON INFINITE DIMENSIONAL VARIABLES
text: Here, we introduce a function class in which we suppose the true function fo is included. For a given
l ∈ Z∞0 , define ψli : [0, 1] → R as ψli(x) =  √ 2 cos(2π|li|x) (li < 0),√ 2 sin(2π|li|x) (li > 0),
1 (li = 0),
for x ∈ [0, 1], and
define ψl(X) := ∏∞ i=1 ψli(xi) for X = (xi) ∞ i=1 ∈ [0, 1]∞. Let L2([0, 1]∞) := {f : [0, 1]∞ → R :∫
[0,1]∞ f2(x)dλ∞(x) < ∞} equipped with the inner product 〈f, g〉 := ∫ [0,1]∞ f(x)g(x)dλ∞(x) for f, g ∈ L2([0, 1]∞). Then, (ψl)l∈Z∞0 forms a complete orthonormal system of L 2([0, 1]∞), that
is, f ∈ L2([0, 1]∞) can be expanded as f(X) = ∑ l∈Z∞0
〈f, ψl〉ψl(X) (see Ingster & Stepanova (2011) for example). For s ∈ N∞0 , let δs(f) : R∞ → R be
δs(f)(·) = ∑
l∈Z∞0 :b2si−1c≤|li|<2si
〈f, ψl〉ψl(·),
1This is a rather strong assumption. We can omit this if we take θ = 1 and p = ∞ for Fγp,θ . However, we don’t pursue this direction in this study.
which can be seen as the frequency component of f of frequency |li| ' 2si toward each coordinate. We also define ‖f‖p := (∫ [0,1]∞ |f |pdλ∞ )1/p for p ≥ 1. Then, we define a function space with a general smoothness configuration as follows. Definition 1 (Function class with γ-smoothness). For a given γ : N∞0 → R>0 which is monotonically non-decreasing with respect to each coordinate. For p ≥ 1, θ ≥ 1, we define the γ-smooth space as
Fγp,θ([0, 1] ∞) :=
{ f = ∑ l∈Z∞0 〈f, ψl〉ψl : ( ∑ s∈N∞0 2θγ(s)‖δs(f)‖θp )1/θ <∞ } ,
equipped with the norm ‖f‖Fγp,θ := (∑ s∈N∞0 2θγ(s)‖δs(f)‖θp )1/θ .
In the following, Fγp,θ([0, 1]∞) is abbreviated to F γ p,θ, and its unit ball is denoted by U(F γ p,θ). Remind that δs(f) represents the frequency component associated with the frequency (2si)∞i=1, and then the norm of the γ-smooth space imposes weight 2θγ(s) on each frequency component associated with s. In that sense, γ(s) controls the weight of each frequency component and accordingly a function in the space can have different smoothness toward different coordinates. As a special case of γ(s), we investigate the following ones in this paper. We can see that a finite dimensional analysis can be easily reduced to a special case of the infinite dimensional analysis (see Appendix A). In that sense, our analysis generalizes existing finite dimensional analyses. Definition 2 (Mixed smoothness and anisotropic smoothness). Given a monotonically nondecreasing sequence a = (ai)∞i=1 ∈ R∞>0, we define the mixed smoothness as
(mixed smoothness) γ(s) = 〈a, s〉, where 〈a, s〉 := ∑∞ i=1 aisi 2, and define the anisotropic smoothness as
(anisotropic smoothness) γ(s) = max{aisi : i ∈ N}.
Each component ai of a = (ai)∞i=1 represents the smoothness of the function with respect to the variable xi. Since we assumed (ai)∞i=1 is monotonically non-decreasing, a function in the space has higher smoothness toward the coordinate xi with higher index i. In other words, the function f in the space is less sensitive to the variable xi with a larger index i. For example, in computer vision tasks, we may suppose xi with a large index i corresponds to a higher frequency component of the input image, and then the function is less sensitive to such high frequency components and more sensitive to a 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) (see Appendix C for detailed discussions). In our theoretical analysis, we will assume that the true target function fo is included in the γ-smooth function space. Assumption 3. The target function satisfies fo ∈ U(Fγp,θ) with p ≥ 1 and θ ≥ 1, and ‖fo‖∞ ≤ Bf for a fixed constant Bf > 0, where the smoothness γ is either the mixed smoothness or the anisotropic smoothness.

heading: 3 RELATION TO EXISTING WORK
text: A function space with the mixed smoothness in a finite dimensional setting can 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 a special setting of a1 = · · · = ad, and an approximation error analysis for a1 = · · · = ad = 2 was given by Montanelli & Du (2019) using a sparse-grid technique. The mathematical properties of the anisotropic Besov space with finite dimensional input were analyzed in Nikol’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
2Note that, since the number of nonzero components of s ∈ N∞0 is finite, the summation always converges. For the same reason, the maximum in the anisotropic smoothness is also attained by some finite index i.
optimal rate for density estimation where the density is in an 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 γ-smooth function space is closely related to Ingster & Stepanova (2011) in which the anisotropic Sobolev space defined byFc =Wa2 := { f ∈ L2([0, 1]∞) : ∑∞ i=1 ∥∥∂aif ∂x ai i ∥∥2 2 <
∞ }
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 NadarayaWatson estimator for functional input has been extensively studied (Ferraty et al. (2007) and Ling & Vieu (2018) for a comprehensive survey). If we apply the bound given in 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 γ-smoothness. See Appendix C for more details.
Kohler & Langer (2020) analyzed CNNs in a setting where the target function has a hierarchical max-pooling structure each layer of which is sufficiently smooth. On the other hand, our γ-smooth function class imposes smoothness more directly on the target function. Liu et al. (2021) analyzed learning ability of CNNs with a ResNet structure in a classification task where the data are distributed on a low-dimensional manifold and established a rate which only depends on the dimensionality of the low dimensional manifold. However, the input should be distributed on a low dimensional manifold, while our analysis allows its support to be infinite dimensional. Estimation errors on a low dimensional structure also have been studied in Yang & Dunson (2016); Bickel & Li (2007); Nakada & Imaizumi (2020); Schmidt-Hieber (2019); Chen et al. (2019b).

heading: 4 DEFINITION OF A DILATED CONVOLUTIONAL NEURAL NETWORK
text: In this section, we introduce the neural network model that we investigate in this paper. Let L ∈ N be the depth of the network and di (i = 1, . . . , L + 1) be the width of the i-th layer in the network where we set dL+1 = 1. Then, the fully connected neural network (FNN) can be given by (ALη(·) + bL) ◦ · · · ◦ (Aiη(·) + bi) ◦ · · · ◦ (A1x + b1) where Ai ∈ Rdi+1×di , bi ∈ Rdi+1 and η(x) = max{x, 0} is the ReLU activation function that is applied element-wise. The set of FNN with depth L ∈ N, maximum widthW ∈ N, norm boundB > 0, and sparsity level S ∈ N is defined by
Φ(L,W, S,B) := { f(x) = (ALη(·) + bL) ◦ · · · ◦ (Aiη(·) + bi) ◦ · · · ◦ (A1x+ b1) :
max i=1,...,L ‖Ai‖∞ ∨ ‖bi‖∞ ≤ B, L∑ i=1 ‖Ai‖0 + ‖bi‖0 ≤ S, max i=1,...L di ≤W } ,
where ‖ · ‖∞ is the maximum absolute value among the elements of a vector or matrix3, and ‖ · ‖0 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 RC×∞ :={ (x1, . . . xi, . . . ) : xi ∈ RC } . Suppose that w ∈ RC×W ′ is a filter with a width W ′ ∈ N, channel size C ∈ N and an interval h ∈ N, then define the dilated convolution w?hX ′ ∈ R∞ for an infinitesequence of vectors X ′ = (x′i,j) C,∞ i=1,j=1 ∈ RC×∞ as (w ?h X ′)k = ∑C i=1 ∑W ′ j=1 wi,jx ′ i,h(j−1)+k. When h = 1, it is called a normal convolution. Moreover, given a filter F ∈ RC′×C×W ′ with (C ′)- multiple channel outputs, we define its corresponding convlution Convh,F : RC×∞ → RC ′×∞ as
Convh,F (X ′) =  F1,:,: ?h X ′
... FC′,:,: ?h X ′  . Then, the dilated CNN can be defined as follows (its illustration can be found in Figure 1).
3We define a ∨ b := max{a, b} and a ∧ b := min{a, b} for a, b ∈ R.
Definition 4 (Dilated CNN). For a given L′, W ′ ∈ N, suppose that we are given filters Fl ∈ RCl+1×Cl×W ′ with the number of channels Cl ∈ N (l ∈ [L′]) with
C1 = 1 and an FNN gFNN ∈ Φ(L,W,B, S), then a neural network given by f(X) =( gFNN ◦ ConvW ′L′−1,FL′ ◦ · · · ◦ ConvW ′l−1,Fl ◦ · · · ◦ Conv1,F1 ◦X ) 1
is called a dilated CNN4, where gFNN 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 Cl = C ′ (2 ≤ ∀l ≤ L′) in all layers but C1 = 1 is denoted by
P(L′, B′,W ′, C ′, L,W, S,B) = {( gFNN ◦ ConvW ′L′−1,FL′ ◦ · · · ◦ Conv1,F1 ◦X ) 1 :
Fl ∈ RC ′×C′×W ′ (l ≥ 2), F1 ∈ RC ′×1×W ′ , ‖Fl‖∞ ≤ B′, gFNN ∈ Φ(L,W,B, S) } .
For simplicity, the set of dilated CNNs is abbreviated to P when there is no ambiguity about the parameter configuration. When L′ = 1, it coincides with a set of regular CNNs. In our analysis, it is sufficient to consider an dilated CNN with a constant number of channels throughout all layers (Cl = C (∀l ∈ [L′])). To evaluate the estimation accuracy, it is important to assume the functions in the set is bounded in terms of the L∞-norm. For that purpose, we consider an dilated CNN clipped by a bound Bf > 0 defined as P̄(Bf , L′, B′,W ′, C, L,W, S,B) :={ f̄(X) = (−Bf ∨ (Bf ∧ f(X))) : f ∈ P(L′, B′,W ′, C, L,W, S,B) } .
Remark 5. In the definition of the dilated CNN, we do not impose ReLU activation. However, since ReLU activation can realize a linear function for a bounded input and thus our analysis can be straightforwardly applied even if there is nonlinear ReLU activation. Moreover, this paper mainly focuses on 1D-convolution, but it can be generalized to 2D-convolution. See Appendix I for the detailed discussions in which it is shown that γ-smoothness over a wavelet decomposition of an input image achieves the same rate of convergence as in 1D-convolution.

heading: 5 APPROXIMATION AND ESTIMATION ERRORS OF DEEP LEARNING
text: 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 γ-smooth function class.

heading: 5.1 APPROXIMATION ERROR ANALYSIS BY FULLY CONNECTED NEURAL NETWORKS
text: Here, we present the approximation error analysis of FNNs for a general smoothness γ not restricted to the mixed/anisotropic smoothness. For a given T > 0 and the smoothness γ : N∞0 → R>0, define
I(T, γ) := {i ∈ N : ∃s ∈ N∞0 , si 6= 0, γ(s) < 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 defined by dmax(T, γ) := |I(T, γ)|. Moreover, the frequency direction complexity is defined by fmax(T, γ) := maxs∈N∞0 : γ(s)≤T maxi∈N si.
The axial complexity is used to evaluate how many components need to be extracted from a given infinite-dimensional sequence X ∈ R∞ to achieve a particular approximation error, and the frequency complexity characterizes up to which frequency we require to approximate a target function with a particular error. Let
v := (
1 p − 1 2 ) + , α(γ) := sups∈N∞0 ∑∞ i=1 si γ(s) , G(T, γ) := ∑ s∈N∞0 : γ(s)<T 2s,
where (x)+ := max{x, 0}. Then, a general approximation error theory for FNNs can be obtained as follows. Theorem 7 (Approximation error for the γ-smooth space by FNNs). Assume that γ, γ′ : N∞0 → R>0 satisfy
γ′(s) < γ(s), vα(γ) < 1, vα(γ′) < 1,
4Here, we employ h = W ′k−1 for the k-th layer convolution. This structure is useful to show its feature extraction ability in Section 5.3.
and the target function f ∈ Fγp,θ (p ≥ 1, θ ≥ 1) to be approximated satisfies ‖f‖∞ ≤ Bf for a constant Bf ∈ R>0. For arbitrary T > 0, we let a tuple (dmax, fmax, G) be
(dmax, fmax, G) = { (dmax(γ), fmax(γ), G(T, γ)) (1 ≤ θ ≤ 2), (dmax(γ ′), fmax(γ ′), G(T, γ′)) (2 < θ),
and with some positive constants K, K ′ depending only on Bf , we let L = 2K max { d2max, T 2, (logG)2, log fmax } , W = 21dmaxG,
S = 1764Kd2max max { d2max, T 2, (logG)2, log fmax } G, B = ( √ 2)dmaxK ′.
Then, there exists an FNN R̂T ∈ Φ(L,W, S,B) with dmax-dimensional input that takes (xi)i∈I(T,γ) ∈ [0, 1]dmax as an input such that f ′ : [0, 1]∞ → R given by f ′(X) := R̂T ( (xi)i∈I(T,γ) ) for X = (xi)∞i=1 ∈ [0, 1]∞ satisfies
‖f − f ′‖2 .  2 −(1−vα(γ))T ‖f‖Fγp,θ (1 ≤ θ ≤ 2),
2−(1−vα(γ ′))T (∑ T≤γ′(s) 2 2θ θ−2 (γ ′(s)−γ(s)) )1/2−1/θ ‖f‖Fγp,θ (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 approximation accuracy is determined by (dmax, fmax, G), it is not directly affected by the dimensionality but is characterized merely by the smoothness parameter γ. Intuitively, T > 0 controls the approximation 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 is characterized by the number of s ∈ N∞0 with γ(s) < T , and the maximum frequency required for the approximation is also important for the analysis. The bound is proven by evaluating an approximation error of a trigonometric polynomial approximation of f ∈ Fγp,θ and showing that we can construct a neural network that approximates a trigonometric polynomial with a certain accuracy.

heading: 5.2 SMOOTHNESS WITH POLYNOMIAL ORDER INCREASE
text: Here, we derive a concrete convergence rate for CNNs in a setting where γ is mixed or anisotropic smoothness and the smoothness parameter a = (ai)∞i=1 is polynomially increasing. In this setting, we just need to 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 < ∞ such that the smoothness parameter a = (ai)∞i=1 satisfies ai = Ω(i
q). We also assume a1 < a2 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). Suppose that Assumptions 3 and 8 hold, then we have the following approximation error bounds:
1. Mixed smoothness (γ(s) = 〈a, s〉): Suppose that v/a1 < 1. Then, for arbitrary T > 0, there exists a configuration of the network structure, L′ = 1, B′ = 1, W ′ ∼ T 1 q , C ′ ∼ T 1 q and
L1(T ) ∼ max { T 2 q , T 2 } , W1(T ) ∼ (∏∞ i=2 ( 1− 2 −(ai−a1) a1 )−1) T 1 q 2 T a1 ,
S1(T ) ∼ (∏∞
i=2
( 1− 2 −(ai−a1) a1 )−1) T 2 q max { T 2 q , T 2 } 2 T a1 , B1(T ) ∼ ( √ 2)T 1 q ,
such that there exists an dilated CNN f ′ ∈ P(L′, B′,W ′, C ′, L1(T ),W1(T ), S1(T ), B1(T )) satisfying the following approximation error:
‖f ′ − fo‖2 . 2 − ( 1− va1 ) T .
2. Anisotropic smoothness (γ(s) = maxi{aisi}): Let ã := ( ∑∞ i=1 a −1 i ) −1 and suppose 0 < ã and v < ã, then there exists a network structure setting L′ = 1, B′ = 1, W ′ ∼ T 1 q , C ′ ∼ T 1 q and
L2(T )∼max { T 2 q , T 2 } , W2(T )∼T 1 q 2T/ã, S2(T )∼T 2 q max { T 2 q , T 2 } 2T/ã, B2(T )∼( √ 2)T 1 q ,
such that there exists an dilated CNN f ′ ∈ P(L′, B′,W ′, C ′, L2(T ),W2(T ), S2(T ), B2(T )) satisfying the following approximation error: ‖f ′ − fo‖2 . 2−(1−v/ã)T .
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 I(T, γ) 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 I(T, γ).
Next, we consider the estimation error of these models in the regression problem (Eq. (1)). Suppose that we are given n observations Dn = (Xi, yi)ni=1 following the model (1). We consider the empirical risk minimization estimator (ERM estimator) in the model P̄ that is given by any minimizer of the empirical risk:
f̂ ∈ argmin f∈P̄
1
n n∑ i=1 (f(Xi)− yi)2.
As we have stated above, we employ the mean squared error ‖f̂−fo‖2PX as a performance measure. Since f̂ depends on the training data Dn, we take expectation with respect to Dn: EPn [‖f̂ − fo‖2PX ] := E(Xi,yi)ni=1∼Pn [‖f̂ − f
o‖2PX ]. Then, the following theorem holds. Theorem 10 (Estimation error under smoothness with polynomial order increase). Suppose that Assumptions 3 and 8 hold, then we have the following estimation error bounds:
1. Mixed smoothness (γ(s) = 〈a, s〉): If v/a1 < 1, then by setting the network structure as L′ = 1, B′ = 1, W ′ ∼ (log n) 1 q , C ′ ∼ (log n) 1 q and (L,W, S,B) = (L1(T ),W1(T ), S1(T ), B1(T )) for T = a12(a1−v)+1 log2(n), the ERM estimator f̂ in P̄(Bf , L ′, B′,W ′, C ′, L,W, S,B) achieves
EPn [‖f̂ − f◦‖2PX ] . (∏∞ i=2(1− 2 −(ai−a1) a1 )−1 ) n − 2(a1−v) 2(a1−v)+1 (log n) 2 q+2 max{(log n) 4 q , (log n)4}.
2. Anisotropic smoothness (γ(s) = maxi{aisi}): Under the same setting, if v < ã, by setting the network structure as L′ = 1, B′ = 1, W ′ ∼ (log n) 1 q , C ′ ∼ (log n) 1 q and (L,W, S,B) = (L2(T ),W2(T ), S2(T ), B2(T )) for T = ã2(ã−v)+1 log2(n), the ERM estimator f̂ in P̄(Bf , L′, B′,W ′, C ′, L,W, S,B) achieves
EPn [‖f̂ − f◦‖2PX ] . n − 2(ã−v) 2(ã−v)+1 (log n) 2 q+2 max{(log n) 4 q , (log n)4}.
The proof can be found in Appendix F. This theorem shows that even if the dimension of the input data is infinite, for a function with a particular smoothness, CNNs can achieve a dimensionindependent convergence rate which is a polynomial order, that is, it can avoid the curse of dimensionality by utilizing the increasing smoothness. We can see that the derived convergence rate is a direct extension of finite dimensional one. Actually, if v = 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 as minimax optimal. Therefore, CNNs can achieve the optimal rate up to poly-log order at least when v = 0. As for the mixed smoothness, a finite dimensional version was analyzed (Suzuki, 2019) and a similar rate was derived. However, our analysis assumes a1 < a2 and ai = Ω(iq) and thus obtained completely dimensionality independent bound while the bound by Suzuki (2019) depends on d in the exponent of the poly-log order.

heading: 5.3 SMOOTHNESS WITH SPARSITY
text: Next, we relax the assumption ai = Ω(iq) and consider a situation where there is a kind of sparse structure in a. As we have seen in the previous section, under the assumption that the coordinates 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 a 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 `q-norm of smoothness). Given a = (ai)∞i=1 ∈ R∞>0 which is not necessarily monotonically increasing, consider the sorted sequence 0 < ai1 ≤ ai2 ≤ · · · in the ascending order. Then, define its weak `q-norm for 0 < q <∞ as ‖a‖wlq := supj jqa−1ij .
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‖wlq is small, almost all ais are very large and there are only few indices that are small, which means sparseness. If the smoothness parameter a has a small weak `q-norm, then we can say that the functions with such smoothness has a small number of important coordinate directions. Therefore, it is expected that we can approximate such a function efficiently by a neural network. In this section, we analyze the approximation and estimation errors under the condition of sparse smoothness. Assumption 12. a = (ai)∞i=1 satisfies ‖a‖wlq ≤ 1 for 0 < q <∞ and ai = Ω(log i).
Note that this assumption relaxes the condition ai = Ω(iq) in Assumption 8 to ai = Ω(log i). Instead, it imposes the sparsity ‖a‖wlq ≤ 1. Under this assumption, we obtain the following approximation 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 (γ(s) = 〈a, s〉): Suppose that v/ai1 < 1, then there exist a set of network structure parameters satisfying5
L′ ∼ T, B′ = 1, W ′ = 3, C ′ ∼ T 1 q ,
such that there exists an dilated CNN f ′ ∈ P(L′, B′,W ′, C ′, L1(T ),W1(T ), S1(T ), B1(T )) satisfying ‖f ′ − fo‖2 . 2 −(1− 1ai1 )T .
2. Anisotropic smoothness (γ(s) = maxi{aisi}): Suppose that 0 < ã and v < ã, then there exist a set of network structure parameters satisfying L′ ∼ T, B′ ∼ 1, W ′ = 3, C ′ ∼ T 1 q such that there exists an dilated CNN f ′ ∈ P(L′, B′,W ′, C ′, L2(T ),W2(T ), S2(T ), B2(T )) satisfying ‖f ′ − fo‖2 . 2−(1−v/ã)T .
We can see that this approximation error bound gives the same bound as Theorem 9 under a relaxed 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 9. This difference is required to 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 ∈ N : i = O(3L′)} (see Figure 1 for illustration of feature extraction by CNNs). Accordingly, we also have the following estimation error bound. Theorem 14 (Estimation error for sparse smoothness). Suppose that Assumptions 3 and 12 hold, then by setting L′ ∼ log n, B′ ∼ 1, W ′ = 3, C ′ ∼ (log n) 1 q and (L,W, S,B) as in Theorem

heading: 10, the ERM estimator f̂ in the class of dilated CNNs can achieve the same convergence rate of the estimation error as Theorem 10.
text: 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 extracting data with long-term dependence, convergence rates that avoid dependence on dimensionality can be achieved by using dilated CNNs.

heading: 6 CONCLUSION
text: In this study, we gave a condition on 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) or infinite dimensional (d =∞). This study showed that the smoothness of the target function plays an essential role in characterizing the estimation error bound. Especially, when the smoothness parameter (ai)∞i=1 grows up as the index i increase, we can obtain a polynomial order convergence rate even if the input is infinite dimensional. Future plans include, for example, considering a situation where the smoothness depends on each input location, and extending the definition of Fγp,θ so that it captures more realistic situations.
5The choice W ′ = 3 is not a strict requirement. It can be replaced by an arbitrary integer H with H ≥ e.

heading: A CONNECTION TO FINITE DIMENSIONAL INPUT SETTING
text: We can easily see that the analysis in our paper can be directly applied to a setting where the input is finite dimensional (say, d-dimensional). Let
Jd := {s ∈ N∞0 : si = 0 (i = d+ 1, . . . )} ,
and suppose that γ(s) : N∞ → R>0 ∪ {∞} satisfies γ(s) < ∞ (s ∈ Jd) and γ(s) = ∞ (s /∈ Jd). If we set
Fγp,θ,d([0, 1] ∞) :=
{ f = ∑ l∈Z∞0 〈f, ψl〉ψl : ( ∑ s∈Jd 2θγ(s)‖δs(f)‖θp )1/θ <∞, δs(f) = 0 (∀s /∈ Jd) } ,
then by the condition δs(f) = 0 (∀s /∈ Jd), f ∈ Fγp,θ,d([0, 1]∞) is independent of (xi)i>d:
f(x1, . . . , xd, xd+1, . . . , xi, . . . ) = f(x1, . . . , xd, x ′ d+1, . . . , x ′ i . . . ),
for any (xi)∞i=1 ∈ [0, 1]∞ and x′i ∈ [0, 1] (i = d+ 1, d+ 2, . . . ). Then, for f ∈ F γ p,θ,d([0, 1] ∞), we may define
fd(x1, . . . xd) := f(x1, . . . , xd, 0, . . . ),
and it holds that ‖f − f ′‖2 = ‖fd − f ′d‖2. Hence, by the same argument as the proof of Theorem 7, we have the same bound for Fγp,θ,d([0, 1]∞). Thus, the same statement as Theorem 7 holds for the γ-smooth functions on [0, 1]d. This shows that the difficulty of the approximation depends only on the smoothness γ(s) and independent of the dimensionality d. In particular, we can establish the bound even for d n.

heading: B ANALYSIS OF ESTIMATION ERROR BY CONVOLUTIONAL NEURAL NETWORK
text: In this section, we discuss approximation and estimation errors by CNNs and dilated CNNs. In Theorem 7, we considered approximating a function in Fγp,θ by FNNs. According to the analysis, the index required to achieve the derived approximation error bound is determined by I(T, γ), and only the coordinates corresponding to the index set I(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, it 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 in mixed and anisotropic smooth spaces that depends on the smoothness of the function classes.

heading: C RELATIONSHIP TO EXISTING FUNCTION SPACES
text: In this section, we discuss the relationship between the spaceFγp,θ, its finite dimensional counter-part and some related function classes.
C.1 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]d. Definition 15 (Mixed smooth modulus of smoothness). For r ∈ N and h ∈ R>0, let
∆rh(f)(x) =
{∑r j=0 ( r j ) (−1)r−jf(x+ jh) (x ∈ [0, 1], x+ rh ∈ [0, 1]),
0 (otherwise),
be the r-th order discrete differentiation for a function f : [0, 1] → R. By applying this discrete differential operator to each coordinate of a subset e ⊂ {1, . . . , d}, the mixed discrete differential operator for a step length h ∈ Rd>0 and the order parameter r ∈ Nd is defined as
∆ri,ihi (f)(x) = ∆ ri hi (f(x1, . . . , ·, . . . , xd)(xi))) , ∆r,eh (f) := (∏ i∈e ∆ri,ihi ) (f),
for x ∈ [0, 1]d. Then, the modulus of mixed smoothness is defined by wer,p(f, t) := sup
|hi|≤ti,i∈e ‖∆r,eh (f)‖p,
for t ∈ Rd>0 and 1 ≤ p, where ‖ · ‖p is the Lp-norm with respect to the Lebesgue measure on [0, 1]d.
Then, based on this modulus of mixed smoothness, we can define the mixed smooth Besov space as follows. Definition 16 (Mixed smooth Besov space). Let 1 ≤ p, q ≤ ∞. For a given smoothness parameter a ∈ Rd>0, let ri = baic+ 1 (i ∈ [d]) and define the seminorm | · |MBa,ep,q as
|f |MBa,ep,q :=  {∫ x∈[0,1]d [(∏ i∈e t −ai i ) wer,p(f, t) ]q dt∏ i∈e ti }1/q (1 ≤ q <∞),
supt∈[0,1]d (∏ i∈e t −ai i ) wer,p(f, t) (q =∞).
Then we define the norm of the mixed smooth Besov space as ‖f‖MBap,q := ‖f‖p + ∑
e⊂{1,...,d}
|f |MBa,ep,q ,
so that the mixed smooth Besov space is given by MBαp,q([0, 1] d) := {f ∈ Lp([0, 1]d) : ‖f‖MBap,q <∞}.
The mixed smooth Besov space defined above can be seen as the finite dimensional counter part of our space with mixed smoothness γ. Here, for s ∈ Nd, let
δs(f) = ∑
l∈Zd0 :b2si−1c≤|li|<2si
〈f, ψl〉ψl,
where ψl : [0, 1]d → R is defined in the same way as in the infinite dimensional setting and f ∈ L2([0, 1]d). Then, it is known that
|f |MBap,q ∼ ( ∑ s∈Nd0 (2〈a,s〉‖δs(f)‖p)q )1/q
holds for 1 < p < ∞ (see Section 3.3 of Dung et al. (2018), Yanchenko (2020); Lizorkin & Nikol’skii (1990) and references therein). Therefore, the mixed frequency space can be viewed as an extension of the finite-dimensional mixed smooth Besov space to the infinite dimensional one. Approximation and estimation abilities of deep learning with ReLU activation for the true function in the finite-dimensional mixed smooth Besov space was investigated by Suzuki (2019) when a1 = · · · = ad. They showed that deep learning can achieve the (near) minimax optimal rate in this setting and the mixed smoothness alleviates the curse of dimensionality.
C.2 ANISOTROPIC SMOOTHNESS
Ingster & Stepanova (2006) considered a general function class representated by
Fc := f ∈ L2([0, 1]∞) : ∑ l∈Z∞0 c2l 〈f, φl〉2 <∞  for a given sequence c = (cl)l∈Z∞0 with cl ∈ R. This class includes our γ-smooth space with p = θ = 2. In particular, Ingster & Stepanova (2011) analyzed an estimation problem when (cl)l∈Z∞0 is given by
c2l = ∞∑ i=1 (2πli) 2ai ,
for monotonically increasing sequence a = (ai)∞i=1 ∈ R∞>0. It can be shown that, in this setting, Fc is specifically given by the following anisotropic Sobolev classe:
Fc =Wa2 :=
{ f ∈ L2([0, 1]∞) :
∞∑ i=1 ∥∥∥∥∂aif∂xaii ∥∥∥∥2 2 <∞ } .
This characterization highlights the intuition of the anisotropic smoothness, i.e., we assume the functions f ∈ Fc have different smoothness (ai) with respect to each coordinate xi. Here, by noticing that ‖δs(f)‖22 = ∑ l∈Z∞0 :b2si−1c≤|li|<2si 〈f, φl〉2, we have that
‖f‖2Wa2 = ∑ l∈Z∞0 c2l 〈f, ψl〉2 = ∑ s∈N∞0 ∑ l∈Z∞0 :2si−1≤|li|<2si c2l 〈f, ψl〉2
≥ ∑ s∈N∞0 max i∈N {(2π2si−1)2ai} ∑ l∈Z∞0 :2si−1≤|li|<2si 〈f, ψl〉2
≥ ∑ s∈N∞0 22 max{aisi} ∞ i=1 ∑ l∈Z∞0 :2si−1≤|li|<2si 〈f, ψl〉2
= ∑ s∈N∞0 22 max{aisi} ∞ i=1‖δs(f)‖22 = ‖f‖2Fγ2,2 ,
for γ(s) = maxi{aisi}. Therefore, we see that the unit ball of the anisotropic Sobolev spaceWa2 is included in the unit ball of Fγ2,2. 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 on a finite dimensional space [0, 1]d (Nikol’skii, 1975; Vybiral, 2006; Triebel, 2011).

heading: D PROOF OF THEOREM 7
text: We can see that δs can be decomposed as δs(f)(x) = ∑
k∈Z∞0 :b2si−1c≤|ki|<2si
ck exp(2πi〈k, x〉),
for ck ∈ C and the imaginary number i. Thus, when 1 ≤ p ≤ 2, from Theorem 1 of Nessel & Wilmes (1978), we have that ‖δs(f)‖2 ≤ 2vs‖δs(f)‖p, (4) where v = ( 1p − 1 2 )+ and 2 vs = 2v ∑∞ i=1 si . Furthermore, for 2 < p, from the Cauchy-Schwarz inequality, we obtain
‖δs(f)‖22 = ∫
[0,1]∞ δs(f)
2dλ∞
≤ (∫ [0,1]∞ δs(f) pdλ∞ )2/p(∫ [0,1]∞ 1dλ∞ )1−2/p = ‖δs(f)‖2p.
Therefore, Eq. (4) holds all over the range of 1 ≤ p <∞. To show the approximation error in the assertion of the theorem, we consider approximating f by RT (f) defined as
RT (f) :=
{∑ s∈N∞0 :γ(s)<T
δs(f) (1 ≤ θ ≤ 2),∑ s∈N∞0 :γ′(s)<T δs(f) (2 < θ).
Then, we further approximateRT (f) by a fully connected neural network. For that purpose, we first analyze the approximation error ‖f − RT (f)‖2 by RT (f). This can be evaluated in the following lemma. Lemma 17. Under the same setting as Theorem 7, we have that
‖f −RT (f)‖2 ≤  2 −(1−vα)T ‖f‖Fγp,θ (1 ≤ θ ≤ 2), 2−(1−vα ′)T [∑
T≤γ′(s) 2 2θ θ−2 (γ
′(s)−γ(s)) ]1−2/θ
‖f‖Fγp,θ (θ > 2).
Proof. We show the inequality for the settings 1 ≤ θ ≤ 2 and 2 < θ separately. 1. Approximation error ‖f −RT (f)‖2 by RT (f) for 1 ≤ θ ≤ 2: Using the orthogonality of δs between different s, we have
‖f −RT (f)‖θ2 = (‖f −RT (f)‖22)θ/2
≤  ∑ s∈N∞0 :T≤γ(s) ‖δs(f)‖22 θ/2 (5) ≤
∑ s∈N∞0 :T≤γ(s) (2vs‖δs(f)‖p)θ (∵ θ/2 ≤ 1)
= ∑
s∈N∞0 :T≤γ(s)
(2γ(s)2vs−γ(s)‖δs(f)‖p)θ, (6)
where Eq. (4) is used to show Eq. (5). Then, for s ∈ N∞0 with T ≤ γ(s), using the assumption v ∑∞ i=1 si γ(s) ≤ vα(γ) < 1, we have that
2vs−γ(s) ≤ 2(vα−1)γ(s) ≤ 2(vα−1)T .
Then, applying this inequality to Eq. (6), we obtain∑ T≤γ(s) (2γ(s)2vs−γ(s)‖δs(f)‖p)θ ≤ 2−θ(1−vα)T ∑ T≤γ(s) ( 2γ(s)‖δs(f)‖p )θ ≤ 2−θ(1−vα)T ‖f‖θFγp,θ .
2. Approximation error ‖f −RT (f)‖2 by RT (f) for 2 < θ: Using again the orthogonality of δs(f) between different s, we obtain
‖f −RT (f)‖22 = ∑
T≤γ′(s)
‖δs(f)‖22,
and ∑ T≤γ′(s) ‖δs(f)‖22 ≤ ∑ T≤γ′(s) (2vs‖δs(f)‖p)2
= ∑
T≤γ′(s)
( 2vs−γ ′(s)2γ ′(s)−γ(s)2γ(s)‖δs(f)‖p )2 . (7)
Then, using the assumption vα′ < 1 for α′ = α(γ′), we obtain 2vs−γ ′(s) ≤ 2(vα′−1)γ′(s) ≤ 2(vα ′−1)T . Applying this inequality to Eq. (7), we obtain∑
T≤γ′(s)
( 2vs−γ ′(s)2γ ′(s)−γ(s)2γ(s)‖δs(f)‖p )2 ≤ 2−2(1−vα ′)T ∑
T≤γ′(s)
( 2γ ′(s)−γ(s)2γ(s)‖δs(f)‖p )2 .
Then, by using Cauchy-Schwarz inequality, we obtain
2−2(1−vα ′)T ∑ T≤γ′(s) ( 2γ ′(s)−γ(s)2γ(s)‖δs(f)‖p )2
≤ 2−2(1−vα ′)T  ∑ T≤γ′(s) ( 2γ(s)‖δs(f)‖p )θ2/θ ×  ∑ T≤γ′(s) ( 2γ ′(s)−γ(s) )2/(1−2/θ)(1−2/θ)
≤ 2−2(1−vα ′)T  ∑ T≤γ′(s) 2 2θ θ−2 (γ ′(s)−γ(s)) 1−2/θ ‖f‖2Fγp,θ .
Next, consider approximatingRT by a neural network. We show it only for 1 ≤ θ ≤ 2, but the same argument can be applied for 2 < θ. Theorem 4.1 in Perekrestenko et al. (2018) asserts that there exist constants C1, C2 > 0 such that, for
Lψ̃ = C1
[( log 1 )2 + log (fmax) ] ,
there exists a neural network ψ̃li ∈ Φ(Lψ̃, 21, C2, 212Lψ̃) that can approximate ψli as
‖ψli − ψ̃li‖L∞([0,1]) ≤ .
Moreover, since ψli ∈ [− √ 2, √ 2],
‖max{− √ 2,min{ √
2, ψ̃li}} − ψli‖L∞([0,1]) ≤ . (8) Since, we can write
max{− √ 2,min{ √ 2, x}} = [ η(x)− η(x− √ 2) ] + [ −η(−x) + η(−x+ √ 2) ]
for x ∈ R, it holds that max{− √ 2 min{ √ 2, x}} ∈ Φ(2, 4, √ 2, 16) and then we can see that
max{− √ 2,min{ √ 2, ψ̃li}} ∈ Φ(Lψ̃ + 2, 21, max{C2, √ 2}, 212(Lψ̃ + 2)).
By using these facts, we can construct the neural network that takes value in [− √ 2, √
2]. In the following, let
ψ̂li = max{− √ 2,min{ √ 2, ψ̃li}}, Lψ̃ = C1 [( log 1 )2 + log (fmax) ] + 2.
Since we need to approximate a trigonometric polynomial, we need to (approximately) realize multiplications by neural networks. By Proposition 3 of Yarotsky (2017), using
L× =
⌈ log ( 3dmax + 5 )⌉ dlog dmaxe , W× = 6dmax, S× = L×W 2×
and a constant B× > 0, there exists a neural network φ× ∈ Φ(L×,W×, B×, S×) that satisfies∥∥∥∥∥φ× − dmax∏ i=1 xi ∥∥∥∥∥ L∞([−1,1]dmax ) ≤ . Since ψ̂li ≤ √
2 is satisfied, we know that∥∥∥∥∥φ× ( ψ̂l1√ 2 , . . . , ψ̂ldmax√ 2 ) − dmax∏ i=1 ψ̂li√ 2 ∥∥∥∥∥ L∞([0,1]∞) ≤
⇒ ∥∥∥∥∥(√2)dmaxφ× ( ψ̂l1√ 2 , . . . , ψ̂ldmax√ 2 ) − dmax∏ i=1 ψ̂li ∥∥∥∥∥ L∞([0,1]∞) ≤ √ 2 dmax . (9)
Here, note that Eq. (8) yields that∥∥∥∥∥ dmax∏ i=1 ψ̂li − dmax∏ i=1 ψli ∥∥∥∥∥ L∞([0,1]∞)
= ∥∥∥∥∥∥ dmax−1∑ j=0  j∏ i=1 ψ̂li dmax∏ i=j+1 ψli − j+1∏ i=1 ψ̂li dmax∏ i=j+2 ψli ∥∥∥∥∥∥ L∞([0,1]∞)
= ∥∥∥∥∥∥ dmax−1∑ j=0  j∏ i=1 ψ̂li dmax∏ i=j+2 ψli ( ψ̂lj+1 − ψlj+1 )∥∥∥∥∥∥ L∞([0,1]∞)
≤ √ 2 dmax dmax−1∑ j=0 ∥∥∥ψ̂lj+1 − ψlj+1∥∥∥ L∞([0,1]∞) ≤ √ 2 dmax
dmax .
Then, by using triangle inequality and Eq. (9), we know that∥∥∥∥∥(√2)dmaxφ× ( ψ̂l1√ 2 , . . . , ψ̂ldmax√ 2 ) − dmax∏ i=1 ψli ∥∥∥∥∥ L∞([0,1]∞)
≤ ∥∥∥∥∥(√2)dmaxφ× ( ψ̂l1√ 2 , . . . , ψ̂ldmax√ 2 ) − dmax∏ i=1 ψ̂li ∥∥∥∥∥ L∞([0,1]∞) + ∥∥∥∥∥ dmax∏ i=1 ψ̂li − dmax∏ i=1 ψli ∥∥∥∥∥ L∞([0,1]∞) ≤ ( √ 2)dmax(dmax + 1) .
Therefore, if we set
R̂T (f) := ∑
γ(s)<T ∑ l∈J(s) ( √ 2)dmax〈f, ψl〉φ×
( ψ̂l1√
2 , . . . , ψ̂ldmax√ 2
) ,
where J(s) := {l ∈ Z∞0 : b2si−1c ≤ |li| < 2si}, we obtain that
‖R̂T −RT ‖L∞([−1,1]dmax)
= ∥∥∥∥∥∥ ∑
s∈N∞0 :γ(s)<T
∑ l∈J(s) ( √ 2)dmax〈f, ψl〉
( φ× ( ψ̂l1√
2 , . . . , ψ̂ldmax√ 2
) − ψl√
2 dmax )∥∥∥∥∥∥ L∞([−1,1]dmax )
≤ BfG(T, γ)( √ 2)dmax(dmax + 1) ,
where we used the fact 〈f, ψl〉 ≤ ‖f‖2 ≤ Bf in the last inequality. Hence, if we put
= 2−T
( √ 2)dmaxBf (dmax + 1)G(T, γ) , (10)
then we have that
‖f − R̂T ‖2 ≤ ‖f −RT ‖2 + ‖R̂T −RT ‖L∞([−1,1]dmax ) ≤ (2−T +Q(T ))‖f‖Fγp,θ ,
where Q(T ) =  2 −(1−vα)T (1 ≤ θ ≤ 2), 2−(1−vα ′)T [∑
T≤γ′(s) 2 2θ θ−2 (γ
′(s)−γ(s)) ]1−2/θ
(θ > 2). Noting that
2−T . Q(T ), we have that ‖f − R̂T ‖2 . Q(T )‖f‖Fγp,θ .
Finally, we evaluate the network size to achieve this approximation error. Since R̂T is the linear
combination of neural network φ×
( ψ̂l1√
2 , . . . , ψ̂ldmax√ 2
) , by putting
L = Lφ̂ + L× + 1,
W = 21dmaxG(T, γ),
S = (212dmaxLφ̂ + L×W 2 × + 1)G(T, γ), B = max{( √ 2)dmaxBf , B×, C2},
we have that R̂T ∈ Φ(L,W, S,B). Substituting Eq. (10) to L× and Lφ̂, we can evaluate as
Lψ̂ = C1
⌈( log 1 )2 + log(fmax) + 2 ⌉
= C1 ⌈( T log 2 + dmax log √ 2 + logS(γ, T ) + logBf + log dmax + 1 )2 + log fmax ⌉ ≤ ⌈ C1 (6 max{logBf , log 2})2 ⌉ ⌈( max{d2max, T 2, (logS(γ, T )) 2 , log fmax, 2}
)⌉ and
L× =
⌈ log ( 3dmax + 5 )⌉ dlog dmaxe
≤ ⌈ max { log ( 3dmax ) , log 5 } + log 2 ⌉ dlog dmaxe
≤ d6 max{logBf , log 5}e dmax{dmax, T, logG(T, γ)}e dlog dmaxe . Therefore, if we set K = 2 max { d6 max {logBf , log 5}e , ⌈ C1 (6 max {logBf , log 2})2 ⌉} , then
it holds that L ≤ 2K max { d2max, T 2, (logG(T, γ))2, log fmax } ,
and thus we also have
S = (212dmaxLφ̂ + L×W 2 × + 1)G(T, γ) ≤ 2K(212dmax + 36d2max) max { d2max, T 2, (logG(T, γ))2, log fmax } G(T, γ)
≤ 4× 212Kd2max max { d2max, T 2, (logG(T, γ))2, log fmax } G(T, γ).
For the setting of 2 < θ, we can prove the bound by the same procedure. Thus, we obtain the assertion.

heading: E PROOF OF THEOREM 9
text: 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 = (ai)∞i=1 and a′ = (a′i)∞i=1 are positive monotonically non-decreasing sequences such that 1 ≤ a1 = a′1 and
∞∏ i=2
1
1− 2−(ai−a1) <∞, ∞∏ i=2
1
1− 2−β(ai−a′i) <∞,
for a positive constant β > 0. Then we have the following inequalities:
∑ s∈N∞0 :〈a′,s〉≥T 2−β〈a,s〉 ≤ (1− 2−β)−1 ( ∞∏ i=2
1
1− 2−β(ai−a′i)
) 2−βT (21)
and ∑ s∈N∞0 :〈a,s〉<T 2s ≤ 8 ( ∞∏ i=2
1
1− 2−(ai−a1)
) 2T . (22)
Proof. First, note that∑ s∈N∞0 :〈a′,s〉≥T 2−β〈a,s〉
= ( ∞∑ s1=0 2−βs1 ) ×  ∑ (si)∞i=2∈N∞0 : ∑∞ i=2 a ′ isi≥T 2−β ∑∞ i=2 aisi  +
∑ (si)∞i=2∈N∞0 : ∑∞ i=2 a ′ isi<T 2−β ∑∞ i=2 aisi  ∑ s1∈N∪{0}:s1≥T− ∑∞ i=2 a ′ isi 2−βs1  . (23) If T satisfies ∑∞ i=2 a
′ isi < T , then we have that∑ s1∈N∪{0}:s1≥T− ∑∞ i=2 a ′ isi 2−βs1 = 2−βT 2β ∑∞ i=2 a ′ isi 1− 2−β .
Thus, the second term of the right hand side of Eq. (23) can be evaluated as 2−βT (1− 2−β)−1 ∑
(si)∞i=2∈N∞0 : ∑∞ i=2 a ′ isi<T
2−β ∑∞ i=2(ai−a ′ i)si .
Next, we evaluate the first term of the right hand side of Eq. (23). We see that ∞∑ s1=0 2−βs1 = (1− 2−β)−1,
and ∑ (si)∞i=2∈N∞0 : ∑∞ i=2 a ′ isi≥T 2−β ∑∞ i=2 aisi
≤ ∑
(si)∞i=2∈N∞0 : ∑∞ i=2 a ′ isi≥T
2−β ∑∞ i=2(ai−a ′ i)si2−β ∑∞ i=2 a ′ isi
≤2−βT ∑
(si)∞i=2∈N∞0 : ∑∞ i=2 a ′ isi≥T
2−β ∑∞ i=2(ai−a ′ i)si .
Thus the first term of the right hand side of Eq. (23) can be bounded by 2−βT (1− 2−β)−1 ∑
(si)∞i=2∈N∞0 : ∑∞ i=2 a ′ isi≥T
2−β ∑∞ i=2(ai−a ′ i)si .
Hence, by noticing that∑ s∈N∞0 2−β ∑∞ i=2(ai−a ′ i)si = ∞∏ i=2 ( ∞∑ si=0 2−β(ai−a ′ i)si ) = ∞∏ i=2
1
1− 2−β(ai−a′i) ,
and combining the evaluations above, Eq. (23) yields that∑ s∈N∞0 :〈a′,s〉≥T 2−β〈a,s〉 ≤ 2−βT (1− 2−β)−1 ∞∏ i=2
1
1− 2−β(ai−a′i) ,
which yields the first inequality. Next, we show the second inequality. We decompose ∑ s∈N∞0 :〈a,s〉<T 2s as ∑T t=0 It where It is defined as It :=
∑ s∈N∞0 :t−1≤〈a,s〉<t 2 ∑∞ i=1 si .
Here, for 1 ≤ t ≤ T , we can evaluate It as It ≤ 22t ∑ s∈N∞0 :t−1≤〈a,s〉<t 2 ∑∞ i=1 si−2〈a,s〉
≤ 22t ∑
s∈N∞0 :t−1≤〈a,s〉<t
2− ∑∞ i=1(2ai−1)si .
Since ai ≥ 1, we have ai ≤ 2ai− 1 (i ≥ 1) and thus by Eq. (21) with a′i = a1 (∀i ∈ N) and β = 1, we have ∑
s∈N∞0 :t−1≤〈a,s〉<t
2− ∑∞ i=1(2ai−1)si ≤ ∑ s∈N∞0 :t−1≤〈a,s〉<t 2−〈a,s〉
≤ ∑
s∈N∞0 :t−1≤〈a′,s〉
2−〈a,s〉
≤ 4 ( ∞∏ i=2
1
1− 2−(ai−a1)
) 2−t,
where we used the first assertion (21) in the last inequality. Therefore, we can obtain
It ≤ 22t ∑
s∈N∞0 :t−1≤〈a,s〉<t
2− ∑∞ i=1(2ai−1)si ≤ 4 ( ∞∏ i=2
1
1− 2−(ai−a1)
) 2t.
Now using this bound, we can verify that∑ s∈N∞0 :〈a,s〉<T 2s ≤ 8 ( ∞∏ i=2
1
1− 2−(ai−a1) ) T∑ t=0 2t
≤ 8 ( ∞∏ i=2
1
1− 2−(ai−a1)
) 2T ,
which yields the second assertion (22).
Now, we are ready to show Theorem 9. First, we give the proof in the setting of γ(s) = 〈a, s〉.
Proof for mixed smoothness (γ(s) = 〈a, s〉). First, we consider the setting 1 ≤ θ ≤ 2. Lemma 18 yields
G(T, γ) = ∑
s∈N∞0 :〈a,s〉<T
2s = ∑
s∈N∞0 :〈 a a1 ,s〉< Ta1
2s ≤ 8 ( ∞∏ i=2
1
1− 2 −(ai−a1) a1
) 2 T a1 . (24)
Moreover, we can easily see that
α = sup s∈N∞0
∑∞ i=1 si 〈a, s〉 = 1 a1 ,
because a is a positive monotonically non-decreasing sequence. By the assumption ai = Ω(iq),
dmax ∼ T 1/q, fmax ∼ T
are satisfied. Now, by using the filter w ∈ RC×1×W ′ with the width W ′ = dmax, the number of output channels C = dmax and the number of input channels C ′ = 1 given by
wi,1,j =
{ 1 (i = j),
0 (i 6= j),
for i, j ∈ [dmax], we can see that
(Conv1,w(X))1 =  x1... xdmax  . By Theorem 7, if we set
L = 2K max { T 2 q , T 2 } ,
W = 21 ( ∞∏ i=2
1
1− 2 −(ai−a1) a1
) T 1 q 2 T a1 ,
S = 1764K ( ∞∏ i=2
1
1− 2 −(ai−a1) a1
) T 2 q max { T 2 q , T 2 } 2 T a1 ,
B = ( √ 2)dmaxK ′,
where K,K ′ > 0 are constants, for any function f ∈ U(F 〈a,s〉p,θ ), there exists a neural network R̂T ∈ Φ(L,W,S,B) such that
f ′(X) := R̂T (x1, . . . , xdmax)
satisfies ‖f ′ − f‖2 ≤ 2−(1− v a1 )T .
Since f ′(X) = ( R̂T ◦ Conv1,w(X) ) 1 , we can see that f ′ is a dilated CNN: f ′ ∈ P(L′, B′,W ′, C, L,W,B, S) where L′ = 1, B′ = 1 and W ′ = C = dmax. Next, we consider the setting 2 < θ. Let a′1 = a1 2 , and for δ = a2 − a1 (which is positive by the assumption a2 > a1) and a constant u that satisfies 2 < u < 2+ 2δa1 , we set a ′ i = ai u for i ≥ 1. Then, a′1 < a ′ 2 ≤ . . . is satisfied, that is, a′ = (a′i)∞i=1 is a positive monotonically increasing sequence. Moreover, by the assumption ai = Ω(iq), it holds that, for all c > 0, ∞∏ i=2 1 1− 2 −c ( ai a1 − 2a′ i a1 ) = ∞∏ i=2 1 1− 2−c ( 1 a1 − 2ua1 ) ai <∞. (25)
By noticing that 2(a ′ i−ai) a1
= 2 (
1 u − 1 ) ai a1 ≤ − aia1 where we used u > 2, we also have that∑
s∈N∞0 :〈a′,s〉≥T
2 2θ θ−2 〈a ′−a,s〉 ≤ ∑
s∈N∞0 :〈2a′/a1,s〉≥2T/a1
2− a1θ θ−2 〈a/a1,s〉.
Moreover, since we have verified Eq. (25), we can apply Lemma 18 to the right hand side of this inequality and it can be further bounded as∑
s∈N∞0 :〈2a′/a1,s〉≥2T/a1
2− a1θ θ−2 〈a/a1,s〉 ≤ 2− 2θ θ−2T .
By setting γ′(s) = 〈a′, s〉 and using Theorem 7, we can see that if we define the set of CNN P by the same argument as the case of 1 ≤ θ ≤ 2, for all f ∈ U(Fγp,θ), there exists a dilated CNN f ′ ∈ P such that
‖f ′ − f‖2 . 2−(1−vα(γ ′))T (2− 2θ θ−2T )1/2−1/θ = 2−2(1− v a1 )T
is satisfied, where we used α(γ′) = 2a1 by the definition of a ′. Here, as in Eq. (24), we have that
G(T, γ′) ≤ 8  ∞∏ i=2
1
1− 2 −(a′ i −a′1) a′1  2 Ta′1 ≤ 8( ∞∏ i=2
1
1− 2 −(ai−a1) a1
) 2 2T a1 .
Therefore, by resetting T ← 2T , we obtain the same result as in 1 ≤ θ ≤ 2.
Proof for anisotropic smoothness (γ(s) = maxi{aisi}i). Here, we consider the setting of mixed smoothness γ(s) = maxi{aisi}i. We note that
α(γ) = sup s∈N∞0
∑∞ i=1 si
supi{aisi} ≤ sup s∈R∞>0
∑∞ i=1 si
supi{aisi}
= sup T>0 sup {s∈R>0:maxi{aisi}=T}
∑∞ i=1 si T .
The condition supi{aisi} ≤ T is equivalent to the condition that si ≤ Tai for all i ∈ N, the right hand side can be further bounded as
α(γ) ≤ ∞∑ i=1 1 ai .
Therefore, in the setting of 1 ≤ θ ≤ 2, Theorem 7 with α = ∑∞ i=1 1 ai yields that
‖RT (f)− f‖2 ≤ 2−(1−δα)T ‖f‖Fγp,θ .
Since it holds that
∑ s∈N∞0 :γ(s)<T 2s ≤ ∞∏ i=1
d T ai e∑
si=0
2si  ≤ 2∑∞i=1d Tai e, G(T, γ) . 2 ∑∞ i=1d T ai e is satisfied. By noticing that a is a positive monotonically increasing sequence with polynomial order growth, the same argument as in the setting of γ(s) = 〈a, s〉 can be applied. Then, we obtain the assertion.

heading: F PROOF OF THEOREM 10
text: The estimation error 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).
Definition 19 (Covering number). For a norm space F equipped with a norm ‖ · ‖, the -covering number N (F , , ‖ · ‖) the minimum number of balls with radius (measured by the norm ‖ · ‖) to cover the norm space F:
N (F , δ, ‖ · ‖) := inf{n ∈ N : ∃(f1, . . . , fn) ∈ Fn, ∀f ∈ F , ∃i ∈ [n], ‖fi − f‖ ≤ }.
The covering number of the model of the dilated CNNs can be evaluated as in the following lemma. Lemma 20. The log-covering number of the set of the dilated CNNs P(L′, B′,W ′, C ′, L,W,B, S) can be bounded as
logN (P, δ, ‖ · ‖∞) . (S +W ′C ′)(L+ L′) log ( LL′(B′ ∨ 1)(B ∨ 1)C ′W ′W
δ
) .
Proof. The assertion can be shown by evaluating how strongly a small perturbation of parameters can deviate the function. For w ∈ RC′×W ′ and h ∈ N, we have that
‖w ?h X − w′ ?h X‖∞ ≤ ‖(w − w′) ?h X‖∞ ≤W ′C‖w − w′‖∞‖X‖∞, ‖w ?h X − w ?h X ′‖∞ ≤W ′C ′‖w‖∞‖X −X ′‖∞.
Therefore, for F, F ′ ∈ RC′×C′×W ′ , we have ‖Convh,F ◦X − Convh,F ′ ◦X‖∞ = max
i∈[C′] ‖(Fi,:,: ?h X)− (F ′i,:,: ?h X)‖∞
≤W ′C ′ (
max i∈[C′]
‖Fi,:,: − F ′i,:,:‖∞ ) ‖X‖∞
= W ′C ′‖F − F ′‖∞‖X‖∞, (26) ‖Convh,F ◦X − Convh,F ◦X ′‖∞ ≤ max
i∈[C′] ‖(Fi,:,: ?h X)− (Fi,:,: ?h X ′)‖
≤W ′C ′ (
max i∈[C′]
‖Fi,:,:‖∞ ) ‖X −X ′‖∞
≤W ′C ′‖F‖∞‖X −X ′‖∞. (27) Here, for CNNs f, g such that
f(X) = ConvW ′L′ ,FL′ ◦ · · · ◦ ConvW ′l,Fl ◦ · · · ◦ Conv1,F1 ◦X, g(X) = ConvW ′L′ ,F ′
L′ ◦ · · · ◦ ConvW ′l,F ′l ◦ · · · ◦ Conv1,F ′1 ◦X,
we define
Al(f)(X) := ConvW ′l−1,Fl−1 ◦ · · · ◦ Conv1,F1 ◦X, Bl(g)(X ′) := ConvW ′L′ ,F ′
L′ ◦ · · · ◦ ConvW ′l+1,F ′l+1 ◦X
′,
where A1(f)(X) = BL′(f)(X) = X . By using these notation and the triangle inequality, we can see that it holds that
‖f(X)− g(X)‖∞
≤ L′∑ l=1 ‖Bl(g) ◦ ConvW ′l,Fl ◦ Al(f)(X)− Bl(g) ◦ ConvW ′l,F ′l ◦ Al(f)(X)‖∞.
Hence, by applying the inequalities (27) and (26), we can see that
‖f(X)− g(X)‖∞ ≤ L′(W ′C ′)L ′ ‖X‖∞  L′∏ i=1 ‖Fi‖∞  max l=1,...L′ ‖Fl − F ′l ‖∞
≤ L′(W ′C ′B′)L ′
max l=1,...L′
‖Fl − F ′l ‖∞.
Now, for fFNN ∈ Φ(L,W,B, S), we have
|fFNN(x)− fFNN(x′)| ≤ (BW )L‖x− x′‖∞,
and thus we also have
‖fFNN ◦ f(X)− fFNN ◦ g(X)‖∞ ≤ L′(BW )L(TC ′B′)L ′
max l=1,...L′
‖Fl − F ′l ‖∞.
On the other hands, fFNN, gFNN ∈ Φ(L,W,B, S) can be represented as
fFNN(x) = (ALη(·) + bL) ◦ · · · ◦ (Alη(·) + bl) ◦ · · · ◦ . . . (A1x+ b1), gFNN′(x) = (A ′ Lη(·) + bL) ◦ · · · ◦ (A′lη(·) + b′l) ◦ · · · ◦ . . . (A′1x+ b′1).
Then, by noticing that ‖g(X)‖∞ ≤ (W ′C ′)L ′ , the same argument as Lemma 3 of Suzuki (2019) yields that, if
max l=1,...,L
max {‖Al −A′l‖∞, ‖bl − b′l‖∞} ≤ δ, (28)
then the L∞ distance between the composite functions fFNN ◦ g and gFNN′ ◦ g can be bounded as
‖fFNN ◦ g(X)− gFNN′ ◦ g(X)‖∞ ≤ δL(W ′C ′)L ′ {(B + 1)(W + 1)}L.
Since the triangle inequality yields
‖FNN◦f(X)−FNN′◦g(X)‖∞ ≤ ‖FNN◦f(X)−FNN◦g(X)‖∞+‖FNN◦g(X)−FNN′◦g(X)‖∞,
by combining these inequalities, under the condition (28) and maxl=1,...L′ ‖Fl − F ′l ‖∞ ≤ δ, we obtain
‖FNN ◦ f(X)− FNN′ ◦ g(X)‖∞ ≤ δL′(BW )L(W ′C ′B′)L ′ + δL(W ′C ′)L ′ {(B + 1)(W + 1)}L.
Therefore, by noticing that the number of combinations of non-zero parameter configurations in Φ(L,W,B, S) is bounded by (W + 1)LS , we can again utilize the same argument as Lemma 3 of Suzuki (2019) to we obtain
logN (P, δ, ‖ · ‖∞) . (S +W ′C ′)(L+ L′) log ( LL′(B′ ∨ 1)(B ∨ 1)C ′W ′W
δ
) .
Using a covering number bound of a model, a standard analysis of the ERM estimator gives the following bound on its estimation error.
Lemma 21 (Theorem 2.6 of Hayakawa & Suzuki (2020); Schmidt-Hieber (2020)). Let f̂ be any ERM estimator that takes its value in a model F ⊂ L∞([0, 1]∞). Suppose that there exists a constant F > 0 such that ‖f◦‖∞ ≤ F and ‖f‖ ≤ F for any f ∈ F . Then for any 0 < δ < 1 satisfying N (F , δ, ‖ · ‖∞) ≥ 3, it holds that
EPn [‖f̂ − f◦‖2PX ] ≤ 4 inff∈F ‖f − f ◦‖2PX + C
( (F + σ)
N (F , δ, ‖ · ‖∞) n + δ(F + σ)
) ,
where C is a universal constant.
Since we have assumed PX is absolutely continuous to the Lebesgue measure λ∞ and ‖ dPXdλ∞ ‖∞ < ∞, ‖·‖PX in the right hand side can be replaced by ‖·‖2 with a constant factor multiplication. Now, we are ready to show Theorem 10.
Proof of Theorem 10 First, we consider the setting of γ(s) = 〈a, s〉. By Theorem 9, by setting
L′ = 1,
B′ = 1,
W ′ ∼ T 1 q ,
C ′ ∼ T 1 q , L ∼ max { T 2 q , T 2 } ,
W ∼ ( ∞∏ i=2
1
1− 2 −(ai−a1) a1
) T 1 q 2 T a1 ,
S ∼ ( ∞∏ i=2
1
1− 2 −(ai−a1) a1
) T 2 q max { T 2 q , T 2 } 2 T a1 ,
B ∼ ( √ 2)T 1 q ,
we have that, for any f◦ ∈ U(Fγp,θ), there exists a dilated CNN f ∈ P(L′, B′,W ′, C ′, L,W,B, S) such that ‖f − f◦‖22 ≤ 2−2(1−v/a1)T . Moreover, by Lemma 20, the covering number of P can be bounded as
log (N (P, δ, ‖ · ‖∞)) . ( ∞∏ i=2
1
1− 2 −(ai−a1) a1
) 2 T a1 T 2 q+1 max { T 4 q , T 4 } log ( T
δ
) .
Here, under the assumption ‖f◦‖∞ ≤ Bf , we can also obtain that there exists f ∈ P̄(Bf , L′, B′,W ′, C ′, L,W,B, S) such that ‖f − f◦‖22 ≤ 2−2(1−v/a1)T , and a covering number evaluation log ( N (P̄, δ, ‖ · ‖∞) ) ≤ log (N (P, δ, ‖ · ‖∞)). Therefore, by Lemma 21, the ERM estimator f̂ taking its value in P̄(Bf , L′, B′,W ′, C, L,W,B, S) satisfies
EPn [‖f̂ − fo‖2PX ]
. 2−2(1− v a1 )T + (B2f + σ 2)
∏∞ i=2
1
1−2 −(ai−a1) a1 2 Ta1 T 2q+1 max{T 4q ,T 4} log(Tδ ) n + δ(Bf + σ).
Thus, by taking T to satisfy 2 T a1 = n 1 2(a1−v)+1 and letting δ = 1n , we obtain that
EPn [‖f̂ − fo‖2PX ] . ( ∞∏ i=2
1
1− 2 −(ai−a1) a1
) n − 2(a1−v) 2(a1−v)+1 (log n) 2 q+2 max{(log n) 4 q , (log n)4},
which yields the first assertion.
Next, we consider the setting of γ = maxi{aisi}i. We again apply Theorem 9 so that, by setting
L′ = 1,
B′ = 1,
W ′ ∼ T 1 q ,
C ′ ∼ T 1 q , L ∼ max { T 2 q , T 2 } ,
W ∼ T 1 q 2T/ã,
S ∼ T 2 q max { T 2 q , T 2 } 2T/ã,
B ∼ ( √ 2)T 1 q ,
we have that, for any f◦ ∈ U(Fγp,θ), there exists a dilated CNN f ∈ P(L′, B′,W ′, C ′, L,W,B, S) such that ‖f − f◦‖22 . 2−2(1−v/ã)T . Therefore, by the same argument as the setting of mix smoothness, we can verify
EPn [‖f̂ − fo‖2PX ] . − 2(ã−v) 2(ã−v)+1 (log n) 2 q+2 max{(log n) 4 q , (log n)4},
which yields the second assertion.

heading: G PROOFS OF THEOREMS 13 AND 14
text: First, we prove the following lemma.
Lemma 22. Let X = (xi)∞i=1 ∈ R∞. For any sequence (xi1 , . . . , xiN ) satisfying ij ≤ HL ′
with arbitrary integer H > 1 and i1 < i2 < · · · < iN , there exists a dilated CNN where the number of layers is L′, the width of filters is H , the number of channels of each layer is N and the filters Wl ∈ RN×N×H (2 ≤ l ≤ T ) and W1 ∈ RN×H in each layer satisfy ‖Wl‖∞ ≤ 1 (l = 1, . . . , L′) such that
(xi1 , . . . , xiN ) > = ( ConvHL′−1,WL′ ◦ · · · ◦ ConvHl−1,Wl ◦ · · · ◦ Conv1,W1 ◦X ) 1 .
Proof. Let Al(X) = ConvHl−1,Wl ◦ · · · ◦ Conv1,W1 ◦X.
First, we let (W1)k,j = 1 if (ik − 1 mod T ) = j − 1 and (W1)k,j = 0 otherwise, for k ∈ [N ] and j ∈ [T ]. Then, for each k ∈ [N ], there exists i(1)k ∈ [HL
′−1] such that A1(X)k,(i(1)k −1)H+1 = xik ,
indeed, i(1)k can be obtained as i (1) k = b(ik − 1)/Hc+ 1. In the following, we recursively define Wl and i(l)k for l = 2, . . . , L ′ so that
Al(X)k,(i(l)k −1)Hl+1 = xik (k ∈ [N ]) (29)
is satisfied. We remark that this is satisfied for l = 2. Suppose that, for l, we have Wl and i (l) k that satisfy the condition (29). If we define
A′l,i:(X) := ( Al(X):,(i−1)Hl+1+(j−1)Hl+1 )∞ j=1 ∈ RN×∞
for i ∈ N, then we have that
Al+1(X):,(i−1)Hl+1+1 = (ConvHl,Wl+1 ◦ Al(X)):,(i−1)Hl+1+1
=  (Wl+1)1,:,: ?1 A ′ l,i:(X)
... (Wl+1)N,:,: ?1 A′l,i:(X)  1 .
Therefore, by letting i(l+1)k as i (l+1) k = b(i (l) i − 1)/Hc + 1 (i.e., the integer such that (i (l+1) k − 1)H + 1 ≤ i(l)k < i (l+1) k H) and setting Wl+1 so that (Wl+1)k,j = 1 if (i (l) k − 1 mod T ) = j − 1 and (Wl+1)k,j = 0 otherwise (k ∈ [N ] and j ∈ [T ]), we can see that the condition (29) (Al+1(X)k,(i(l+1)k −1)T l+1+1 = xik for all k ∈ [N ]) holds for l + 1. Therefore, by the inductive argument, we have that
AL′(X):,1 = (xik)Nk=1,
because i(L ′) k satisfies 0 ≤ i (L′) k − 1 ≤ (ik − 1)/HL ′ which yields i(L ′) k = 1 for all k ∈ [N ] by the assumption ik ≤ HL ′ .
A pictorial illustration of the proof of Lemma 22 with H = W ′, N = C ′ and L′ = 2 is given in Figure 1.
Proofs of Theorems 13 and 14.
Let (i j )1j =1 be the sequence of indices that yieldsai 1 < a i 2 < for the given positive sequence a = ( ai )1i =1 . We only give the proof for the mixed smoothness setting (s) = ha; si . As for the anisotropic smoothness setting, the same reasoning can be applied.
Sincekakwl q 1 is satis ed by the assumption, we haveai j j q for all j 2 N. Therefore, we can verify that for allT > 0, it holds that
I (T; ) = f i : 9s 2 N10 ; si 6= 0 ; ha; si Tg
= n i j : 1 j T 1 q o :
Hence, we can see thatdmax = T 1 q ; f max = T 1 q by their de nitions. Sinceai = (log i ), there exists a constantQ > 0 such that ai Q log i
for all i 2 [N ]. Then, ifai T , i exp T Q is satis ed. By using Lemma 22 withN = dmax , we can construct the dilated convolutional structure
Conv 3d
T Q e 1 ;W dTQ e
Conv1;W 1 X
that extracts all of the elements inI (T; ). In particular, for a fully connected neural network̂RT with dmax dimensional input, we have that
0
@R̂T Conv 3d
T Q e 1 ;W dTQ e
Conv1;W 1 X
1
A
1
= R̂T ((x i : i 2 I (T; ))) ; (32)
that is, the convolutional neural network in the right hand side depends only on the elements in I (T; ).
On the other hand, by Lemma 18, we have that∑ s∈N∞0 :〈a,s〉<T 2s = ∑ s∈N∞0 : ∑∞ j=1 aij sij<T 2s
. ∏ i 6=i1
1
1− 2− (ai−ai1 ) ai1  2 Tai1 . Therefore, by Theorem 7, if we set
L ∼ max{T 2 q , T 2}, W ∼ 21  ∏ i 6=i1
1
1− 2− (ai−ai1 ) ai1 T 1q 2 Tai1 , S ∼
∏ i 6=i1
1
1− 2− (ai−ai1 ) ai1 maxT 2q {T 2q , T 2}2 Tai1 , B ∼ √2T 1q , there exists a neural network R̂T ∈ Φ(L,W,B, S) such that f ′(X) = R̂T ((xi : i ∈ I(T, γ)) satisfies
‖f ′ − fo‖2 ≤ 2 −(1− vai1 )T . (35)
Therefore, by combining Eq. (32) and Eq. (35), we can set
L′ =
⌈ T
Q
⌉ ∼ T, W ′ = 3, C ′ = T 1 q , B′ = 1,
and (L,W, S,B) as above so that there exists f ′ ∈ P(L′, B′,W ′, C ′, L,W,B, S) such that
‖f ′ − f‖2 ≤ 2 −(1− vai1 )T .
This yields the proof of Theorem 13.
The remaining proof for the estimation error (Theorem 14) can be done in the same manner as that of Theorem 10, which yields Theorem 14.

heading: H NUMERICAL EXPERIMENTS
text: H.1 THE EXPERIMENT OF DIMENSION INDEPENDENCE
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:
1. Smoothness with Polynomial order increase: We consider the following function as the true function:
f◦(x) = d∑ k=1 √ 2 k∑k i=1 2 ip k∏ i=1 cos (2πxi),
where p, d ∈ N are parameters. Data generation model: yi = f◦(xi) (i = 1, . . . , n). Parameter settings: n = 128, p = 1.2, 2.0, 3.0, 4.0, 5.0, d = 100, 200, 500, 1000. The trained model: CNN with the kernel widthW ′ = 10, the number of channels C ′ = 10, and the depth L′ = 1.
2. Smoothness with sparse structure: We consider the following function as the true function:
f◦(x) = [d/10]∑ k=1 √ 2 k∑k i=1 2 ip k∏ i=1 cos (2πx10i),
where p, d ∈ N are parameters. Data generation model: yi = f◦(xi) (i = 1, . . . , n). Parameter setting: n = 128, p = 1.2, 2.0, 3.0, 4.0, 5.0, 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 n observations (xi, yi)ni=1 using a 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 theoretical upper bound is dimension independent and depends only on smoothness. Moreover, in the setting of sparse smoothness, we again observe that the estimation error is dimension-independent by using dilated CNN, which is also consistent with our theoretical findings.

heading: I EXTENSION OF 2D CONVOLUTION
text: Here, we present that a similar argument can be applied to 2D convolution for image inputs. For that purpose, we consider a quite simple setting where the true function fo has a mixed/anisotropic smoothness with respect to the wavelet coefficients of the input image. More precisely, suppose that the input image X has size N × N where N = 2K for an integer K (X ∈ [0, 1]N×N ) and let (αk,j)3(N/2 k)2
j=1 for k ∈ K be the wavelet coefficient at the level k. Then, we assume the true function is γ-smooth with respect to the wavelet coefficients (α1,1, α1,2, . . . , α1,3(N/2)2 , α2,1, . . . , α2,3(N/22), . . . , αK,1) ∈ RN 2
. Usually, N2 is large and a standard analysis suffers from the curse of dimensionality.
The construction of wavelet coefficients is as follows (see Daubechies (1992) for more details). The wavelet transform is obtained based on a pair of a wavelet filter ϕ ∈ RN and scaling filter ψ ∈ RN . We assume this pair of filters are given. For u ∈ RM1 and v ∈ RM2 , let
u⊗ v :=  u1v1 . . . u1vM2... . . . ... uM1v1 . . . uM1vM2  ∈ RM1×M2 , and for x, y ∈ RM1×M2 , let
〈x, y〉 := M1∑ i=1 M2∑ j=1 xi,jyi,j .
The level k wavelet and scaling bases are obtained by
ϕ (k) i = 2k−1∑ j=1 ϕi+(j−1)N/2k−1 , ψ (k) i = 2k−1∑ j=1 ϕi+(j−1)N/2k−1 (i = 1, . . . , N/2 k−1).
We apply a shift operation on these basis functions as ϕ(k,j) = ( ϕ (k)
[(i−1+2(j−1)) mod (N/2k−1)]+1 )N/2k−1 i=1 ∈ RN/2 k−1 (j = 1, . . . , N/2k),
and we define ψ(k,j) in the same way. Using these filter, we can calculate the wavelet coefficients in an inductive manner. At the first level, we obtain
α (1,1) i,j = 〈ϕ (1,i) ⊗ ϕ(1,j), X〉 (i, j ∈ [N/2]),
α (1,2) i,j = 〈ϕ (1,i) ⊗ ψ(1,j), X〉 (i, j ∈ [N/2]),
α (1,3) i,j = 〈ψ (1,i) ⊗ ϕ(1,j), X〉 (i, j ∈ [N/2]),
α (1,4) i,j = 〈ψ (1,i) ⊗ ψ(1,j), X〉 (i, j ∈ [N/2]).
Let A(1,q) = (α(1,q)i,j )i,j for q = 1, 2, 3, 4. At the k-th level, we assume that we have already have A(k−1,q) ∈ RN/2k−1 (q ∈ [4]). Then, the k-th level coefficients can be obtained by α
(k,1) i,j = 〈ϕ (k,i) ⊗ ϕ(k,j), A(k−1,1)〉 (i, j ∈ [N/2k]),
α (k,2) i,j = 〈ϕ (k,i) ⊗ ψ(k,j), A(k−1,1)〉 (i, j ∈ [N/2k]),
α (k,3) i,j = 〈ψ (k,i) ⊗ ϕ(k,j), A(k−1,1)〉 (i, j ∈ [N/2k]),
α (k,4) i,j = 〈ψ (k,i) ⊗ ψ(k,j), A(k−1,1)〉 (i, j ∈ [N/2k]).
We again let A(k,q) = (α(k,q)i,j )i,j for q = 1, 2, 3, 4. Then, we obtain the wavelet coefficient as A(X) = (A(k,2), A(k,3), A(k,4))K−1k=1 in a recursive manner that represents strength of each frequency component k of the input image X at each location j. We assume that the true function fo is γ-smooth with respect to this coefficient (more precisely its vectorization vec(A(X)) ∈ RN2 ). Assumption 23. The true function fo : RN×N → N is γ-smooth with respect to vec(A(X)). The smoothness satisfies the sparsity (Assumption 12). Moreover, we also assume Assumptions 3 is satisfied.
From now on, we construct a 2D-CNN structure to extract variables in I(T, γ) from vec(A(X)). Suppose that the support of ϕ and ψ are included in the first H components, then the inner product appeared above are executable just in a 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 7. If we can show that a CNN can extract variables included in I(T, γ), then we can apply the same argument to Theorems 13 and 14.
Let the number of channels of of 2D convolution be Ck = dmax + 4 for k = 1, . . . ,K and C0 = 1. For each layer k ∈ [K − 1], we will define a filter W (k) ∈ RCk×Ck−1×Hk×Hk where Hk = min{H,N/2k}. Let Ak(X) ∈ RCk×N/2
k×N/2k be the output from the k-th layer of the CNN. Then, Ak(X) is updated by the following convolution with the interval h = 2: A0(X) = X and
Ak(X)q,i,j = Hk∑ i1=1 Hk∑ j1=1 Ck−1∑ q1=1 Ak−1(X)q1,2(i−1)+i1,2(j−1)+j1W (k) q,q1,i1,j1 (q ∈ Ck, i, j ∈ [N/2k]), where, by convention, we letAk−1(X)i,j = Ak−1(X)(i−1 mod N/2k−1)+1,(j−1 mod N/2k−1)+1 for i and j which are out of the range {1, . . . , N/2k−1}.
Next, we show that an appropriately defined filter can extract I(T, γ). First, we let a part of W (k) as follows to extract (A(k,1), A(k,2), A(k,3), A(k,4)):
W (k) 1,1,:,: = ϕ1:Hk ⊗ ϕ1:Hk ,
W (k) 2,1,:,: = ϕ1:Hk ⊗ ψ1:Hk ,
W (k) 3,1,:,: = ψ1:Hk ⊗ ϕ1:Hk ,
W (k) 4,1,:,: = ψ1:Hk ⊗ ψ1:Hk ,
where xi:i′ = (xi, xi+1, . . . , xi′)> for a vector x.
Second, for k ≥ 2, we extract the “important coefficients” included in I(T, γ)from (A(k−1,2), A(k−1,3), A(k−1,4)) that are already extracted in the last layer. For that purpose, let W
(k) j,q,i1,j1 = 1 for 2 ≤ q ≤ 4, j ≥ 5 and i1, j1 ∈ [2] if A(k−1,q) contains the (j − 4)-th element of I(T, γ) at its (i1, j1)-th component. Otherwise, let W (k) j,q,i1,j1 = 0.
Finally, we extract the important coefficients included in Ak−1(X)q,:,: for q ≥ 5. For 5 ≤ q ≤ N , let Wj,q,i1,i2 = 1 for j ≥ 5 and i1, j1 ∈ [2] if Ak−1(X)q,:,: contains the (j − 4)-th element of I(T, γ) at its (i1, j1)-th component. Otherwise, we let Wj,q,i1,i2 = 0.
Since the interval of convolution is h = 2, the size of AK(X) is CK × 1× 1 which can be seen as a “vector.” By the construction above, it contains all coefficients included in I(T, γ). Therefore, by feeding X̃ = vec(AK(X)) to an FNN R̂T as considered in the proof of Theorems 13 and 14, we obtain the same approximation and estimation error bounds as those theorems under Assumption 23. Here, note that the number of parameters in the CNN constructed above has the same order as the 1D-situation thanks. Thus, we obtain the same convergence rate as Theorems 13 and 14.

Review summaries:
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). The 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. For 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).

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.