Year: 2018

Abstract:
We develop new approximation and statistical learning theories of convolutional neural networks (CNNs) via the ResNet-type structure where the channel size, filter size, and width are fixed. It is shown that a ResNet-type CNN is a universal approximator and its expression ability is no worse than fully-connected neural networks (FNNs) with a block-sparse structure even if the size of each layer in the CNN is fixed. Our result is general in the sense that we can automatically translate any approximation rate achieved by block-sparse FNNs into that by CNNs. Thanks to the general theory, it is shown that learning on CNNs satisfies optimality in approximation and estimation of several important function classes. As applications, we consider two types of function classes to be estimated: the Barron class and Hölder class. We prove the clipped empirical risk minimization (ERM) estimator can achieve the same rate as FNNs even the channel size, filter size, and width of CNNs are constant with respect to the sample size. This is minimax optimal (up to logarithmic factors) for the Hölder class. Our proof is based on sophisticated evaluations of the covering number of CNNs and the nontrivial parameter rescaling technique to control the Lipschitz constant of CNNs to be constructed.

heading: 1 INTRODUCTION
text: Convolutional Neural Network (CNN) is one of the most popular architectures in deep learning research, with various applications such as computer vision (Krizhevsky et al. (2012)), natural language processing (Wu et al. (2016)), and sequence analysis in bioinformatics (Alipanahi et al. (2015), Zhou & Troyanskaya (2015)). Despite practical popularity, theoretical justification for the power of CNNs is still scarce from the viewpoint of statistical learning theory.
For fully-connected neural networks (FNNs), there is a lot of existing work, dating back to the 80’s, for theoretical explanation regarding their approximation ability (Cybenko (1989), Barron (1993), Lu et al. (2017), Yarotsky (2017), and Petersen & Voigtlaender (2017)) and generalization power (Barron (1994), Arora et al. (2018), and Suzuki (2018)). See also Pinkus (2005) and Kainen et al. (2013) for surveys of earlier works. Although less common compared to FNNs, recently, statistical learning theory for CNNs has been studied, both about approximation ability (Zhou (2018), Yarotsky (2018), Petersen & Voigtlaender (2018)) and about generalization power (Zhou & Feng (2018)). One of the standard approaches is to relate the approximation ability of CNNs with that of FNNs, either deep or shallow. For example, Zhou (2018) proved that CNNs are a universal approximator of the Barron class (Barron (1993), Klusowski & Barron (2016)), which is a historically important function class in the approximation theory. Their approach is to approximate the function using a 2-layered FNN (i.e., an FNN with a single hidden layer) with the ReLU activation function (Krizhevsky et al. (2012)) and transform the FNN into a CNN. Very recently independent of ours, Petersen & Voigtlaender (2018) showed any function realizable with an FNN can extend to an equivariant function realizable by a CNN that has the same order of parameters. However, to the best of our knowledge, no CNNs that achieves the minimax optimal rate (Tsybakov (2008), Giné & Nickl (2015)) in important function classes, including the Hölder class, can keep the number of
units in each layer constant with respect to the sample size. Architectures that have extremely large depth, while moderate channel size and width have become feasible, thanks to recent methods such as identity mappings (He et al. (2016), Huang et al. (2018)), sophisticated initialization schemes (He et al. (2015), Chen et al. (2018)), and normalization techniques (Ioffe & Szegedy (2015), Miyato et al. (2018)). Therefore, we would argue that there are growing demands for theories which can accommodate such constant-size architectures.
In this paper, we analyze the learning ability of ResNet-type ReLU CNNs which have identity mappings and constant-width residual blocks with fixed-size filters. There are mainly two reasons that motivate us to study this type of CNNs. First, although ResNet is the de facto architecture in various practical applications, the approximation theory for ResNet has not been explored extensively, especially from the viewpoint of the relationship between FNNs and CNNs. Second, constant-width CNNs are critical building blocks not only in ResNet but also in various modern CNNs such as Inception (Szegedy et al. (2015)), DenseNet (Huang et al. (2017)), and U-Net (Ronneberger et al. (2015)), to name a few. Our strategy is to replicate the learning ability of FNNs by constructing tailored ResNet-type CNNs. To do so, we pay attention to the block-sparse structure of an FNN, which roughly means that it consists of a linear combination of multiple (possibly dense) FNNs (we define it rigorously in the subsequent sections). Block-sparseness decreases the model complexity coming from the combinatorial sparsity patterns and promotes better bounds. Therefore, it is often utilized, both implicitly or explicitly, in the approximation and learning theory of FNNs (e.g., Bölcskei et al. (2017), Yarotsky (2018)). We first prove that if an FNN is block-sparse with M blocks (M -way block-sparse FNN), we can realize the FNN with a ResNet-type CNN withO(M) additional parameters, which are often negligible since the original FNN already has Ω(M) parameters. Using this approximation, we give the upper bound of the estimation error of CNNs in terms of the approximation errors of block sparse FNNs and the model complexity of CNNs. Our result is general in the sense that it is not restricted to a specific function class, as long as we can approximate it using block-sparse FNNs.
To demonstrate the wide applicability of our methods, we derive the approximation and estimation errors for two types of function classes with the same strategy: the Barron class (of parameter s = 2) and Hölder class. We prove, as corollaries, that our CNNs can achieve the approximation error of order Õ(M− D+2 2D ) for the Barron class and Õ(M− β D ) for the β-Hölder class and the estimation error of order Õp(N − D+2 2(D+1) ) for the Barron class and Õp(N− 2β
2β+D ) for the β-Hölder class, where M is the number of parameters (we used M here, same as the number of blocks because it will turn out that CNNs have O(M) blocks for these cases), N is the sample size, and D is the input dimension. These rates are same as the ones for FNNs ever known in the existing literature. An important consequence of our theory is that the ResNet-type CNN can achieve the minimax optimal estimation error (up to logarithmic factors) for β-Hölder class even if its filter size, channel size and width are constant with respect to the sample size, as opposed to existing works such as Yarotsky (2017) and Petersen & Voigtlaender (2018), where optimal FNNs or CNNs could have a width or a channel size goes to infinity as N →∞. In summary, the contributions of our work are as follows:
• We develop the approximation theory for CNNs via ResNet-type architectures with constant-width residual blocks. We prove any M -way block-sparse FNN is realizable such a CNN with O(M) additional parameters. That means if FNNs can approximate a function with O(M) parameters, we can approximate the function with CNNs at the same rate (Theorem 1).
• We derive the upper bound of the estimation error in terms of the approximation error of FNNs and the model complexity of CNNs (Theorem 2). This result gives the sufficient conditions to derive the same estimation error as that of FNNs (Corollary 1).
• We apply our general theory to the Barron class and Hölder class and derive the approximation (Corollary 2 and 4) and estimation (Corollary 3 and 5) error rates, which are identical to those for FNNs, even if the CNNs have constant channel and filter size with respect to the sample size. In particular, this is minimax optimal for the Hölder case.

heading: 2 RELATED WORK
text: We summarize in Table 1 the differences in the CNN architectures between our work and Zhou (2018) and Petersen & Voigtlaender (2018), which established the approximation theory of CNNs via FNNs. First and foremost, Zhou (2018) only considered a specific function class — the Barron class — as a target function class, although their method is applicable to any function class that can be realized by a 2-layered ReLU FNN. Regarding the architecture, they considered CNNs with a single channel and whose width is “linearly increasing” (Zhou (2018)) layer by layer. For regression or classification problems, it is rare to use such an architecture. In addition, since they did not bound the norm of parameters in the approximating CNNs, we cannot derive the estimation error from this method. Petersen & Voigtlaender (2018) fully utilized the group invariance structure of underlying input spaces to construct CNNs. Such a structure makes theoretical analysis easier, especially for investigating the equivariance properties of CNNs since it enables us to incorporate mathematical tools such as group theory, Fourier analysis, and representation theory. Although their results are quite strong in that it is applicable to any function that can be approximated by FNNs, their assumption on the group structure excludes the padding convolution layer, an important and popular type of convolution operations. Another point is that if we simply apply their construction method to derive the estimation error for (equivariant) Hölder functions, combined with the approximation result of Yarotsky (2017), the resulting CNN that achieves the minimax optimal rate has Õ(ε− D β ) channels where ε is the approximation error threshold. It is partly because their construction is not aware of the internal sparse structure of approximating FNNs. Finally, the filter size of their CNN is as large as the input dimension. As opposed to these two works, we employ padding- and ResNettype CNNs which have multiple channels, fixed-size filters, and constant widths. Like Petersen & Voigtlaender (2018), our result is applicable to any function, as long as the FNNs to be approximated are block sparse, including the Barron and Hölder cases. If we apply our theorem to these classes, we can show that the optimal CNNs can achieve the same approximation and estimation rate as FNNs, while the number of channels is independent of the sample size. Further, this is minimax optimal up to the logarithmic factors for the Hölder class.
Due to its practical success, theoretical analysis for ResNet has been explored recently (e.g., Lin & Jegelka (2018), Lu et al. (2018), Nitanda & Suzuki (2018), and Huang et al. (2018)). From the viewpoint of statistical learning theory, Nitanda & Suzuki (2018) and Huang et al. (2018) investigated the generalization power of ResNet from the perspective of the boosting interpretation. However, they did not discuss the function approximation ability of ResNet. To the best of our knowledge, our theory is the first work to provide the approximation ability of the CNN class that can accommodate the ResNet-type ones.
We import the approximation theories for FNNs, especially ones for the Barron class and Hölder class. The approximation theory for the Barron class has been investigated in e.g., Barron (1993), Klusowski & Barron (2016), and Lee et al. (2017). Originally Barron (1993) considered the parameter s = 1 (see Definition 3) and the activation function σ satisfying σ(z)→ 1 as z →∞ and σ(z) → 0 as z → −∞. Later, Klusowski & Barron (2016) studied the approximation theory with s = 2 and proved that 2-layered ReLU FNNs with M hidden units can approximate functions of this class with the order of Õ(M− D+2 2D ). Yarotsky (2017) proved FNNs with O(S) non-zero parameters can approximate β-Hölder continuous functions with the order of Õ(S− β D ). Using this bound, Schmidt-Hieber (2017) proved that the estimation error of the ERM estimator is Õ(N− 2β 2β+D ), which is minimax optimal up to logarithmic factors (see, e.g., Tsybakov (2008)).

heading: 3 PROBLEM SETTING

