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 \textit{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\"older 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\"older class. Our proof is based on sophisticated evaluations of the covering number of CNNs and the non-trivial parameter rescaling technique to control the Lipschitz constant of CNNs to be constructed. 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) , Giné & Nickl (2015) ) in important function classes, including the Hö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., Bö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 with O(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 Hölder class. We prove, as corollaries, that our CNNs can achieve the approximation error of orderÕ(M ) for the β-Hö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 β-Hö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 Hö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 Hölder case. 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 Hö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 Hö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 Hö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.
It is shown that ResNet-type CNNs are a universal approximator and its expression ability is not worse than fully connected neural networks (FNNs) with a \textit{block-sparse} structure even if the size of each layer in the CNN is fixed.
{"src": "scitldr-AIC_train", "paper_id": "HklnzhR9YQ"}