Deep learning has achieved significant success in various practical applications with high-dimensional data set, such as computer vision (Krizhevsky et al., 2012), natural language processing (Graves et al., 2013;Young et al., 2018;Wu et al., 2016), health care (Miotto et al., 2018;Jiang et al., 2017) and bioinformatics (Alipanahi et al., 2015;Zhou & Troyanskaya, 2015).
International Conference on Machine Learning, PMLR 139, 2021. Copyright 2021 by the author(s).
The success of deep learning clearly demonstrates the great power of neural networks in representing complex data. In the past decades, the representation power of neural networks has been extensively studied. The most commonly studied architecture is the feedforward neural network (FNN), as it has a simple composition form. The representation theory of FNNs has been developed with smooth activation functions (e.g., sigmoid) in Cybenko (1989); Barron (1993); McCaffrey & Gallant (1994); Hamers & Kohler (2006); Kohler & Krzyżak (2005); Kohler & Mehnert (2011) or nonsmooth activations (e.g., ReLU) in Lu et al. (2017); Yarotsky (2017); Lee et al. (2017); Suzuki (2019). These works show that if the network architecture is properly chosen, FNNs can approximate uniformly smooth functions (e.g., Hölder or Sobolev) with arbitrary accuracy. In real-world applications, convolutional neural networks (CNNs) are more popular than FNNs (LeCun et al., 1989;Krizhevsky et al., 2012;Sermanet et al., 2013;He et al., 2016;Chen et al., 2017;Long et al., 2015;Simonyan & Zisserman, 2014;Girshick, 2015). In a CNN, each layer consists of several filters (channels) which are convolved with the input, as demonstrated in Figure 1(a). Due to such complexity in the CNN architecture, there are limited works on the representation theory of CNNs (Zhou, 2020b;a;Fang et al., 2020;Petersen & Voigtlaender, 2020). The constructed CNNs in these works become extremely wide (in terms of the size of each layer's output) as the approximation error goes to 0. In most real-life applications, the network width does not exceed 2048 (Zagoruyko & Komodakis, 2016;Zhang et al., 2020).
Convolutional residual networks (ConvResNet) is a special CNN architecture with skip-layer connections, as shown in Figure 1(b). Specifically, in addition to CNNs, ConvRes-Nets have identity connections between inconsecutive layers. In many applications, ConvResNets outperform CNNs in terms of generalization performance and computational efficiency, and alleviate the vanishing gradient issue. Using this architecture, He et al. (2016) won the 1st place on the ImageNet classification task with a 3.57% top 5 error in 2015.
Recently, Oono & Suzuki (2019) , which is far beyond the sample size used in practical applications. For example, the ImageNet data set consists of 1.2 million labeled images of size 224 ⇥ 224 ⇥ 3. According to this theory, to achieve a 0.1 error, the sample size is required to be in the order of 10 224⇥224⇥3 which greatly exceeds 1.2 million. Due to the curse of dimensionality, there is a huge gap between theory and practice.
We bridge such a gap by taking low-dimensional geometric structures of data sets into consideration. It is commonly believed that real world data sets exhibit low-dimensional structures due to rich local regularities, global symmetries, or repetitive patterns (Hinton & Salakhutdinov, 2006;Osher et al., 2017;Tenenbaum et al., 2000). For example, the ImageNet data set contains many images of the same object with certain transformations, such as rotation, translation, projection and skeletonization. As a result, the degree of freedom of the ImageNet data set is significantly smaller than the data dimension (Gong et al., 2019).
The function space considered in Oono & Suzuki (2019) is the Hölder space in which functions are required to be differentiable everywhere up to certain order. In practice, the target function may not have high order derivatives. Function spaces with less restrictive conditions are more desirable. In this paper, we consider the Besov space B s p,q , which is more general than the Hölder space. In particular, the Hölder and Sobolev spaces are special cases of the Besov space:
for any 0 < p, q 1, s 2 N and ↵ 2 (0, 1]. For practical applications, it has been demonstrated in image processing that Besov norms can capture important features, such as edges (Jaffard et al., 2001). Due to the generality of the Besov space, it is shown in Suzuki & Nitanda (2019) that kernel ridge estimators have a sub-optimal rate when estimating Besov functions.
In this paper, we establish theoretical guarantees of Con-vResNets for the approximation of Besov functions on a low-dimensional manifold, and a statistical theory on binary classification. Let M be a d-dimensional compact Riemannian manifold isometrically embedded in R D . Denote the Besov space on M as B s p,q (M) for 0 < p, q 1 and 0 < s < 1. Our function approximation theory is established for B s p,q (M). For binary classification, we are given n i.i.d. samples {(x i , y i )} n i=1 where x i 2 M and y i 2 { 1, 1} is the label. The label y follows the Bernoullitype distribution
for some ⌘ : M ! [0, 1]. Our results (Theorem 1 and 2) are summarized as follows:
Theorem (informal). Assume s d/p + 1.
1. Given " 2 (0, 1), we construct a ConvResNet architecture such that, for any f ⇤ 2 B s p,q (M), if the weight parameters of this ConvResNet are properly chosen, it gives rises to f satisfying
2. Assume ⌘ 2 B s p,q (M). Let f ⇤ be the minimizer of the population logistic risk. If the ConvResNet architecture is properly chosen, minimizing the empirical logistic risk gives rise to b f ,n with the following excess risk bound
and C is a constant independent of n.
We remark that the first part of the theorem above requires the network size to depend on the intrinsic dimension d and only weakly depend on D. (2019). Among these works, Zhou (2020b) shows that CNNs can approximate Sobolev functions in W s,2 for s D/2 + 2 with an arbitrary accuracy " 2 (0, 1). The network in Zhou (2020b) has width increasing linearly with respect to depth and has depth growing in the order of " 2 as " decreases to 0. It is shown in Petersen & Voigtlaender (2020); Zhou (2020a) that any approximation error achieved by FNNs can be achieved by CNNs. Combining Zhou (2020a) and Yarotsky (2017), we can show that CNNs can approximate W s,1 functions in R D with arbitrary accuracy ". Such CNNs have the number of channels in the order of " D/s and a cardinality constraint. The only theory on ConvResNet can be found in Oono & Suzuki (2019), where an approximation theory for Hölder functions is proved for ConvResNets with fixed width.
Statistical theories for binary classification by FNNs are established with the hinge loss (Ohn & Kim, 2019;Hu et al., 2020) and the logistic loss (Kim et al., 2018). Among these works, Hu et al. (2020) uses a parametric model given by a teacher-student network. The nonparametric results in Ohn & Kim (2019); Kim et al. (2018) are cursed by the data dimension, and therefore require a large number of samples for high-dimensional data.
Binary classification by CNNs has been studied in Kohler et al. (2020); Kohler & Langer (2020); Nitanda & Suzuki (2018); Huang et al. (2018). Image binary classification is studied in Kohler et al. (2020); Kohler & Langer (2020) Montanelli & Yang (2020). These works show that, if data are near a low-dimensional manifold, the performance of FNNs depends on the intrinsic dimension of the manifold and only weakly depends on the data dimension. Our work focuses on ConvResNets for practical applications.
The networks in many aforementioned works have a cardinality constraint. From the computational perspective, training such networks requires substantial efforts (Han et al., 2016;2015;Blalock et al., 2020). In comparison, the ConvResNet in Oono & Suzuki (2019) and this paper does not require any cardinality constraint. Additionally, our constructed network has a fixed filter size and a fixed number of channels, which is desirable for practical applications.
As a summary, we compare our approximation theory and existing results in Table 1.
The rest of this paper is organized as follows: In Section 2, we briefly introduce manifolds, Besov functions on manifolds and convolution. Our main results are presented in Section 3. We give a proof sketch in Section 4 and conclude this paper in Section 5.
Notations: We use bold lower-case letters to denote vectors, upper-case letters to denote matrices, calligraphic letters to denote tensors, sets and manifolds. For any x > 0, we use dxe to denote the smallest integer that is no less than x and use bxc to denote the largest integer that is no larger than x. For any a, b 2 R, we denote a _ b = max(a, b). For a function f : R d ! R and a set ⌦ ⇢ R d , we denote the restriction of f to ⌦ by f | ⌦ . We use kf k L p to denote the L p norm of f . We denote the Euclidean ball centered at c with radius ! by B ! (c).
We first introduce some concepts on manifolds. We refer the readers to Tu (2010); Lee (2006) for details. Throughout this paper, we let M be a d-dimensional Riemannian manifold M isometrically embedded in R D with d D. We first introduce charts, an atlas and the partition of unity. bijective, and1 are both continuous).
In a chart (U, ), U is called a coordinate neighborhood and is a coordinate system on U . A collection of charts which covers M is called an atlas of M.
and are pairwise C k compatible:
for any ↵, 2 A. An atlas is called finite if it contains finitely many charts. Definition 3 (Smooth Manifold). A smooth manifold is a manifold M together with a C 1 atlas.
The Euclidean space, the torus and the unit sphere are examples of smooth manifolds. C s functions on a smooth manifold M are defined as follows:
Definition 4 (C s functions on M). Let M be a smooth manifold and f : M ! R be a function on M. We say f is a C s function on M, if for every chart (U, ) on M, the function f
We next define the C 1 partition of unity which is an important tool for the study of functions on manifolds.
1. there is a neighbourhood of x where only a finite number of the functions in {⇢ ↵ } ↵2A are nonzero, and 2.
An open cover of a manifold M is called locally finite if every x 2 M has a neighbourhood which intersects with a finite number of sets in the cover. The following proposition shows that a C 1 partition of unity for a smooth manifold always exists (Spivak, 1970, Chapter 2, Theorem 15).
Proposition 1 (Existence of a C 1 partition of unity). Let {U ↵ } ↵2A be a locally finite cover of a smooth manifold M. There is a C 1 partition of unity
The reach of M introduced by Federer (Federer, 1959) is an important quantity defined below. Let d(x, M) = inf y2M kx yk 2 be the distance from x to M. Definition 6 (Reach (Federer, 1959;Niyogi et al., 2008)).
The closure of G is called the medial axis of M. The reach of M is defined as
We illustrate large and small reach in Figure 2. ! R be in L p (⌦) for p > 0, the r-th modulus of smoothness of f is defined by
The norm of the Besov space B s p,q (⌦) is defined as kf k B s p,q (⌦) := kf k L p (⌦) + |f | B s p,q (⌦) . The Besov space is B s p,q (⌦) = {f 2 L p (⌦)|kf k B s p,q < 1}. We next define B s p,q functions on M (Geller & Pesenson, 2011;Triebel, 1983;1992).
Definition 9 (B s p,q Functions on M). Let M be a compact smooth manifold of dimension d. Let {(U i , i )} C M i=1 be a finite atlas on M and {⇢ i } C M i=1 be a partition of unity on
Since ⇢ i is supported on U i , the function
The extended function lies in the Besov space B s p,q (R d ) (Triebel, 1992, Chapter 7).
In this paper, we consider one-sided stride-one convolution in our network. Let W = {W j,k,l } 2 R C 0 ⇥K⇥C be a filter where C 0 is the output channel size, K is the filter size and C is the input channel size. For z 2 R D⇥C , the convolution of W with z gives y 2 R D⇥C 0 such that
where 1 i D, 1 j C 0 and we set z i+k 1,l = 0 for i + k 1 > D, as demonstrated in Figure 3(a).
The building blocks of ConvResNets are residual blocks.
For an input x, each residual block computes x + F (x) where F is a subnetwork consisting of convolutional layers (see more details in Section 3.1). A residual block is demonstrated in Figure 3 . Here W = {W j,k,l } 2 R C 0 ⇥K⇥C is a filter where C 0 is the output channel size, K is the filter size and C is the input channel size. Wj,:,: is a D ⇥ C matrix for the j-th output channel. (b) Demonstration of a residual block.
In this section, we first introduce the ConvResNet architecture, and then present our main results.
We study the ConvResNet with the rectified linear unit (ReLU) activation function: ReLU(z) = max(z, 0). The ConvResNet we consider consists of a padding layer and several residual blocks followed by a fully connected feedforward layer.
We first define the padding layer. Given an input A 2 R D⇥C1 , the network first applies a padding operator P :
In the m-th block, let W m = {W } be a collection of filters and biases. The m-th residual block maps a matrix from R D⇥C to R D⇥C by Conv Wm,Bm + id, where id is the identity operator and
with ReLU applied entrywise. Denote
For networks only consisting of residual blocks, we define the network class as
is in the form of (4) with M residual blocks.
Each block has filter size bounded by K, number of channels bounded by J, max
where k•k 1 denotes `1 norm of a vector, and for a tensor
Based on the network Q in (4), a ConvResNet has an additional fully connected layer and can be expressed as
where W and b are the weight matrix and the bias in the fully connected layer. The class of ConvResNets is defined as
Sometimes we do not have restriction on the output, we omit the parameter R and denote the network class by C(M, L, J, K, 1 , 2 ).
Our approximation theory is based on the following assumptions of M and the object function
Assumption 3 implies that f ⇤ is Lipschitz continuous (Triebel, 1983, Section 2.7.1 Remark 2 and Section 3.3.1).
Our first result is the following universal approximation error of ConvResNets for Besov functions on M.
Theorem 1. Assume Assumption 1-3. For any " 2 (0, 1) and positive integer K 2 [2, D], there is a ConvRes-Net architecture C(M, L, J, K, 1 , 2 ) such that, for any f ⇤ 2 B s p,q (M), if the weight parameters of this ConvRes-Net are properly chosen, the network yields a function
Such a network architecture has
The constant hidden in O(•) depend on d, s, 2d sp d , p, q,c 0 , ⌧ and the surface area of M.
The architecture of the ConvResNet in Theorem 1 is illustrated in Figure 4. It has the following properties:
• The network has a fixed filter size and a fixed number of channels.
• There is no cardinality constraint.
• The network size depends on the intrinsic dimension d, and only weakly depends on D.
Theorem 1 can be compared with Suzuki (2019)
We next consider binary classification on M. For any x 2 M, denote its label by y 2 { 1, 1}. The label y follows the following Bernoulli-type distribution
We assume the following data model:
Assumption 4. We are given i.i.d. sample {(x i , y i )} n i=1 , where x i 2 M, and the y i 's are sampled according to (10).
In binary classification, a classifier f predicts the label of x as sign(f (x)). To learn the optimal classifier, we consider the logistic loss (z) = log(1 + exp( z)). The logistic risk
For any classifier f , we define its logistic excess risk as
In this paper, we consider ConvResNets with the following architecture:
where M 1 , M 2 , L, J, K, 1 , 2 , 3 are some parameters to be determined.
The empirical classifier is learned by minimizing the empirical logistic risk:
We establish an upper bound on the excess risk of b f ,n :
Theorem 2. Assume Assumption 1, 2 and 4. Assume 0 < p, q 1, 0 < s < 1, s d/p+1 and ⌘ 2 B s p,q (M) with k⌘k B s p,q c 0 for some constant c 0 . For any 2 K D, we set
for some constant C. Here C is linear in D log D and additionally depends on d, s, 2d sp d , p, q, c 0 , ⌧ and the surface area of M. The constant hidden in O(•) depends on d, s, 2d sp d , p, q, c 0 , ⌧ and the surface area of M. Theorem 2 shows that a properly designed ConvResNet gives rise to an empirical classifier, of which the excess risk converges at a fast rate with an exponent depending on the intrinsic dimension d, instead of D.
Theorem 2 is proved in Appendix A. Each building block of C (n) is constructed for the following purpose:
which is realized by Theorem 1.
• ḡ2 h is designed to approximate a truncated univariate function log z 1 z .
We provide a proof sketch of Theorem 1 in this section.
More technical details are deferred to Appendix C.
We prove Theorem 1 in the following four steps:
1. Decompose f ⇤ = P i f i as a sum of locally supported functions according to the manifold structure. 2. Locally approximate each f i using cardinal B-splines. 3. Implement the cardinal B-splines using CNNs. 4. Implement the sum of all CNNs by a ConvResNet for approximating f ⇤ .
Step 1: Decomposition of f ⇤ . • Construct an atlas on M. Since the manifold M is compact, we can cover M by a finite collection of open balls B ! (c i ) for i = 1, . . . , C M , where c i is the center of the ball and ! is the radius to be chosen later. Accordingly, the manifold is partitioned as Niyogi et al., 2008, Lemma 5.4). The total number of partitions is then bounded by
, where SA(M) is the surface area of M and T d is the average number of U i 's that contain a given point on M (Conway et al., 1987, Chapter 2 Equation (1)).
On each partition, we define a projection-based transformation i as i (x) = a i V > i (x c i ) + b i , where the scaling factor a i 2 R and the shifting vector b i 2 R d ensure i (U i ) ⇢ [0, 1] d , and the column vectors of V i 2 R D⇥d form an orthonormal basis of the tangent space T ci (M). The atlas on M is the collection (U i , i ) for i = 1, . . . , M. See Figure 5 for a graphical illustration of the atlas.
• Decompose f ⇤ according to the atlas. We decompose
where
i=1 is guaranteed by Proposition 1. As a result, each f i is supported on a subset of U i , and therefore, we can rewrite (17) as
where 1 Ui is the indicator function of U i . Since i is a bijection between U i and i (U i ), f i
The extended function is in B s p,q ([0, 1] d ) (see Lemma 4 in Appendix C.1). This allows us to use cardinal B-splines to locally approximate each f i 1 i as detailed in Step 2.
Step 2: Local cardinal B-spline approximation. We approximate f i 1 i using cardinal B-splines e f i as
where
Here k is a scaling factor, j is a shifting vector, m is the degree of the B-spline and d is the dimension (see a formal definition in Appendix C.2).
Since s d/p + 1 (by Assumption 3), setting r = +1, m = dse + 1 in Lemma 5 (see Appendix C.3) and applying Lemma 4 gives
for some constant C depending on s, p, q and d.
Combining ( 18) and ( 19), we approximate f ⇤ by
Such an approximation has error
Step 3: Implement local approximations in Step 2 by CNNs. In Step 2, (21) gives a natural approximation of f ⇤ . In the sequel, we aim to implement all ingredients of e f i,j i ⇥ 1 Ui using CNNs. In particular, we show that CNNs can implement the cardinal B-spline e f i,j , the linear projection i , the indicator function 1 Ui , and the multiplication operation.
• Implement 1 Ui by CNNs. Recall our construction of
To implement 1 Ui , we rewrite it as the composition of a univariate indicator function 1 [0,! 2 ] and the distance function
We show that CNNs can efficiently implement both 1 [0,! 2 ] and d 2 i given ✓ 2 (0, 1) and 8DB 2 ✓, there exist CNNs that yield functions e 1 and e
where C 1 is a constant depending on s, p, q and d. The constant hidden in O(•) depends on d, s, 2d sp d , p, q, c 0 . The CNN class F CNN is defined in Appendix B.
• Implement the multiplication ⇥ by a CNN. According to Lemma 7 (see Appendix C.4) and Lemma 8, for any ⌘ 2 (0, 1), the multiplication operation ⇥ can be approximated by a CNN e ⇥ with L 1 error ⌘:
Such a CNN has O (log 1/⌘) layers, 6 channels. All parameters are bounded by max(2c 2 0 , 1).
Step 4: Implement e f ⇤ by a ConvResNet. We assemble all CNN approximations in Step 3 together and show that the whole approximation can be realized by a ConvResNet.
• Assemble all ingredients together. Assembling all CNN approximations together gives an approximation of e f i,j
After substituting ( 27) into (21), we approximate the target function f ⇤ by
The approximation error of f is analyzed in Lemma 12 (see Appendix C.9). According to Lemma 12, the approximation error can be bounded as follows:
where , ⌘, and ✓ are defined in ( 25), ( 26), ( 24) and ( 23), respectively. For any " 2 (0, 1), with properly chosen , ⌘, and ✓ as in (53) in Lemma 12, one has
With these choices, the network size of each CNN is quantified in Appendix C.10.
• Realize f by a ConvResNet. Lemma 17 (see Appendix C.15) shows that for every fi,j , there exists f CNN i,j 2 F CNN (L, J, K, 1 , 2 ) with L = O(log 1/"+D+ log D), J = O(D), 1 = O(1), log 2 = O log 2 1/" such that f CNN i,j (x) = fi,j (x) for any x 2 M. As a result, the function f in (28) can be expressed as a sum of CNNs:
Our results show that ConvResNets are adaptive to lowdimensional geometric structures of data sets. Specifically, we establish a universal approximation theory of ConvRes-Nets for Besov functions on a d-dimensional manifold M.
Our network size depends on the intrinsic dimension d and only weakly depends on D. We also establish a statistical theory of ConvResNets for binary classification when the given data are located on M. The classifier is learned by minimizing the empirical logistic loss. We prove that if the ConvResNet architecture is properly chosen, the excess risk of the learned classifier decays at a fast rate depending on the intrinsic dimension of the manifold.
Our ConvResNet has many practical properties: it has a fixed filter size and a fixed number of channels. Moreover, it does not require any cardinality constraint, which is beneficial to training.
Our analysis can be extended to multinomial logistic regression for multi-class classification. In this case, the network will output a vector where each component represents the likelihood of an input belonging to certain class. By assuming that each likelihood function is in the Besov space, we can apply our analysis to approximate each function by a ConvResNet.