heading: 3.1 EMPIRICAL RISK MINIMIZATION
text: We consider a regression task in this paper. Let X be a [−1, 1]D-valued random variable with unknown probability distribution PX and ξ be an independent random noise drawn from the Gaussian distribution with an unknown variance σ2: ξ ∼ N (0, σ2) (σ > 0). Let f◦ be an unknown deterministic function f◦ : [−1, 1]D → R (we will characterize f◦ rigorously in the theorems later). We define a random variable Y by Y := f◦(X) + ξ. We denote the joint distribution of (X,Y ) by P . Suppose we are given a dataset D = ((x1, y1), . . . , (xN , yN )) independently and identically sampled from the distribution P , we want to estimate the true function f◦ from the finite dataset D. We evaluate the performance of an estimator by the squared error. For a measurable function f : [−1, 1]D → R, we define the empirical error of f by R̂D(f) := ∑N n=1(yn − f(xn))2 and the
estimation error by R(f) := EX,Y [ (f(X)− Y )2 ] . Given a subset F of measurable functions from [−1, 1]D → R, we consider the clipped empirical risk minimization (ERM) estimator f̂ of F that satisfies
f̂ := clip[fmin] where fmin ∈ arg min f∈F R̂D(clip[f ]).
Here, clip is the clipping operator defined by clip[f ] := (f ∨−‖f◦‖∞)∧‖f◦‖∞. For a measurable function f : [−1, 1]D → R, we define the L2-norm (weighted by PX ) and the sup norm of f by
‖f‖L2(PX) := (∫ [−1,1]D f 2(x)dPX(x) ) 1 2
and ‖f‖∞ := supx∈[−1,1]D |f(x)|, respectively. Let L2(PX) be the set of measurable functions f such that ‖f‖L2(PX) <∞ with the norm ‖ · ‖L2(PX). The task is to estimate the approximation error minf∈F ‖f − f◦‖∞ and the estimation error of the clipped ERM estimator: R(f̂) − R(f◦). Note that the estimation error is a random variable with respect the choice of the training dataset D. By the definition of R and the independence of X and ξ, the estimation error equals to ‖f̂ − f◦‖2L2(PX).

heading: 3.2 CONVOLUTIONAL NEURAL NETWORKS
text: In this section, we define CNNs used in this paper. For this purpose, it is convenient to introduce `0, the set of real-valued sequences whose finitely many elements are non-zero: `0 := {w = (wn)n∈N>0 | ∃N ∈ N>0 s.t. wn = 0,∀n ≥ N}. w = (w1, . . . , wK) ∈ RK can be regarded as an element of `0 by setting wn = 0 for all n > K. Likewise, for C,C ′ ∈ N>0, which will be the input and output channel sizes, respectively, we can think of (wk,j,i)k∈[K],j∈[C′],i∈[C] ∈ RK×C
′×C as an element of `C
′×C 0 . For a filter w = (wn,j,i)n∈N>0,i∈[C],j∈[C′] ∈ ` C′×C 0 , we define the one-sided
padding and stride-one convolution by w as an order-4 tensor LwD = ((L w D) β,j α,i) ∈ RD×D×C ′×C by
(LwD) β,j α,i := { w(α−β+1),j,i if 0 ≤ α− β ≤ D − 1 0 otherwise.
Here, i (resp. j) runs through 1 to C (resp. C ′) and α and β runs through 1 to D. Since we fix the input dimension D throughout the paper, we will omit the subscript D and write as Lw if it is obvious from context.
Remark 1. For K ≤ K ′, we can embed RK into RK′ by inserting zeros: w = (w1, . . . , wK) 7→ w′ = (w1, . . . , wK , 0, . . . , 0). It is easy to show Lw = Lw ′ . Using this equality, we can expand a size-K filter to size-K ′.
We can interpret Lw as a linear mapping from RD×C to RD×C′ . Specifically, for x = (xα,i)α,i ∈ RD×C , we define (yβ,j)β,j = Lw(x) ∈ RD×C ′ by
yβ,j := ∑ i,α (Lw)β,jα,i x α,i.
Next, we define the building block of CNNs: convolutional layers and fully-connected layers. Let C,C ′,K ∈ N>0 be the input channel size, output channel size, and filter size, respectively. For a weight tensor w ∈ RK×C′×C , a bias vector b ∈ RC′ , and an activation function σ : R → R, we define the convolutional layer Convσw,b : RD×C → RD×C ′ by Convσw,b(x) := σ(L
w(x)− 1D ⊗ b) where, ⊗ is the outer product of vectors and σ is applied in element-wise manner. Similarly, let W ∈ RD×C , b ∈ R, and σ : R → R, we define the fully-connected layer FCσW,b : RD×C → R by FCσW,b(a) = σ(vec(W )
>vec(a) − b). Here, vec(·) is the vectorization operator that flattens a matrix into a vector.
Finally, we define the ResNet-type CNN as a sequential concatenation of one convolution block, M residual blocks, and one fully-connected layer. Figure 1 is the schematic view of the CNN we adopt in this paper. Definition 1 (Convolutional Neural Networks (CNNs)). Let M ∈ N>0 and Lm ∈ N>0, which will be the number of residual blocks and the depth of m-th block, respectively. Let C(l)m ,K (l) m be the channel size and filter size of the l-th layer of the m-th block for m = 0, . . . ,M 1 and l ∈ [Lm]. We assume C(L0)0 = C (L1) 1 = · · · = C (LM ) M . Let w (l) m ∈ RK (l) m ×C (l) m ×C (l−1) m and b(l)m ∈ R be the weight tensors and biases of l-th layer of the m-th block in the convolution part, respectively. Finally, let W ∈ RD×C (L0) 0 and b ∈ R be the weight matrix and the bias for the fully-connected layer part, respectively. For θ := ((w(l)m )m,l, (b (l) m )m,l,W, b) and an activation function σ : R → R, we define CNNσθ : RD → RD, the CNN constructed from θ, by
CNNσθ := FC id W,b ◦ (Conv σ wM ,bM + id) ◦ (Conv σ wM−1,bM−1 + id) ◦ · · ·
◦ (Convσw1,b1 + id) ◦ Conv σ w0,b0 ,
where Convσwm,bm := Conv id
w (Lm) m ,b (Lm) m ◦ Convσ w (Lm−1) m ,b (Lm−1) m ◦ · · · ◦ Convσ w (1) m ,b (1) m and id :
RD×C (L0) 0 → RD×C (L0) 0 is the identity function.
Although CNNσθ in this definition has a fully-connected layer, we refer to the stack of convolutional layers both with or without the final fully-connect layer as a CNN in this paper. We say a linear convolutional layer or a linear CNN when the activation function σ is the identity function and a ReLU convolution layer or a ReLU CNN when σ is ReLU defined by ReLU(x) = x∨0. We borrow the term from ResNet and call Convσwm,bm (m > 0) and id in the above definition the m-th residual block and the m-th identity mapping, respectively. We say a 4-tuple θ is compatible with (C(l)m )m,l and (K(l)m )m,l when each component of θ satisfies the aforementioned dimension conditions.
1Note that m starts from 0. It is convenient for our purpose.
For architecture parameters C = (C(l)m )m,l and K = (K (l) m )m,l (m = 0, . . . ,M, l ∈ [Lm]), and norm parameters for convolution layers B(conv) > 0 and for fully-connected layers B(fc) > 0, we define F (CNN) = F (CNN)
C,K,B(conv),B(fc) , the hypothesis class consisting of ReLU CNNs, as follows:
F (CNN) := CNNReLUθ θ = ((w (l) m )m,l, (b (l) m )m,l,W, b) is compatible with (C,K), maxm=0,...,M,l∈[Lm] ‖w (l) m ‖∞ ∨ ‖b(l)m ‖∞ ≤ B(conv),
‖W‖∞ ∨ ‖b‖∞ ≤ B(fc)  . Here, the domain of CNNs is restricted to [−1, 1]D. Note that we impose norm constraints to the convolution part and fully-connected part separately. We emphasize that we do not impose any sparse constraints (e.g., restricting the number of non-zero parameters in a CNN to some fixed value) to F (CNN), as opposed to previous literature such as Yarotsky (2017), Schmidt-Hieber (2017), and Imaizumi & Fukumizu (2018). Since the notation is cluttered, we sometimes omit the subscripts as we do in the above. Remark 2. In this paper, we adopted one-sided padding, which is not often used practically, in order to make proofs simple. However, with slight modifications, all statements are true for equallypadded convolutions, the widely employed padding style which adds (approximately) same numbers of zeros to both ends of an input signal, with the exception that the filter size K is restricted to K ≤ ⌊ D 2 ⌋ instead of K ≤ D − 1. We also discuss our design choice, especially the comparison with the original ResNet proposed in He et al. (2016) in Section G of the appendix.

heading: 3.3 BLOCK-SPARSE FULLY-CONNECTED NEURAL NETWORKS
text: In this section, we mathematically define FNNs we consider in this paper, in parallel with the CNN case. Our FNN, which we coin a block-sparse FNN, consists of M possibly dense FNNs (blocks) concatenated in parallel, followed by a single fully-connected layer. We sketch the architecture of a block-sparse FNN in Figure 2. Definition 2 (Fully-connected Neural Networks (FNNs)). Let M ∈ N>0 be the number of blocks in an FNN. Let Dm = (D (1) m , . . . , D (Lm) m ) ∈ NLm>0 be the sequence of intermediate dimensions of the m-th block, where Lm ∈ N>0 is the depth of the m-th block for m ∈ [M ] 2. Let W (l) m ∈ RD (l) m ×D (l−1) m and b(l)m ∈ R be the weight matrix and the bias of the l-th layer of mth block (with the convention D(0)m = D). Let wm ∈ RD (Lm) m be the weight (sub)vector of the final fully-connected layer corresponding to the m-th block and b ∈ R be the bias for the last layer. For θ = ((W (l)m )m,l, (b (l) m )m,l, (wm)m, b) and an activation function σ : R → R, we define FNNσθ : RD → R, the block-sparse FNN constructed from θ, by
FNNσθ := M∑ m=1 w>mFC σ Wm,bm(·)− b,
2Be aware that contrary to the CNN case, m starts from 1 here.
where FCσWm,bm := FC σ
W (Lm) m ,b (Lm) m ◦ · · ·FCσ W (1) m ,b (1) m .
We call a block-sparse FNN with M blocks a M -way block-sparse FNN. We say θ is compatible with (D(l)m )m,l when each component of θ matches the dimension conditions determined by (D (l) m )m,l, as we did in the CNN case. Note that when Lm = 1 for all m ∈ [M ], the block-
sparse FNN is a 2-layered neural network with D′ := ∑M m=1D (1) m hidden units of the form
f(x) = ∑D′ d=1 bdσ(a > d x− td)− b where ad ∈ RD and bd, td, b ∈ R.
For an architectureD = (D(l)m )m∈[M ],l∈[Lm] and norm parameters for the block part B (bs) > 0 and for the final layer B(fin) > 0, we define F (FNN) = F (FNN) D,B(bs),B(fin)
, the set of function realizable by FNNs:
F (FNN) := FNNReLUθ θ = ((W (l) m )m,l, (b (l) m )m,l, (wm)m, b) is compatible withD, maxm∈[M ],l∈[Lm](‖W (l) m ‖∞ ∨ ‖b(l)m ‖∞) ≤ B(bs),
maxm∈[M ] ‖wm‖∞ ∨ |b| ≤ B(fin).  . Again, the domain is restricted to [−1, 1]D. Similar to the CNN case, we sometimes remove subscripts of the function class for simplicity.

heading: 4 MAIN THEOREMS
text: With the preparation in the previous sections, we state our main results of this paper. We only describe statements of theorems and corollaries and key ideas in the main article. All complete proofs are deferred to the appendix.

heading: 4.1 APPROXIMATION
text: Our first main theorem claims that any M -way block-sparse FNN is realizable by a ResNet-type CNN with fixed-sized channels and filters by adding O(M) parameters, if we treat the widths D(l)m of the FNN as constants with respect to M .
Theorem 1. Let M ∈ N>0, K ∈ {2, . . . D} and L0 := ⌈ D−1 K−1 ⌉ . Let Lm ∈ N>0, D(l)m ∈ N>0
(m ∈ [M ]), and D = (D(l)m )m∈[M ],l∈[Lm]. Then, there exist L′m ∈ N>0 (m = 0, . . . ,M ), C = (C
(l) m )m=0,...,M,l∈[L′m], andK = (K (l) m )m=0,...,M,l∈[L′m] satisfying the following conditions:
1. L′0 ≤ 1, L′m ≤ Lm + L0 (m ∈ [M ]),
2. max m=0,...,M,l∈[L′m] C(l)m ≤ 4 max m∈[M ],l∈[Lm] D(l)m , and
3. max m=0,...,M,l∈[L′m] K(l)m ≤ K
such that, for any B(bs), B(fin) > 0, we have
F (FNN) D,B(bs),B(fin) ⊂ F (CNN) C,K,B(conv),B(fc) , (1)
that is, any FNN in F (FNN) D,B(bs),B(fin) can be realized by a CNN in F (CNN) C,K,B(conv),B(fc) . Here, B(conv) = B(bs) and B(fc) = B(fin) ( 1 ∨ 1
B(bs)
) .
An immediate consequence of this theorem is that if we can approximate a function f◦ with a blocksparse FNN, we can also approximate f◦ with a CNN.

heading: 4.2 ESTIMATION
text: Our second main theorem bounds the estimation error of the clipped ERM estimator f̂ .
Theorem 2. Let f◦ : RD → R be a measurable function andB(bs), B(fin) > 0. LetM ,K, L0, Lm, D, B(conv) and B(fc) as in Theorem 1. Suppose L′m,C,K satisfies the equation (1) of Theorem 1 for B(bs) and B(fin) (their existence is ensured for any B(bs) and B(fin) if they satisfy the conditions 1 – 3. of Theorem 1). Suppose that the covering nubmer of F (CNN) := F (CNN)
C,K,B(conv),B(fc) is larger
than 3. Then, the clipped ERM estimator f̂ in F := {clip[f ] | f ∈ F (CNN)} satisfies
ED‖f̂ − f◦‖2L2(PX) ≤ C
( inf
f∈F(FNN) ‖f − f◦‖2∞ +
M2F̃ 2
N log(2M1BN)
) . (2)
Here, F (FNN) := F (FNN) D,B(bs),B(fin) , C > 0 is a universal constant, F̃ := ‖f ◦‖∞ σ ∨ 1 2 , and B = B(conv) ∨B(fc). M1 and M2 are defined by
M1 := (2M + 3)C (L′0) 0 D(1 ∨B(fc))(1 ∨B(conv)) ( M∏ m=0 (1 + ρm) )( 1 + M∑ m=0 L′mρ + m ) ,
M2 := M∑ m=0 L′m∑ l=1 ( C(l−1)m C (l) m K (l) m + C (l) m ) + C (L′0) 0 D + 1,
where ρm := ∏L′m l=0 C (l−1) m K (l) m B(conv) and ρ+m := ∏L′m l=0(1 ∨ C (l−1) m K (l) m B(conv)).
The first term of (2) is the approximation error achieved by F (FNN). On the other hand, M1 and M2 are determined by the architectural parameters of F (CNN) — M1 corresponds to the Lipschitz constant of a function realized by a CNN and M2 is the number of parameters, including zeros, of a CNN. Therefore, the second term of (2) represents the model complexity of F (CNN). There is a trade-off between the two terms. Using appropriately chosen M to balance them, we can evaluate the order of estimation error with respect to the sample size N .
Corollary 1. Under the same assumptions as Theorem 2, suppose further logM1(B(conv)∨B(fc)) = Õ(1) as a function ofM . If inff∈F(FNN) ‖f−f◦‖2∞ = Õ(M−γ1) andM2 = Õ(Mγ2) for some constant γ1, γ2 > 0 independent of M , then, the clipped ERM estimator f̂ of F achieves the estimation error ‖f◦ − f̂‖2L2(PX) = Õp ( N− 2γ1 2γ1+γ2 ) .

heading: 5 APPLICATION OF MAIN THEOREMS

heading: 5.1 BARRON CLASS
text: The Barron class is an example of the function class that can be approximated by block-sparse FNNs. We employ the definition of Barron functions used in Klusowski & Barron (2016).
Definition 3 (Barron class). We say a measurable function f◦ : [−1, 1]D → R is a Barron function with the parameter s > 0 if f◦ admits the Fourier representation (i.e., f◦(x) = F̌F [f◦]) and vf◦ := ∫ RD ‖w‖ s 2 |F [f◦](w)|dw < ∞. Here, F and F̌ are the Fourier transformation and the inverse Fourier transformation, respectively.
Klusowski & Barron (2016) studied the approximation of the Barron function f◦ with the parameter s = 2 by a linear combination ofM ridge functions (i.e., a 2-layered ReLU FNN). Specifically, they showed that there exists a function fM of the form
fM := f ◦(0) +∇f◦>(0)x+ 1
M M∑ m=1 bm(a > mx− tm)+ (3)
with |bm| ≤ 1, ‖am‖1 = 1 and |tm| ≤ 1, such that ‖f◦ − fM‖∞ = Õ ( M−( 1 2 + 1 D ) )
. Using this approximator fM , we can derive the same approximation order using CNNs by applying Theorem 1 with L1 = · · · = LM = 1 and D(1)1 = · · · = D (1) M = 1.
Corollary 2. Let f◦ : [−1, 1]D → R be a Barron function with the parameter s = 2 such that f◦(0) = 0 and ∇f◦(0) = 0D. Then, for any K = 2, . . . , D, there exists a CNN f (CNN) with M residual blocks, each of which has depth O(1) and at most 4 channels, and whose filter size is at
most K, such that ‖f◦ − f (CNN)‖∞ = Õ ( M−( 1 2 + 1 D ) ) .
We have one design choice when we apply Corollary 1 to derive the estimation error: how to set B(bs) and B(fin). Looking at (3), the naive choice would be B(bs) := 1 and B(fin) := 1M . However, this cannot satisfy the assumption on M1 of Corollary 1, due to the term ∏M m=0 (1 + ρm) whose logarithm is O(M). We want its logarithm to be Õ(1). In order to do that, we change the relative scale between parameters in the block-sparse part and the fully-connected part using the homogeneous property of the ReLU function: ReLU(ax) = aReLU(x) for a > 0. The rescaling operation enables us to choose B(bs) := 1M and B
(fin) = 1 to meet the assumption of Corollary 1. By setting γ1 = 1 2 + 1 D and γ2 = 1, we obtain the desired estimation error.
Corollary 3. There exist the number of residual blocks M = O ( N D 2+2D ) , depth of each residual
block L = O (1), channel size C = O(1), filter size K ∈ {2, . . . , D}, and norm bounds for the convolution part B(conv) = O ( N− D 2+2D ) , and for the fully-connected part B(fc) = O ( N D 2+2D ) such that for sufficiently large N , the clipped ERM estimator f̂ of F := {clip[f ] | f ∈

heading: F (CNN)
text: C,K,S,B(conv),B(fc) } achieves the estimation error ‖f◦ − f̂‖2L2(PX) = Õp ( N− D+2 2(D+1) ) . Here, C (l) m = C,K (l) m = K for m = 0, . . . ,M, l ∈ [L] and define C = (C(l)m )m,l,K = (K(l)m )m,l.

heading: 5.2 HÖLDER CLASS
text: We next consider the approximation and error rates of CNNs when the true function is a β-Hölder function. Definition 4 (Hölder class). Let β > 0, f◦ : [−1, 1]D → R is a β-Hölder function if
‖f◦‖β := ∑
0≤|α|<bβc ‖∂αf◦‖∞ + ∑ |α|=bβc sup x6=y |∂αf◦(x)− ∂αf◦(y)| |x− y|β−bβc <∞.
Here, α = (α1, . . . , αD) is a multi-index. That is, ∂αf := ∂ |α|f
∂x α1 1 ···∂x αD D
and |α| := ∑D d=1 αd.
Yarotsky (2017) showed that FNNs with O(S) non-zero parameters can approximate any D variate β-Hölder function (β > 0) with the order of Õ(S− β D ). Schmidt-Hieber (2017) also proved a similar statement using a different construction method. They only specified their width (Schmidt-Hieber (2017) only), depth, and non-zero parameter counts of the approximating FNN and did not write in detail how non-zero parameters are distributed explicitly in the statements (see Theorem 1 of Yarotsky (2017) and Theorem 5 of Schmidt-Hieber (2017)). However, if we carefully look at their proofs, we find that we can transform the FNNs they constructed into the block-sparse ones. Therefore, we can utilize these FNNs and apply Theorem 1. To meet the assumption of Corollary 1, we again rescale the parameters of the FNNs, as we did in the Barron class case, so that logM1 = Õ(1). We can derive the approximation and estimation errors by setting γ1 = βD and γ2 = 1. Corollary 4. Let β > 0, and f◦ : [−1, 1]D → R be a β-Hölder function. Then, for any K = 2, . . . , D, there exists a CNN f (CNN) withO(M) residual blocks, each of which has depthO(logM)
and O(1) channels, and whose filter size is at most K, such that ‖f◦ − f (CNN)‖∞ = Õ ( M− β D ) .
Corollary 5. There exist the number of residual blocks M = O ( N D 2β+D ) , depth of each residual
block L = Õ (1), channel size C = O(1), filter size K ∈ {2, . . . , D}, norm bounds for the convolution part B(conv) = O(1), and for the fully-connected part B(fc) > 0 (logB(fc) = O(logN)) such that for sufficiently large N , the clipped ERM estimator f̂ of F := {clip[f ] | f ∈

heading: F (CNN)
text: C,K,S,B(conv),B(fc) } achieves the estimation error ‖f◦ − f̂‖2L2(PX) = Õp ( N− 2β 2β+D ) . Here, C (l) m = C,K (l) m = K for m = 0, . . . ,M, l ∈ [L] and define C = (C(l)m )m,l,K = (K(l)m )m,l.
Since the estimation error rate of the β-Hölder class is Op ( N− 2β 2β+D ) (see, e.g., Tsybakov (2008)),
Corollary 5 implies that our CNN can achieve the minimax optimal rate up to logarithmic factors even the width D, the channel size C, and the filter size K are constant with respect to the sample size N .

heading: 6 CONCLUSION
text: In this paper, we established new approximation and statistical learning theories for CNNs by utilizing the ResNet-type architecture of CNNs and the block-sparse structure of FNNs. We proved that any M -way block-sparse FNN is realizable using CNNs with O(M) additional parameters, when the width of the FNN is fixed. Using this result, we derived the approximation and estimation errors for CNNs from those for block-sparse FNNs. Our theory is general because it does not depend on a specific function class, as long as we can approximate it with block-sparse FNNs. To demonstrate the wide applicability of our results, we derived the approximation and error rates for the Barron class and Hölder class in almost same manner and showed that the estimation error of CNNs is same as that of FNNs, even if the CNNs have a constant channel size, filter size, and width with respect to the sample size. The key techniques were careful evaluations of the Lipschitz constant of CNNs and non-trivial weight parameter rescaling of FNNs.
One of the interesting open questions is the role of the weight rescaling. We critically use the homogeneous property of the ReLU activation function to change the relative scale between the block-sparse part and the fully-connected part, if it were not for this property, the estimation error rate would be worse. The general theory for rescaling, not restricted to the Barron nor Hölder class would be beneficial for deeper understanding of the relationship between the approximation and estimation capabilities of FNNs and CNNs.
Another question is when the approximation and estimation error rates of CNNs can exceed that of FNNs. We can derive the same rates as FNNs essentially because we can realize block-sparse FNNs using CNNs that have the same order of parameters (see Theorem 1). Therefore, if we dig into the internal structure of FNNs, like repetition, more carefully, the CNNs might need fewer parameters and can achieve better estimation error rate. Note that there is no hope to enhance this rate for the Hölder case (up to logarithmic factors) because the estimation rate using FNNs is already minimax optimal. It is left for future research which function classes and constraints of FNNs, like block-sparseness, we should choose.

heading: A NOTATION
text: For tensor a, a+ := a∨0 where maximum operation is performed in element-wise manner. Similarly a− := −(−a ∨ 0). Note that a = a+ − a− holds for any tensor a. For normed spaces (V, ‖ · ‖V ), (W, ‖ · ‖W ) and linear operator T : V → W we denote the operator norm of T by ‖T‖op := sup‖v‖V =1 ‖Tv‖W . For a sequence w = (w
(1), . . . , w(L)) and l ≤ l′, we denote its subsequence from the l-th to l′-th elements by w[l : l′] := (w(l), . . . , w(l
′)). 1P equals to 1 if the statement P is true, equals to 0 otherwise.

heading: B PROOF OVERVIEW

heading: B.1 THEOREM 1
text: For f (FNN) ∈ F (FNN), we realize a CNN f (CNN) using M residual blocks by “serializing” blocks in the FNN and converting them into convolution layers.
First, we double the channel size using the m = 0 part of CNN (i.e., D(L0)0 = 2). We will use the first channel for storing the original input signal for feeding to downstream (i.e., m ≥ 1) blocks and the second one for accumulating the output of each blocks, that is, ∑m′ m=1 w > mFC ReLU Wm,bm(x) where wm is the weight of the final fully-connected layer corresponding to the m-th dense block.
For m = 1, . . . ,M , we create the m-th residual block from the m-th block of f (FNN). First, we show that for any a ∈ RD and t ∈ R, there exists L0-layered 4-channel ReLU CNN with O(D) parameters whose first output coordinate equals to a ridge function x 7→ (a>x − t)+ (Lemma 1 and Lemma 2). Since the first layer of m-th block is concatenation of D(1)m hinge functions, it is realizable by a 4D(1)m -channel ReLU CNN with L0-layers.
For the l-th layer of the m-th block (m ∈ [M ], l = 2, . . . , L(l)m ), we prepare D(l)m size-1 filters made from the weight parameters of the corresponding layer of the FNN. Observing that the convolution operation with size-1 filter is equivalent to a dimension-wise affine transformation, the first coordinate of the output of l-th layer of the CNN is inductively same as that of the m-th block of the FNN. After computing the m-th block FNN using convolutions, we add its output to the accumulating channel in the identity mapping.
Finally, we pick the first coordinate of the accumulating channel and subtract the bias term using the final affine transformation.

heading: B.2 THEOREM 2 AND COROLLARY 1
text: We relate the approximation error of Theorem 2 with the estimation error using the covering number of the hypothesis classF (CNN). Although there are several theorems of this type, we employ the one in Schmidt-Hieber (2017) due to its convenient form (Lemma 5). We can prove that the logarithm of the covering number is upper bounded by M2 log((B(conv) ∨B(fc))M1/ε) (Lemma 4) using the similar techniques to the one in Schmidt-Hieber (2017). Theorem 2 is the immediate consequence of these two lemmas.
To prove Cororraly 1, we set M = O(Nα) for some α ≥ 0. Then, under the assumption of the corolarry, we have ‖f◦ − f̂‖2L2(Px) = Õ ( max ( N−2αγ1 , Nαγ2−1 )) from Theorem 2. The order of the right hand side with respect to N is minimized when α = 12γ1+γ2 . By substituting α, we can prove Corollary 1.

heading: C PROOF OF THEOREM 1

heading: C.1 DECOMPOSITION OF AFFINE TRANSFORMATION
text: The following lemma shows that any affine transformation is realizable with a ⌈ D−1 K−1 ⌉ -layered linear conventional CNN (without the final fully-connect layer).
Lemma 1. Let a ∈ RD, t ∈ R, K ∈ {2, . . . , D − 1}, and L0 := ⌈ D−1 K−1 ⌉ . Then, there exists
w(l) ∈  RK×2×1 (for l = 1) RK×2×2 (for l = 2, . . . , L0 − 1) RK×1×2 (for l = L0)
and b ∈ R such that
1. L0∑ l=1] ‖w(l)‖0 + L0∑ l=1 ‖b(l)‖0 ≤ D + L0,
2. max l∈[Lo] ‖wm‖∞ = ‖a‖∞, max l∈[L0] ‖b(l)‖∞ = |t|, and
3. Convidw,b : RD → RD satisfies Conv id w,b(x) = a >x− t for any x ∈ [−1, 1]D.
Proof. First, observe that the convolutional layer constructed from u = [u1 . . . uK ] > ∈ RK×1×1 takes the inner product with the firstK elements of the input signal: Lu(x) = ∑K k=1 ukxk. In particular, u = [0 . . . 0 1]> ∈ RK×1×1 works as the “left-translation” by K − 1. Therefore, we should define w so that it takes the inner product with the K left-most elements in the first channel and shift the input signal by K − 1 with the second channel. Specifically, we define w = (w(1), . . . , w(L0)) by
(w(1)):,1,: =  a1... aK  , (w(1)):,2,: =  0 ... 0 1  ,
(w(l)):,1,: = 0 a(l−1)K+1... ... 0 alK  , (w(l)):,2,: =  0 0 ... ... 0 0 1 0  ,
(w(L0)):,1,: =  0 a(L0−1)K+1 ... ... 0 aD 0 0 ...
... 0 0
 .
We set b := ( 0, . . . , 0︸ ︷︷ ︸ L0 − 1 times , t). Then w and b satisfy the condition of the lemma.

heading: C.2 TRANSFORMATION OF A LINEAR CNN INTO A RELU CNN
text: The following lemma shows that we can convert any linear CNN to a ReLU CNN that has approximately 4 times larger parameters. This type of lemma is also found in Petersen & Voigtlaender (2017) (Lemma 2.3). Lemma 2. Let C = (C(1), . . . , C(L)) ∈ NL>0 be channel sizes K = (K(1), . . . ,K(L)) ∈ NL>0 be filter sizes. Let w(l) ∈ RK(l)×Cl×C(l) and b(l) ∈ R(l). Consider the linear convolution layers constructed from w and b: fid := Convidw,b : RD → RD×C
(L)NL>0 where w = (w(l))l and b = (b(l))l . Then, there exists a pair w̃ = (w̃(l))l∈[L], b̃ = (b̃(l))l∈[L] where w̃(l) ∈ RK (l)×2C(l)×2C(l−1) and b̃(l) ∈ R2C(l) such that
1. L∑ l=1 ‖w̃(l)‖0 ≤ 4 L∑ l=1 ‖w(l)‖0, L∑ l=1 ‖b̃(l)‖0 ≤ L∑ l=1 ‖b(l)‖0,
2. max l∈[L] ‖w̃(l)‖∞ = max l∈[L] ‖w(l)‖∞, max l∈[L] ‖b̃(l)‖∞ = max l∈[L] ‖b(l)‖∞, and
3. fReLU := ConvReLUw̃,b̃ : R D → RD×2C(L) , satisfies fReLU(·) = (fid(·)+, fid(·)−).
Proof. We define w̃ and b̃ as follows:
(w̃(1))k,:,: = [ (w(1))k,:,: −(w(1))k,:,: ] for k = 1, . . . ,K(1),
(w̃(l))k,:,: = [ (w(l))k,:,: −(w(l))k,:,: −(w(l))k,:,: (w(l))k,:,: ] for k = 1, · · ·K(l),
b̃(l) =
[ b(l) −b(l) ]
By definition, a pair (w̃, b̃) satisfies the conditions (1) and (2). For any x ∈ RD, we set y(l) := Convidw[1:l],b[1:l](x) ∈ RC (l)×D. We will prove
ConvReLU w̃[1:l],b̃[1:l]
(x) = [ y
(l) + y (l) −
]> (4)
for l = 1, . . . , L by induction. Note that we obtain fReLU(·) = (fid+(·), fid−(·)) by setting l = L. For l = 1, by definition of w̃(1) we have,
(w̃(1))α,:,:x β,: =
[ (w(1))α,:,:x β,: −(w(1))α,:,:xβ,: ]
for any α, β ∈ [D]. Summing them up and using the definition of b̃(1) yield
[Lw̃ (1) (x)− 1D ⊗ b̃(1)]> =
[ Lw (1) (x)− 1D ⊗ b(1)
− ( Lw (1) (x)− 1D ⊗ b(1) )]>
Suppose (4) holds up to l (l < L), by the definition of w̃(l+1),
(w̃(l+1))α,:,:
[ (y
(l) + ) β,:
(y (l) − ) β,:
] = [ (w(l+1))α,:,: −(w(l+1))α,:,: −(w(l+1))α,:,: (w(l+1))α,:,: ] [ (y (l) + ) β,:
(y (l) − ) β,:
]
=  (w(l+1))α,:,: ((y(l)+ )β,: − (y(l)− )β,:) −(w(l+1))α,:,: ( (y (l) + ) β,: − (y(l)− )β,: )
=
[ (w(l+1))α,:,:(y (l))β,: −(w(l+1))α,:,:(y(l))β,: ]
for any α, β ∈ [D]. Again, by taking the summation and using the definition of b̃(l+1), we get
[Lw̃ (l+1) ([y (l) + , y (l) − ])− 1D ⊗ b̃(1)]> =
[ Lw (l+1) (y(l))− 1D ⊗ b(l+1)
− ( Lw (l+1) (y(l))− 1D ⊗ b(l+1) )]> .
By applying ReLU, we get
Convp (l+1),ReLU
w̃(l+1),b̃(l+1)
( [y
(l) + , y (l) − ] ) = ReLU ( [y(l+1),−y(l+1)] ) . (5)
By using the induction hypothesis, we get
ConvReLU w̃[1:(l+1)],b̃[1:(l+1)]
(x) = Convp (l+1),ReLU
w̃(l+1),b̃(l+1)
( [y
(l) + , y (l) − ] )
= ReLU ( [y(l+1),−y(l+1)] )
= [y (l+1) + ,−y (l+1) − ]
Therefore, the claim holds for l + 1. By induction, the claim holds for L, which is what we want to prove.

heading: C.3 CONCATENATION OF CNNS
text: We can concatenate two CNNs with the same depths and filter sizes in parallel. Although it is almost trivial, we state it formally as a proposition. In the following proposition, C(0) and C ′(0) is not necessarily 1.
Proposition 1. Let C = (C(l))l∈[L], C ′ = (C ′ (l) )l∈[L], and K = (K(l))l∈[L] ∈ NL>0. Let w(l) ∈ RK(l)×C(l)×C(l−1) , b ∈ RC(l) and denote w = (w(l))l and b = (b(l))l. We define w′ and b′ in the same way, with the exception that C(l) is replaced with C ′(l). We define w̃ = (w̃(1), . . . , w̃(L)) and b̃ = (b̃(1), . . . , b̃(L)) by
(w̃(l))k,:,: :=
[ w(l) 0
0 w′ (l)
] ∈ R(C (l)+C′(l))×(C(l−1)+C′(l−1))
b̃(l) :=
[ b(l)
b′ (l)
] ∈ R(C (l)+C′(l))
for l ∈ [L] and k ∈ [K(l)]. Then, we have,
Convσ w̃,b̃ ([x x′]) = [ Convσw,b(x) Conv σ w′,b′(x ′) ]
for any x, x′ ∈ RD×C(0) and any σ : R→ R.
Note that by the definition of ‖ · ‖0 and ‖ · ‖∞, we have L∑ l=1 ‖w̃(l)‖0 = L∑ l=1 ‖w(l)‖0 + ‖w′ (l)‖0,
L∑ l=1 ‖b̃(l)‖0 = L∑ l=1 ‖b(l)‖0 + ‖b′ (l)‖0,
max l∈[L] ‖w̃(l)‖∞ = max l∈[L] ‖w(l)‖∞ ∨ ‖w′ (l)‖∞, and
max l∈[L] ‖b̃(l)‖∞ = max l∈[L] ‖b(l)‖∞ ∨ ‖b′ (l)‖∞.

heading: C.4 PROOF OF THEOREM 1
text: By the definition of F (FNN) D,B(bs),B(fin) , there exists a 4-tuple θ = ((W (l)m )m,l, (b (l) m )m,l, (wm)m, b) compatible with (D(l)m )m,l (m ∈ [M ] and l ∈ [Lm]) such that
max m∈[M ],l∈[Lm] (‖W (l)m ‖∞ ∨ ‖b(l)m ‖∞) ≤ B(bs), max m∈[M ] ‖wm‖∞ ∨ |b| ≤ B(fin),
and f (FNN) = FNNReLUθ . We will construct the desired CNN consisting of M residual blocks, whose m-th residual block is made from the ingredients of the corresponding m-th block in f (FNN) (specifically,Wm := (W (l) m )l∈[Lm], bm := (b (l) m )l∈[Lm], and wm).
[The m = 0 Block]: We prepare a single convolutional layer with 2 output channels and 2 size-1 filters suth that the first filter works as the identity function and the second filter inserts zeros to the second channel. Weight parameters of this convolutional layer are all zeros except single one. We denote this block by Conv0.
[Them = 1, . . . ,M Blocks]: For fixed m ∈ [M ], we first create a CNN realizing FCReLUWm,bm . We treat the first layer (i.e. l = 1) of FCReLUWm,bm as concatenation of D (1) m hinge functions RD 3 x 7→ fd(x) := ((W (1) m )dx− b(1)m )+ for d ∈ [D(1)m ]. Here, (W (1)m )d ∈ R1×D is the d-th row of the matrix W (1) m ∈ RD (1) m ×D. We apply Lemma 1 and Lemma 2 and obtain ReLU CNNs realizing the hinge functions. By combining them in parallel using Proposition 1, we have a learnable parameter θ(1)m
such that the ReLU CNN ConvReLU θ (1) m : RD×2 → RD×2D(1)m constructed from θ(1)m satisfies
ConvReLU θ (1) m
([x x′] > )1 = [ f1(x) ∗ · · · fD(1)m (x) ∗ ]> .
Since we double the channel size in them = 0 part, the identity mapping has 2 channels. Therefore, we made ConvReLU
θ (1) m so that it has 2 input channels and neglects the input signals coming from the second one. This is possible by adding filters consisting of zeros appropriately.
Next, for l-th layer (l = 2, . . . , Lm), we prepare size-1 filters w (2) m ∈ R1×D (2) m ×2D (1)
m for l = 2 and w (l) m ∈ R1×D (l) m ×2D (l−1) m for l = 3, . . . , D(Lm)m defined by
(w(l)m )1,:,: :=
{ W (2) m ⊗ [ 1 0 ] if l = 2
W (l) m if l = 3, . . . , D (Lm) m ,
where ⊗ is the Kronecker product of matrices. Intuitively, the l = 2 layer will pick all odd indices of the output of ConvReLU
θ (1) m and apply the fully-connected layer. Note that ConvReLU θ (l) m (l ≥ 2) just rearranges parameters of FCReLUWm,bm .
We construct CNNs from θ(l)m := (w (l) m , b (l) m ) (l ≥ 2) and concatenate them along with ConvReLUθ(1)m :
Convm := Conv ReLU
θ (Lm) m ◦ · · · ◦ ConvReLU θ (2) m ◦ ConvReLU θ (1) m .
The output dimension of Convm is either RD×2D (Lm) m (if Lm = 1) or RD×D (Lm) m (if Lm ≥ 2)., We denote the output channel size (either 2D(Lm)m or D (Lm) m ) by D (out) m . By the inductive calculation, we have
Convm(x)1 =
{ FCReLUWm,bm(x)⊗ [ 1 0 ] if Lm = 1
FCReLUWm,bm(x) if Lm ≥ 2 .
By definition, Convm has the depth of L0 + Lm − 1, at most 4D(1)m ∨ maxl=2,...Lm D (l) m ≤ 4 maxl∈[Lm]D (l) m channels. The ∞-norm of its parameters does not exceed that of parameters in FCReLUWm,bm .
Next, we consider the filter w̃m ∈ R1×2×D (out) m defined by
(w̃m)1,:,: = B(bs)
B(fin)  [ 0 · · · 0 wm ⊗ [ 0 1 ]] if Lm = 1[ 0 · · · 0
wm
] if Lm ≥ 2 ,
Then, Conv′m := Conv id w̃m,0 adds the output of m-th residual block, weighted by wm, to the second channel in the identity connections, while keeping the first channel intact. Note that the final layer of each residual block does not have the ReLU activation. By definition, Conv′m has D (Lm) m parameters.
Given Convm and Conv′m for each m ∈ [M ], we construct a CNN realizing FNN ReLU θ . Let f (conv) : RD → RD be the sequential interleaving concatenation of Convm and Conv′m, that is,
f (conv) := (Conv′M ◦ ConvM + I) ◦ · · · ◦ (Conv ′ 1 ◦ Conv1 + I) ◦ Conv0.
Then, we have
f (conv) 1 =
B(bs)
B(fin) M∑ m=1 w>mFC ReLU Wm,bm
(the subscript 1 represents the first coordinate). [Final Fully-connected Layer] Finally, we set w := [ B(fin)
B(bs) 0 · · · 0
] ∈ RD and put FCidw,b
on top of f (conv) to pick the first coordinate of f (conv) and subtract the bias term. By definition, f (CNN) := FCidw,b ◦ f (conv) satisfies f (CNN) = f (FNN).
[Condition Check]: We will check f (FNN) satisfies the desired conditions. (Condition 1): By definition the 0-th residual block Conv0 has L′0 = 1 layer. Since Convm and Conv ′ m has L0 + Lm − 1 and 1 layers, respectively, the m(≥ 1)-th residual block of f (CNN) has L′m = L0 + Lm layers. (Condition 2): Convm has at most 4 maxl∈[Lm]D (l) m channels and Conv′m has at most 2 channels, respectively. Therefore, the channel size of f (CNN) is at most 4 maxm∈[M ],l∈[Lm]D (l) m . (Condition 3): Since each filter of Conv(m) and Conv′m is at most K, the filter size of CNN is also at most K. (Conditions on B(conv) and B(fin)): Parameters of f (conv) are either 0, or parameters of FCReLUWm,Wm , whose absolute value is bounded by B (bs), or B (bs) B(fin) wm. Since we have ‖wm‖∞ ≤ B(fin), the ∞-norm of parameters in f (CNN) is bounded by B(bs). The parameters of the final fully-connected layer FCw,b is either B(fin), 0, or b, therefore their norm is bounded by B(fin) B(bs) ∨B(fin). Remark 3. Another way to construct a CNN which is identical (as a function) to a given FNN is as follows. First, we use a “rotation” convolution with D filters, each of which has a size D, to serialize all input signals to channels of a single input dimension. Then, apply size-1 convolution layers, whose l-th layer consisting of appropriately arranged weight parameters of the l-th layer of the FNN. This is essentially what Petersen & Voigtlaender (2018) does to prove the existence of a CNN equivalent to a given FNN. To restrict the size of filters to K, we should further replace the the first convolution layer withO(D/K) convolution layers with size-K filters. We can show essentially same statement using this construction method.

heading: D PROOF OF THEOREM 2

heading: D.1 COVERING NUMBER OF CNNS
text: The goal of this section is to prove Lemma 4, stated in Section D.1.5, that evaluates the covering number of the set of functions realized by CNNs F (CNN).

heading: D.1.1 BOUNDS FOR CONVOLUTIONAL LAYERS
text: We assume w,w′ ∈ RK×J×I , b, b′ ∈ R, and x ∈ RD×I unless specified. We have in mind that the activation function σ is either the ReLU function or the identity function id. But the following proposition holds for any 1-Lipschitz function such that σ(0) = 0. Remember that we can treat Lw as a linear operator from RD×I to RD×J . We endow RD×I and RD×J with the sup norm and denote the operator norm Lw by ‖Lw‖op. Proposition 2. It holds that ‖Lw‖op ≤ IK‖w‖∞.
Proof. Write w = (wkji)k∈[K],j∈[J],i∈[I], Lw = ((Lw) β,j α,i)α,β∈[D],j∈[J],i∈[I]. For any x = (xα,i)α∈[D],i∈[I] ∈ RD×I , the sup norm of y := (yβj)β∈[D]j∈[J] = Lw(x) is evaluated as follows:
‖y‖∞ = max β,j |yβ,j |
≤ max β,j ∑ α,i |(Lw)β,jα,i ||x α,i|
≤ max β,j ∑ α,i |(Lw)β,jα,i |‖x‖∞
= max β,j ∑ α,i |w(α−β+1),j,i|‖x‖∞
≤ max β,j ∑ α,i ( 1{w(α−β+1),j,i 6= 0} ) ‖w‖∞‖x‖∞
≤ IK‖w‖∞‖x‖∞
Proposition 3. It holds that ‖Convσw,b(x)‖∞ ≤ ‖Lw‖op‖x‖∞ + |b|.
Proof. ‖Convσw,b(x)‖∞ ≤ ‖σ(Lw(x)− 1D ⊗ b)‖∞
≤ ‖Lw(x)− 1D ⊗ b‖∞ ≤ ‖Lw(x)‖∞ + ‖1D ⊗ b‖∞ ≤ ‖Lw‖op‖x‖∞ + |b|.
Proposition 4. The Lipschitz constant of Convσw,b is bounded by ‖Lw‖op.
Proof. For any x, x′ ∈ RD×I , ‖Convσw,b(x)− Conv σ w,b(x
′)‖∞ = ‖σ (Lw(x)− 1D ⊗ b)− σ (Lw(x′)− 1D ⊗ b) ‖∞ ≤ ‖ (Lw(x)− 1D ⊗ b)− (Lw(x′)− 1D ⊗ b) ‖∞ ≤ ‖Lw(x− x′)‖∞ ≤ ‖Lw‖op‖x− x′‖∞.
Note that the first inequality holds because the ReLU function is 1-Lipschitz.
Proposition 5. It holds that ‖Convσw,b(x)− Conv σ w′,b′(x)‖ ≤ ‖Lw−w ′‖op‖x‖∞ + |b− b′|.
Proof.
‖Convσw,b(x)− Conv σ w′,b′(x)‖ = ‖σ(Lw(x)− 1D ⊗ b)− σ(Lw ′ (x)− 1D ⊗ b′)‖∞
≤ ‖(Lw(x)− 1D ⊗ b)− (Lw ′ (x)− 1D ⊗ b′)‖ = ‖Lw(x)− Lw ′ (x)‖+ ‖1D ⊗ (b− b′)‖∞ ≤ ‖Lw−w ′ ‖op‖x‖∞ + |b− b′|

heading: D.1.2 BOUNDS FOR FULLY-CONNECTED LAYERS
text: In the following propositions in this subsection, we assume W,W ′ ∈ RD×C , b, b′ ∈ R, and x ∈ RD×C . Again, these propositions hold for any 1-Lipschitz function σ : R→ R such that σ(0) = 0. But σ = ReLU or id is enough for us. Proposition 6. It holds that |FCσW,b(x)| ≤ ‖W‖0‖W‖∞‖x‖∞ + |b|.
Proof.
|FCσW,b(x)| ≤ |vec(W )>vec(x)− b| ≤ |vec(W )>vec(x)|+ |b|
≤ ∑ α,i ∣∣Wα,ixα,i∣∣+ |b| The number of non-zero summand in the summation is at most ‖W‖0 and each summand is bounded by ‖W‖∞‖x‖∞ Therefore, we have |FCσW,b(x)| ≤ ‖W‖0‖W‖∞‖x‖∞ + ‖b‖∞.
Proposition 7. The Lipschitz constant of FCσW,b is bounded by ‖W‖0‖W‖∞.
Proof. For any x, x′ ∈ RD×C , |FCσW,b(x)− FC σ W,b(x
′)| ≤ ‖(vec(W )>vec(x)− b)− (vec(W )>vec(x′)− b)‖ ≤ ‖vec(W )>(vec(x)− vec(x′))‖ ≤ ‖W‖0‖W‖∞‖vec(x)− vec(x′)‖∞.
Proposition 8. It holds that |FCσW,b(x)− FC σ W ′,b′(x)| ≤ (‖W‖0 + ‖W ′‖0)‖W −W ′‖∞‖x‖∞ + |b− b′|.
Proof.
|FCσW,b(x)− FC σ W ′,b′(x)| ≤ |(vec(W )>vec(x)− b)− (vec(W ′)>vec(x)− b′)|
= |(vec(W −W ′)>vec(x)− (b− b′)| ≤ |(vec(W −W ′)>vec(x)|+ |b− b′| ≤ ‖W −W ′‖0‖W −W ′‖∞‖x‖∞ + |b− b′| ≤ (‖W‖0 + ‖W ′‖0)‖W −W ′‖∞‖x‖∞ + |b− b′|

heading: D.1.3 BOUNDS FOR RESIDUAL BLOCKS
text: In this section, we denote the architecture of CNNs by C = (C(l))l∈[L] ∈ NL>0 and K = (K(l))l∈[L] ∈ NL>0 and the norm constraint on the convolution part by B(conv) (C(0) need not equal to 1 in this section). Let wl, w′(l) ∈ RK(l)×Cl×C(l−1) and b(l), b′(l) ∈ R. We denote w := (w(l))l∈[L], b := (b(l))l∈[L], w′ := (w′ (l) )l∈[L], and b := (b(l))l∈[L].
For 1 ≤ l ≤ l′ ≤ L, we denote ρ(l, l′) := ∏l′ i=l(C (i−1)K(i)B(conv)) and ρ+(l, l′) := ∏l′ i=l 1 ∨ (C(i−1)K(i)B(conv)).
Proposition 9. Let l ∈ [L]. We assume maxl∈[L] ‖w(l)‖∞ ∨ ‖b(l)‖∞ ≤ B(conv). Then, for any x ∈ [−1, 1]D×C(0) , we have ‖Convσw[1:l],b[1:l](x)‖∞ ≤ ρ(1, l)‖x‖∞ +B(conv)lρ+(1, l).
Proof. We write in shorthand as C[s:t] := Conv σ w[s:t],b[s:t]. Using Proposition 3 recursively, we get
‖C[1:l](x)‖∞ ≤ ‖Lw (l) ‖op‖C[1:l−1](x)‖∞ + ‖b(l)‖∞ . . .
≤ ‖x‖∞ l∏ i=1 ‖Lw (i) ‖op + l∑ i=2 ‖b(i−1)‖∞ l∏ j=i ‖Lw (j) ‖op + ‖b(l)‖∞.
By Proposition 2 and assumptions ‖w(i)‖∞ ≤ B(conv) and ‖b(i)‖∞ ≤ B(conv), it is further bounded by
‖x‖∞ l∏ i=1 (C(i−1)K(i)B(conv)) +B(conv) l∑ i=2 l∏ j=i (C(j−1)K(j)B(conv)) +B(conv)
≤ ρ(1, l)‖x‖∞ +B(conv)lρ+(1, l)
Proposition 10. Let ε > 0, suppose maxl∈[L] ‖w(l)−w′ (l)‖∞ ≤ ε and maxl∈[L] ‖b(l)− b′ (l)‖∞ ≤ ε, then ‖C[1:L]−C ′[1:L](x)‖∞ ≤ (Lρ(1, L)‖x‖∞+(1∨B (conv))L2ρ+(1, l))ε for any x ∈ RD×C(0) .
Proof. For any l ∈ [L], we have∣∣∣C ′[l+1:L] ◦ (Cl − C ′l) ◦ C[1:l−1](x)∣∣∣ ≤ ‖C ′[l+1:L] ◦ (Cl − C ′ l) ◦ C[1:l−1](x)‖∞
≤ ρ(l + 1, L) ∥∥(Cl − C ′l) ◦ C[1:l−1](x)∥∥∞ (by Proposition 2 and 4)
≤ ρ(l + 1, L) ( ρ(l, l)‖C[1:l−1]‖∞ε+ ε ) (by Proposition 2 and 5)
≤ ρ(l + 1, L) ( ρ(l, l)(ρ(1, l − 1)‖x‖∞ +B(conv)(l − 1)ρ+(1, l − 1)) + 1 ) ε (by Proposition 9)
= ( ρ(1, L)‖x‖∞ + (1 ∨B(conv))lρ+(1, L) ) ε (6)
Therefore,
‖C[1:L](x)− C ′[1:L](x)‖∞ ≤ L∑ l=1 ‖C[l+1:L] ◦ (Cl − C ′l) ◦ C[1:l−1](x)‖∞
≤ (Lρ(1, L)‖x‖∞ + (1 ∨B(conv))L2ρ+(1, l))ε

heading: D.1.4 PUTTING THEM ALL
text: Let M ∈ N>0, Lm ∈ N>0, C(l)m ,K(l)m ∈ N>0, C := (C(l)m )m,l, and K := (K(l)m )m,l for m = 0, . . . ,M and l ∈ [Lm]. Let θ = ((w(l)m )m,l, (b(l)m )m,l,W, b) and θ′ = ((w′(l)m )m,l, (b′ (l) m )m,l,W ′, b′) be tuples compatible with (C,K) such that CNNReLUθ , CNN ReLU θ′ ∈ F (CNN) C,K,B(conv),B(fc) for some S ∈ N>0 and B(conv), B(fc) > 0. We denote the l-th convolution layer of the m-th block by C(l)m and the m-th residual block of by Cm:
C(l)m :=
{ Convid
w (l) m (if l = Lm) ConvReLU
w (l) m
(otherwise)
Cm := C (Lm) m ◦ · · · ◦ C(1)m .
Also, we denote by C[m:m′] the subnetwork of Conv ReLU θ between the m-th and m ′-th block. That is,
C[m:m′] := { (Cm′ + I) ◦ · · · ◦ (Cm + I) (if m ≥ 1) (Cm′ + I) ◦ · · · ◦ Cm (if m = 0)
for m,m′ = 0, . . . ,M . We define C ′(l)m , C ′ m and C ′ [m:m′] similarly for θ ′.
Proposition 11. For m = 0, . . .M and x ∈ [−1, 1]D, we have ‖C[0:m](x)‖∞ ≤ (1 ∨ B(conv)) ( ∏m i=0(1 + ρi)) ( 1 + ∑m i=0 Liρ + i ) . Here, ρm and ρ+m are constants defined in Theorem 2.
Proof. By using Proposition 9 inductively, we have
‖C[0:m](x)‖∞ ≤ ‖Cm(C[0:m−1](x)) + C[0:m−1](x)‖∞ ≤ ‖(1 + ρm)C[0:m−1](x) +B(conv)Lmρ+m)‖∞ ≤ (1 + ρm)‖C[0:m−1](x)‖∞ +B(conv)Lmρ+m · · ·
≤ ‖C0(x)‖∞ m∏ i=1 (1 + ρi) +B (conv) m∑ i=1 Liρ + i m∏ j=i+1 (1 + ρj)
≤ ρ0 m∏ i=1 (1 + ρi) +B (conv) m∑ i=0 Liρ + i m∏ j=i+1 (1 + ρj)
≤ (1 ∨B(conv)) ( m∏ i=0 (1 + ρi) )( 1 + m∑ i=0 Liρ + i ) .
Lemma 3. Let ε > 0. Suppose θ and θ′ are within distance ε, that is, maxm,l ‖w(l)m −w′(l)m ‖∞ ≤ ε, ‖b(l)m − b′(l)m ‖∞ ≤ ε, ‖W −W ′‖∞ ≤ ε, and ‖b− b′‖∞ ≤ ε. Then, ‖CNN ReLU θ − CNN ReLU θ′ ‖∞ ≤ M1ε where M1 is the function defined in Theorem 2.
Proof. For any x ∈ [−1, 1]D, we have∣∣CNNReLUθ (x)− CNNReLUθ′ (x)∣∣ = ∣∣∣FCidW,b ◦ C[0:M ](x)− FCidW ′,b′ ◦ C ′[0:M ](x)∣∣∣ = ∣∣∣(FCidW,b − FCidW ′,b′) ◦ C[0:M ](x)∣∣∣
+ M∑ m=0 ∣∣∣FCidW ′,b′ ◦ C[m+1:M ] ◦ (Cm − C ′m) ◦ C ′[0:m−1](x)∣∣∣ . (7) We will bound each term of (7). By Proposition 8 and Proposition 11,∣∣∣(FCidW,b − FCidW ′,b′) ◦ C[0:M ](x)∣∣∣
≤ (‖W‖0 + ‖W ′‖0)‖W −W ′‖∞‖C[0:M ](x)‖∞ + ‖b− b′‖∞ ≤ 2C(L0)0 D‖C[0:M ](x)‖∞ε+ ε
≤ 2C(L0)0 D(1 ∨B(conv)) ( M∏ m=0 (1 + ρm) )( 1 + M∑ m=0 Lmρ + m ) ε+ ε
≤ 3C(L0)0 D(1 ∨B(conv)) ( M∏ m=0 (1 + ρm) )( 1 + M∑ m=0 Lmρ + m ) ε (8)
On the other hand, for m = 0, . . . ,M ,∣∣∣FCidW ′,b′ ◦ C ′[m+1:M ] ◦ (Cm − C ′m) ◦ C[0:m−1](x)∣∣∣ ≤ ‖W ′‖0‖W ′‖∞‖C ′[m+1:M ] ◦ (Cm − C ′ m) ◦ C[1:m−1](x)‖∞ (by Proposition 7)
≤ C(L0)0 DB(fc)‖C ′[m+1:M ] ◦ (Cm − C ′ m) ◦ C[0:m−1](x)‖∞ ≤ C(L0)0 DB(fc) ( M∏ i=m+1 ρi )∥∥(Cm − C ′m) ◦ C[0:m−1](x)∥∥∞ (by Proposition 2 and 4) ≤ C(L0)0 DB(fc) ( M∏
i=m+1
ρi )( ρm‖C[0:m−1]‖∞ε+ ε ) (by Proposition 2 and 5)
≤ C(L0)0 DB(fc) ( M∏ i=m+1 ρi )( ρm(1 ∨B(conv)) ( m−1∏ i=0 (1 + ρi) )( 1 + m−1∑ i=0 Liρ + i ) + 1 ) ε
(by Proposition 9)
≤ 2C(L0)0 DB(fc)(1 ∨B(conv)) ( M∏ i=0 (1 + ρi) )( 1 + M∑ i=0 Liρ + i ) ε (9)
By applying (8) and (9) to (7), we have
|CNNReLUθ (x)− CNN ReLU θ′ (x)|
≤ 3C(L0)0 D(1 ∨B(conv)) ( M∏ m=0 (1 + ρm) )( 1 + M∑ m=0 Lmρ + m ) ε
+ 2MC (L0) 0 DB (fc)(1 ∨B(conv)) ( M∏ m=0 (1 + ρm) )( 1 + M∑ m=0 Lmρ + m ) ε
≤ (2M + 3)C(L0)0 D(1 ∨B(fc))(1 ∨B(conv)) ( M∏ m=0 (1 + ρm) )( 1 + M∑ m=0 Lmρ + m ) ε
= M1ε.

heading: D.1.5 BOUNDS FOR COVERING NUMBER OF CNNS
text: For a metric space (M0, d) and ε > 0, we denote the (external) covering number of M ⊂ M0 by N (ε,M, d): N (ε,M, d) := inf{N ∈ N | ∃f1, . . . , fN ∈ M0 s.t. ∀f ∈ M,∃n ∈ [N ] s.t. d(f, fn) ≤ ε}.
Lemma 4. Let B := B(conv) ∨B(fc). For ε > 0, we have N (ε,F (CNN), ‖ · ‖∞) ≤ ( 2BM1 ε )M2 . Proof. The idea of the proof is same as that of Lemma 12 of Schmidt-Hieber (2017). We divide the interval of each parameter range ([−B(conv), B(conv)] or [−B(fc), B(fc)]) into bins with width εM1 (i.e., 2B(conv)M1ε−1 or 2B(fc)M1ε−1 bins for each interval). If f, f ′ ∈ F (CNN) can be realized by parameters such that every pair of corresponding parameters are in a same bin, then, ‖f −f ′‖∞ ≤ ε by Lemma 3. We make a subset F0 of F (CNN) by picking up every combination of bins for M2 parameters. Then, for each f ∈ F (CNN), there exists f0 ∈ F0 such that ‖f − f0‖∞ ≤ ε. There are at most 2BM1ε−1 choices of bins for each parameter. Therefore, the cardinality of F0 is at most(
2BM1 ε )M2 .

heading: D.2 PROOF OF THEOREM 2 AND COROLLARY 1
text: We use the lemma in Schmidt-Hieber (2017) to bound the estimation error of the clipped ERM estimator f̂ . Since our problem setting is slightly different from one in the paper, we restate the statement.
Lemma 5 (cf. Schmidt-Hieber (2017) Lemma 10). Let F be a family of measurable functions from [−1, 1]D to R. Let f̂ be the clipped ERM estimator of the regression problem described in Section 3.1. Suppose the covering number of F satisfiesN (ε,F , ‖ · ‖∞) ≥ 3. Then, ED‖f◦ − f̂‖2L2(PX) ≤
4 ( inff∈F ‖f − f◦‖2L2(PX) + ( 56 logN (F , 1N , ‖ · ‖∞) + 180 ) F̃ 2 N ) , where F̃ := RFσ ∨ ‖f◦‖∞ σ ∨ 1 2 and RF := sup{‖f‖∞ | f ∈ F}.
Proof. Basically, we convert our problem setting so that it fits to the assumptions of Lemma 10 of Schmidt-Hieber (2017) and apply the lemma to it. For f : [−1, 1]D → [−σF̃ , σF̃ ], we define A[f ] : [0, 1]D → [0, 2F̃ ] byA[f ](x′) := 1σf(2x
′−1)+F̃ . Let f̂1 be the (non-clipped) ERM etimator of F . We define X ′ := 12 (X + 1), f
′◦ := A[f◦], Y ′ := f ′◦(X) + ξ′, F ′ := {A[f ] | f ∈ F}, f̂ ′1 := A[f̂1], and D′ := ((x′n, y′n))n∈[N ] where x′n := 12 (xn + 1) and y ′ n := f ′◦(x′n) + 1 σ (yn − f
◦(xn)). Then, the probability that D′ is drawn from P ′⊗N is same as the probability that D is drawn from P⊗N where P ′ is the joint distribution of (X ′, Y ′). Also, we can show that f̂ ′ is the ERM estimator of the regression problem Y ′ = f ′◦+ξ′ using the datasetD′: f̂ ′1 ∈ arg minf ′∈F ′ R̂D′(f ′). We apply the Lemma 10 of Schmidt-Hieber (2017) with n← N , d← D, ε← 1, δ ← 1N , ∆n ← 0, F
′ ← F , F ← 2F̃ , f̂ ← f̂ ′1 and use the fact that the estimation error of the clipped ERM estimator is no worse than that of the ERM estimator, that is, ‖f◦− f̂‖2L2(PX) ≤ ‖f ◦− f̂1‖2L2(PX) to conclude.
Proof of Theorem 2. By definition of ‖ · ‖∞, we have ‖f − f◦‖L2(PX) ≤ ‖f − f◦‖∞ for any f ∈ F . By Lemma 4, logN := logN ( 1N ,F
(CNN), ‖ · ‖∞) ≤ M2 log(2BM1N), where B = B(conv) ∨B(fc). Therefore, by Lemma 5,
‖f◦ − f̂‖2L2(PX) ≤ 4 ( inf f∈F ‖f − f◦‖2L2(PX) + (56 logN + 180) F̃ 2 N )
≤ C ( inf f∈F ‖f − f◦‖2∞ + M2F̃ 2 N log(2BM1N) ) .
Proof of Corollay 1. We only care the order with respect to N in the O-notation. Set M = bNαc for α ≥ 0. Using the assumptions of the corollary, the estimation error is
‖f◦ − f̂‖2L2(Px) = Õ ( max ( N−2αγ1 , Nαγ2−1 )) .
by Theorem 2. The order of the right hand side with respect to N is minimized when α = 12γ1+γ2 . By substituting α, we can show Corollary 1.

heading: E PROOF OF COROLLARY 2 AND COROLLARY 3
text: By Theorem 2 of Klusowski & Barron (2016), for each M ∈ N>0, there exists
f (FNN) := 1
M M∑ m=1 bm(a > mx− tm)+ = M∑ m=1 bm ( a>m M x− tm M ) +
with |bm| ≤ 1, ‖am‖1 = 1, and |tm| ≤ 1 such that ‖f◦−f (FNN)‖∞ ≤ Cvf◦ √ logM +DM− 1 2− 1 D where C > 0 is a universal constant. We set Lm ← 1, D(1)m ← 1, B(bs) ← 1M , B (fin) ← 1 (m ∈ [M ]) in the Theorem 1, then, we have f (FNN) ∈ F (FNN) D1,B(bs),B(fin) . By applying Theorem 1, there exists a CNN f (CNN) ∈ F (CNN) C,K,B(conv),B(fc) such that f (FNN) = f (CNN). Here, C = (C(1)m )m with C(1)m = 4, K = (K (1) m )m with K (1) m = K, B(conv) = 1M , and B
(fc) = M . This proves Corollary 2.
With these evaluations, we have M1 = O(M3) (note that since B(conv) = 1M , we have ∏M m=0(1 + ρm) = O(1)). In addition, B(conv) is O(1) and B(fc) is O(M). Therefore, we have logM1B = Õ(1). Since M2 = O(M), we can use Corollary 1 with γ1 = 12 + 1 D , γ2 = 1. Since we have
M = O ( N 1 2γ1+γ2 ) by the proof of Corollary 1, we can derive the bounds for B(conv), and B(fc)
with respect to N .

heading: F PROOF OF COROLLARY 4 AND COROLLARY 5
text: We first prove the scaling property of the FNN class.
Lemma 6. Let M ∈ N>0, Lm ∈ N>0, and D(l)m ∈ N>0 for m ∈ [M ] and l ∈ [Lm]. Let B(bs), B(fin) > 0. Then, for any k ≥ 1, we have F (FNN)
D,B(bs),B(fin) ⊂ F (FNN) D,k−1B(bs),kLB(fin) where
L := maxm∈[M ] Lm is the maximum depth of the blocks.
Proof. Let θ = ((W (l)m )m,l, (b (l) m )m,l, (wm)m, b) be the parameter of an FNN and suppose that FNNReLUθ ∈ F (FNN) D,B(bs),B(fin) . We define θ′ := ((W ′(l)m )m,l, (b ′(l) m )m,l, (w ′ m), b ′) by
W ′ (l) m := k − LLmW (l)m b ′(l) m := k −l LLm b(l)m w ′ m := k Lwm b ′ := b.
Since k ≥ 1, we have FNNReLUθ′ ∈ F (FNN) D,k−1B(bs),kLB(fin) . Also, by the homogeneous property of the ReLU function (i.e., ReLU(ax) = aReLU(x) for a > 0), we have FNNReLUθ = FNN ReLU θ′ .
Next, we prove the existence of a block-sparse FNN with constant-width blocks that optimally approximates a given β-Hölder function. It is almost same as the proof of Theorem 5 of SchmidtHieber (2017). However, we need to construct the FNN so that it has a block-sparse structure. Lemma 7 (cf. Schmidt-Hieber (2017) Theorem 5 ). Let β > 0, M ∈ N>0 and f◦ : [−1, 1]D → R be a β-Hölder function. Then, there exists D′ := O(1) ∈ N>0, L′ := O(logM) > 0 (C1 and C2 are constants independent of M ) and a block-sparse FNN f (FNN) ∈ F (FNN)D,1,2M‖f◦‖β such that ‖f◦ − f (FNN)‖∞ = Õ(M− β D ). Here, we set Lm := L′ and D (l) m := D′ for all m ∈ [M ] and l ∈ [Lm] and defineD := (D(l)m )m,l.
Proof. First, we prove the lemma when the domain of f◦ is [0, 1]D. Let M ′ be the largest interger satisfying (M ′ + 1)D ≤M . Let Γ(M ′) = ( Z M ′ )D ∩ [0, 1]D = {m′M ′ | m′ ∈ {0, . . . ,M ′}D} be the set of lattice points in [0, 1]D3. Note that the cardinality of Γ(M ′) is (M ′ + 1)D. Let P βa f
◦ be the Taylor expansion of f◦ up to order bβc at a ∈ [0, 1]D:
(P βa f ◦)(x) = ∑ 0≤|α|<β (∂αf◦)(a) α! (x− a)α.
For a ∈ [0, 1]D, we define a hat-shaped function Ha : [0, 1]D → [0, 1] by
Ha(x) := D∏ j=1 (M ′ −1 − |xj − aj |+).
Note that we have ∑ a∈Γ(M ′)Ha(x) = 1, i.e., they are a partition of unity. Let P
βf◦ be the weighted sum of the Taylor expansions at lattice points of Γ(M ′):
(P βf◦)(x) := M ′ D ∑ a∈D(M ′) (P βa f ◦)(x)Ha(x).
By Lemma 7 of Schmidt-Hieber (2017), we have
‖P βf◦ − f◦‖∞ ≤ ‖f◦‖βM ′ −β .
Let m be an interger specified later and set L∗ := (m + 5)dlog2De. By the proof of Lemma 8 of Schmidt-Hieber (2017), for any a ∈ Γ(M ′), there exists an FNN Hata : [0, 1]D → [0, 1] whose depth and width are at most 2 + L∗ and 6D, respectively and whose parameters have sup-norm 1, such that
‖Hata −Ha‖∞ ≤ 3 D2−m.
Next, let B := 2‖f◦‖β and CD,β be the number of distinct D-variate monomials of degree up to bβc. By the equation (7.11) of Schmidt-Hieber (2017), for any a ∈ Γ(M), there exists an FNN Qa : [0, 1]
D → [0, 1] 4 whose depth and width are 1 + L∗ and 6DCD,β respectively and whose parameters have sup-norm 1, such that∥∥∥∥Qa − (P βa f◦B + 12 )∥∥∥∥ ∞ ≤ 3D2−m.
Thirdly, by Lemma 4 of Schmidt-Hieber (2017), there exists an FNN Mult : [0, 1]2 → [0, 1], whose depth and width are m+ 4 and 6, respectively and whose parameters have sup-norm 1 such that
|Mult(x, y)− xy| ≤ 2−m
for any x, y ∈ [0, 1]. For each a ∈ Γ(M ′), we combine Hata and Qa using Mult and constitute a block of the block-sparse FNN corresponding to a ∈ Γ(M) by FCa := Mult(Qa(·),Hata(·)). Then, we have ∥∥∥∥FCa − (P βa f◦B + 12 ) Ha ∥∥∥∥ ∞ ≤ 2−m + 3D2−m + 3D2−m
≤ 3D+12−m.
We define f (FNN)(x) := ∑ a∈Γ(M)(BM ′DFCa(x))−B2 . By construction, f (FNN) is a block-sparse FNN with (M ′+1)D(≤M) blocks each of which has depth and width at mostL′ := 2+L∗+(m+4)
3Schmidt-Hieber (2017) used D(M ′) to denote this set of lattice points. We used different character to avoid notational conflict.
4We prepare Qa for each a ∈ Γ(M) as opposed to the original proof of Schmidt-Hieber (2017), in which Qa’s shared the layers the except the final one and were collectively denoted by Q1.
and D′ := 6(CD,β + 1)D, respectively. The norms of the block-sparse part and the finally fullyconnected layer are 1 and BM ′D(≤ BM), respectively. In addition, we have |f (FNN)(x)− (P βf◦)(x)|
≤ ∑
a∈Γ(M)
BM ′ D ∣∣∣∣FCa(x)− ( (P βa f◦)(x)B + 12 ) Ha(x) ∣∣∣∣+ B2 ∣∣∣∣∣∣1−M ′D ∑ a∈Γ(M ′) Ha(x) ∣∣∣∣∣∣ ≤ (M ′ + 1)D ×BM ′D3D+12−m
≤ 3D+12−mBM2
for any x ∈ [0, 1]D. Therefore, |f (FNN)(x)− f◦(x)| ≤ |f (FNN) − (P βf◦)(x)|+ |(P βf◦)(x)− f◦(x)|
≤ B3D+1M22−m + ‖f◦‖βM−β
≤ 2‖f◦‖β3D+1M22−m + ‖f◦‖βM− β D 2β .
We set m = dlog2M2+ β D e, then, we have L′ = O(logM), D′ = O(1), and
‖f (FNN) − f◦‖ ≤ ‖f◦‖β(2 · 3D+1 + 2β)M− β D .
By the defnition of f (FNN) we have f (FNN) ∈ F (FNN)D,1,2‖f◦‖βM .
When the domain of f◦ is [−1, 1]D, we should add the function x 7→ 12 (x + 1) = 1 2 (x + 1)+ − 1 2 (−x − 1)+ as a first layer of each block to fit the range into [0, 1]
D. Specifically, suppose the first layer of m-th block in f (FNN) is x 7→ ReLU(Wx − b), then the first two layers become x 7→ ReLU( [ 1 2 (x+ 1) − 1 2 (x+ 1) ] ) and [y1 y2] 7→ ReLU(Wy1 − Wy2 − b), respectively. Since this transformation does not change the maximum sup norm of parameters in the block-sparse and the order of L′ and D′, the resulting FNN is still belongs to F (FNN)D,1,2‖f◦‖M .
Proof of Corollary 4 and Corollary 5. In this proof, we only care the dependence on M in the O-notation. Let M̃ := 2‖f◦‖βM . By Lemma 7, there exists f (FNN) ∈ F (FNN)D,1,M̃ such that
‖f (FNN) − f◦‖∞ = O ( M− β D ) (L′, D′, andD as in Lemma 7). Let k := 16D′K(M 1 L′ ∧ 1)−1 =
16D′K(e 1 C′ ∧ 1)−1 ≥ 1 where C ′ is a constant such that L′ = C ′ logM . Using, Lemma 6, there exists f̃ (FNN) ∈ F (FNN) D,k−1,kL′M̃ such that f̃ (FNN) = f (FNN). We apply Theorem 1 to F (FNN) D,k−1,kL′M̃ and find f (CNN) ∈ F (CNN) C,K,B(conv),B(fc)
such that L ≤ M(L′ + L0), C := (C(l)m )m=0,...,M,l∈[Lm] with C(l)m ≤ 4D′, K := (K(l)m )m=0,...,M,l∈[Lm] with K (l) m ≤ K, B(conv) = k−1, B(fc) = kL ′ (k ∨ 1)M̃ = kL′+1M̃ , and f (CNN) = f̃ (FNN). By definition, we have B(conv) = k−1 = O(1) and logB(fc) = (L′ + 1)k + log(M̃) = O(logM). This proves Corollary 4.
By the definition of k and the bound on C(l)m and K (l) m , we have C (l−1) m K (l) m k−1 ≤ 14M − 1 L′ . Therefore, we have ρm ≤ ∏L′ l=1(C (l−1) m K (l) m k−1) ≤ M−1 and hence ∏M m=0(1 + ρm) = O(1). Since C (l−1) m K (l) m k−1 ≤ 12 for sufficiently large M , we have ρ + m = 1 for sufficiently large M . In addition, we have log(B(conv) ∨ B(fc)) = Õ(1). Combining them, we have logM1 = Õ(1) and hence logM1(B
(conv) ∨ B(fc)) = Õ(1). For M2, we can bound it by M2 = O(M logM) using bounds for C(l)m , K (l) m and L′. Therefore, we can apply Corollary 2 with γ1 = βD , γ2 = 1 and obtain the
desired estimation error. Since we have M = O ( N 1 2γ1+γ2 ) by the proof of Corollary 1, we can
derive the bounds for Lm, B(conv), and B(fc) with respect to N .

heading: G COMPARISON OF OUR CNNS AND ORIGINAL RESNET
text: There are several differences between the CNN in this paper and the original ResNet, aside from the number of layers. First and foremost, our CNN does not have pooling nor Batch Normalization
(Ioffe & Szegedy (2015)) layers. It is left for future research whether our result can extend to the ResNet-type CNNs with pooling or Batch Normalization layers. Second, our CNN does not have ReLU activation after the junction points and the final layer of the 0-th block, while they have in the original ResNet. We choose this design to make proofs simpler. We can easily extend our results to the architecture that adds the ReLU activations to those points with slight modifications using similar techniques appeared in Lemma 2 of the appendix.

Review summaries:
This manuscript shows the statistical error of the ERM for nonparametric regression using the family of a Resnet-type of CNNs. Specifically, two results are showed. First, the authors show that any block-sparse fully connected neural network can be embedded in CNNs. Second, they show the covering number of the family of CNNs. Combining with the existing results of the approximation error of neural nets (Klusowski&Barron 2016, Yarotsky 2017, Schmidt-Hieber 2017), they show the L2 statistical risk. 

The authors demonstrate the function expression properties for the Residual type convolutional neural networks to approximate the block sparse fully connected neural networks. Then it is shown that such Res-CNNs can approximate any function as long as it can be expressed by the block-sparse FNNs, including the Barron class and Holder class functions. The price to pay is that the number of parameters is larger than that of the FNNs by a constant factor.