Theory of Deep Convolutional Neural Networks II: Spherical Analysis

Deep learning based on deep neural networks of various structures and architectures has been powerful in many practical applications, but it lacks enough theoretical verifications. In this paper, we consider a family of deep convolutional neural networks applied to approximate functions on the unit sphere $\mathbb{S}^{d-1}$ of $\mathbb{R}^d$. Our analysis presents rates of uniform approximation when the approximated function lies in the Sobolev space $W^r_\infty (\mathbb{S}^{d-1})$ with $r>0$ or takes an additive ridge form. Our work verifies theoretically the modelling and approximation ability of deep convolutional neural networks followed by downsampling and one fully connected layer or two. The key idea of our spherical analysis is to use the inner product form of the reproducing kernels of the spaces of spherical harmonics and then to apply convolutional factorizations of filters to realize the generated linear features.


Introduction
Deep learning has attracted tremendous attention from various fields of science and technology recently. Wide applications including those in image processing [9] and speech recognition [12] have received great successes. Based on deep neural network structures, it has a strong capability of obtaining data features and distinguishes itself from classical machine learning methods. Though it is successful in practical applications, theoretical assurances are still lacking and need to be investigated. Many attempts have been made trying to understand the practical power of deep neural networks [3,18].
The classical (shallow) neural networks to approximate functions or process data on R d take the form 1) where N is the number of neurons called width, are parameters corresponding to connection weights, biases, and coefficients, w k , x = w k · x is the inner product in R d , and σ : R → R is an activation function. Approximation of functions on subsets of R d by shallow neural networks (1.1) was studied well around the late 1980s. See [19,5] and references therein. As a natural extension of shallow nets, fully connected deep neural networks (DNNs) have been developed since the 1990s. A fully connected DNN of input x = (x 1 , x 2 , . . . , x d ) ∈ R d with J hidden layers of neurons DNNs designed by convolutions are called deep convolutional neural networks (CNNs) and have been very successful in image classification and related applications [16]. Such a network is associated with a sequence of convolutional filters w = {w (j) : Z → R} J j=1 , where w (j) is supported in 0, · · · , S (j) for some S (j) ∈ N called filter length. The convolution of such a filter w supported in {0, · · · , S} with another sequence v = (v 1 , . . . , v D ) is a sequence w * v given by which is supported in {1, · · · , D + S}. Then by restricting the convoluted sequence onto its support, for input x = (x 1 , x 2 , . . . , x d ) ∈ R d , a deep CNNs with J hidden layers of neurons {h (j) : R d → R d j } and widths d j = d j−1 + S (j) is defined iteratively by h (0) (x) = x and By inducing a Toeplitz type convolutional matrix ..,D+S,k=1,...,D associated with a filter w of filter length S and D ∈ N given explicitly by a deep CNN can be regarded as a special sparse form of a fully connected DNNs with the full connection matrices F (j) in (1.2) replaced by the sparse Toeplitz convolutional matrices T (j) := T w (j) with D = d j−1 and S = S (j) for j = 0, 1, . . . , J. That is, (1.3) becomes Compared with fully-connected DNNs, deep CNNs reduce the computational complexity by using at each layer a Toeplitz matrix due to the sparsity and convolutional nature. Throughout the paper we take an identical filter length S (j) ≡ S ∈ N implying {d j = d+jS} and take the rectified linear unit (ReLU) activation function It was shown in [33] that the output layer of any fully-connected DNN can be realized by a downsampled deep CNN with free parameters of the same order, and that deep CNNs can approximate ridge functions of the form g(ξ ·x) with univariate functions g and unknown ξ ∈ R d to the same accuracy with much smaller number of free parameters. Universality of approximation by deep CNNs was also established in [32] where rates of approximation were provided for restrictions of functions from the Sobolev space H r (R d ) with a regularity index r > 2 + d/2. The regularity index r is large when d increases and is essentially needed in the analysis there due to the function regularity on the whole Euclidean space R d . Note that the issue of approximating non-smooth functions by fully connected DNNs has been studied in [28,13]. Moreover, the Sobolev space H r (R d ) requires derivatives of various orders to belong to the L 2 space, while the approximation considered in [32] is measured in the L ∞ norm.
In this paper, we overcome the difficulty in the large regularity index and the inconsistency of L 2 and L ∞ norms for the setting with data from the unit sphere S d−1 in R d . With our novel analysis conducted with spherical harmonic expansions, we can present rates of approximating functions from the Sobolev space W r ∞ (S d−1 ) (to be defined below) on S d−1 , with any positive index r, by downsampled deep CNNs defined in [33] followed by two fully connected layers.
where ⌊u⌋ denotes the integer part of u > 0.
After the last CNN layer, we add two fully connected layers h (J+1) , h (J+2) with widths D 1 , D 2 > 0, respectively, connection matrices F (J+1) , F (J+2) and bias vectors b (J+1) , b (J+2) , to be determined. Precisely, and Such a network with many convolutional layers followed by downsampling operations and very few fully connected layers is quite common in practical applications [16,9]. The hypothesis space of functions on S d−1 induced by our network is given by (1.9)

Main Results on Rates of Approximation
Our target is to establish rates of approximating functions in W r ∞ (S d−1 ) by those from the hypothesis space H J,D 1 ,D 2 ,S defined by (1.9). Since the sums of the rows in the middle of the Toeplitz type matrix (1.4) are equal, we impose for the bias vectors {b (j) } J j=1 of the convolutional layers a restriction b (j) For the two fully connected layers we take the widths for some positive integer N ∈ N and connection matrices Here the matrix Ξ D 2 , u takes a block form as Our first main result, to be proved in Section 5, can be stated as follows. A positive parameter τ (which can be arbitrarily small) is needed due to the continuous embedding of the Sobolev space W s 2 (S d−1 ) with s > d−1 2 into C(S d−1 ) found in Proposition 1 below.
Then for any f ∈ W r ∞ (S d−1 ), there exists a deep neural network consisting of J layers of CNNs with filters of length S and bias vectors satisfying (2.1) followed by downsampling and two fully connected layers with widths (2.2) and connection matrices (2.3) such that the hypothesis space H J,D 1 ,D 2 ,S contains a functionf satisfying where C r,d,τ,S is a constant independent of J or f . Moreover, the total number of free parameters N in the network can be bounded as Remark 1. To achieve the approximation accuracy f −f ∞ ≤ ǫ, we only need to take where we denote the smallest integer greater than or equal to u > 0 as ⌈u⌉.
When 0 < r < d − 1, we may set τ = 1 and see that the network achieving the approximation accuracy ǫ has depth J = O ǫ − 2d r and N = O ǫ − 2d r free parameters. When r > d − 1, we may set 0 < τ < r − (d − 1) and find the depth and the number of free parameters of this network are both of orders O (ǫ −2 ), slightly better than that in [32].
Our second main result aims at further demonstrating the superiority of deep CNNs over fully connected networks observed empirically in many practical applications. Motivated by our earlier work [33] on approximating ridge functions of type g(y · x) with y ∈ R d , g : R → R, and additive models (see, e.g., [4,24]) in statistics of the form f (x) = d j=1 g j (x j ) with univariate functions {g j } d j=1 , we consider a family of additive ridge functions of the form with y j ∈ S d−1 , g j : R → R for j ∈ {1, . . . , m}. The following theorem to be proved in Section 5 is about approximating additive ridge functions by deep CNNs followed by downsampling and one fully-connected layer. For 0 < α ≤ 1, denote the space of Lipschitz-α functions on for some 0 < α ≤ 1, then there exists a deep neural network consisting of J layers of CNNs with filters of length S and bias vectors satisfying (2.1) followed by downsampling and one fully connected layer h (J+1) with width (2N + 3)⌊(d + JS)/d⌋ and connection ma- The total number of free parameters N in the network can be bounded as

Remark 2.
To achieve an accuracy ǫ > 0 for approximating an additive ridge function (2.4) on S d−1 , we only need to take The total number of free parameters of the achieving network is of orders O ǫ − 1 α . This is the complexity required by the classical literature on fullyconnected networks to achieve an accuracy ǫ > 0 for approximating univariate functions. This extends our earlier work [33] from the ridge case with m = 1 to an additive ridge case with m ∈ N and hints the superiority of deep CNNs in approximating multivariate functions of special structures.

Spherical Analysis for Deep CNNs
In this section, we introduce ideas of our analysis before proving our main results. We first give a brief review on relevant concepts from spherical harmonic analysis and introduce some classes of functions. More details can be found in [6,29].

Spherical harmonics and Sobolev spaces on spheres
A spherical harmonic of degree n ∈ Z + on S d−1 is the restriction to S d−1 of a homogeneous and harmonic polynomial of total degree n defined on R d . Let H d n denote the set of all spherical harmonics of degree n on S d−1 . It can be found in [6] the dimension of the linear space H d n is The spaces H d n , n ∈ Z + , of spherical harmonics are mutually orthogonal with respect to the inner product of L 2 (S d−1 ). Since the space of spherical polynomials is dense in L 2 (S d−1 ), each f ∈ L 2 (S d−1 ) has a spherical harmonic expansion: is an orthonormal basis of H d n , f n,l is the Fourier coefficients of f given by and Proj n is the orthogonal projection of L 2 (S d−1 ) onto the subspace H d k of spherical harmonics, which has an integral representation: It can be readily shown that Z n (x, y) is the reproducing kernel of H d n independent of the choice of {Y n,l } N (n,d) where C λ n (t) is the Gegenbauer polynomial of degree n with parameter λ > −1/2, see, for instance, [6].
The spaces H d n of spherical harmonics can also be characterized as eigenfunction spaces of the Laplace-Beltrami operator ∆ 0 on S d−1 . Indeed, where λ n = n(n + d − 2) and C 2 (S d−1 ) denotes the space of all twice continuously differentiable functions on S d−1 . As a matter of fact, we may define the fractional power which is a self-adjoint operator on L 2 (S d−1 ) in the sense that is a Hilbert space with the inner product: f n,l g n,l .
In addition, we have the following continuous embedding lemma, see [11] and also [14, Eq. 14, p. 420]. By these lemmas, we know that the infinity norm can be bounded by the Sobolev norm when r > d−1 p .
where c r,d is a constant independent of f .

Near-best approximation and discretization
The best approximation of a function by those from polynomial spaces of various degrees might be nonlinear. A useful tool in spherical harmonic analysis is a linear scheme L n .

6)
where with λ = d−2 2 , l n is a kernel given by It can be found in [6,Chapter 4] that L n is near best, achieving the order of best approximation for f ∈ W r p (S d−1 ).
where c is a constant depending only on the function η in defining L n .
Note that since (−∆ 0 here and in what follows, we denote In fact, ζ n,r is a polynomial of degree at most 2n with expression The novelty here using a fractional power of (−∆ 0 + I) caused by the regularity of f ∈ W r ∞ (S d−1 ) enables us to get an r-dependent error bound for discretizing L n (f ): the larger the regularity index r, the smaller the bound.
To approximate the function L n (f ) by a neural network, we need a stepping stone, discretizing the integral form (3.6) to an empirical version given in terms of a sample y = {y 1 , . . . , y m } ⊂ S d−1 . The following estimate for the error L y n,m (f ) − L n (f ) will be proved by a probability inequality in Section 5. Such a probabilistic argument has been applied in [15].
, then for any n, m ∈ N, there exist y = {y 1 , y 2 , . . . , y m } ⊂ S d−1 such that where for θ ∈ R and n ∈ N we denote and C r,d,τ is a positive constant depending on r, d, τ but not on n, m or f .

Approximating ridge functions by deep CNNs
The last step in our spherical analysis of deep CNNs is to approximate the ridge function L y n,m (f ) by functions from the network with a bound to be proved in Section 5.

11)
where c ′ r,d is a constant depending only on r and d. The total number of free parameters N in the network can be bounded as

Comparison with Related Work
In this section, we give a brief review of related work on rates of function approximation by neural networks.
The fully connected shallow nets (1.1) or multi-layer nets (1.2) have nice approximation properties due to the fully connected nature, which was well studied in a large literature around 30 years ago. When the activation function is a C ∞ sigmoidal type function, approximation rates were obtained by many authors. In particular, in [1] rates were given for functions in f ∈ L 2 (R d ) whose Fourier transformsf satisfy a decay condition R d |w||f(w)|dw < ∞. Another typical result based on localized Taylor expansions asserts [19] that even for shallow nets (1.1) , if for some b ∈ R and some integer ℓ ∈ N \ {1}, the C ∞ activation function σ satisfies σ (k) (b) = 0 for all k ∈ Z + and lim u→−∞ σ(u)/|u| ℓ = 0 and lim u→∞ σ(u)/u ℓ = 1. These conditions required by the localized Taylor expansion approach are not satisfied by ReLU, so the approximation theory developed 30 years ago does not apply to ReLU. The difficulty was overcome in the recent deep learning literature and approximation properties of ReLU nets were established in [15] for ReLU shallow nets and functions satisfying R d |w||f(w)|dw < ∞, in [30,2,22,20] for deep nets and functions from W r ∞ ([−1, 1] d ) with 0 < r ≤ 2, and in [25] for approximation on manifolds. These results are obtained for fully connected nets.
Deep CNNs are different from fully connected nets. They have special sparse convolutional connection matrices (1.4), which leads to sparsity and reduces the computational complexity for structured data. Recently in [32], for functions f on Ω ⊂ [−1, 1] d satisfying f = F | Ω with F ∈ W r 2 R d and an integer index r > 2 + d/2, it was shown that the approximation accuracy f −f ∞ ≤ ǫ can be achieved by a deep CNN of depth 4⌈ 1 ǫ 2 log 1 ǫ 2 ⌉ and at most ⌈ 75 ǫ 2 log 1 ǫ 2 ⌉d free parameters. The linear increment of the free parameter number with respect to d improves the bound in Theorem 1 of [30] which requires at least 2 d ǫ −d/r free parameters and C 0 d 4 (log(1/ǫ)+d) fully connected layers with C 0 > 0 to achieve the same approximation accuracy ǫ. Periodized deep CNNs with different architectures and connection matrices different from the Toeplitz convolutional ones (1.4) were shown in [21,23] to be able to realize the output layer of any fully-connected DNN with free parameters of the same order. The same result was shown for deep CNNs (1.5) in [33].
The index r > 2 + d/2 required in [32] can be very large for processing high dimensional data. Hence approximated functions are required to possess high regularity which is not the usual case in applications. The problem happens because the approximation considered in [32] is measured in the L ∞ norm, while the Sobolev space H r (R d ) requires derivatives of various orders to belong to the L 2 space. This essentially causes the technical difficulty by To overcome the difficulty, we consider the case when the data is from the unit sphere S d−1 . The restriction can be relaxed in this situation through applying spherical harmonic expansions to construct a near best approximation for functions f ∈ W r ∞ (S d−1 ) in L ∞ norm, while the Sobolev embedding theorem is only used in discretizing integrals. In the literature, there have been some other harmonic analysis approaches in dealing with approximation by fully connected neural networks, using ridgelet transforms in [27], local Taylor expansions in [30], and B-spline functions in [28]. Our spherical harmonic analysis approach makes full use of the inner product nature (3.3) of the reproducing kernel of H d n which, after discretizing the polynomial approximation L n (f ) to L y n,m (f ), enables us to represent the linear transformations { y i , x } by deep CNNs with linearly increasing widths, an idea borrowed from our earlier work [32]. A key consequence of our approach is to allow the index r here to be an arbitrarily small positive number, which relaxes the restriction in [32] for the regularity of the approximated function. While the approximation of non-smooth functions is unified for r > 0 and the same order O (ǫ −2 ) for the number of network free parameters to achieve an approximation accuracy ǫ > 0 is kept when r > d − 1, a parameter number of order O ǫ − 2d r is required when 0 < r < d − 1. This is due to our approach of using a Hilbert space W s 2 (S d−1 ) in our probabilistic estimate for the discretization, which makes our rate suboptimal compared with [30,20,24] for r < d − 1. It would be interesting to derive optimal rates of approximating by deep CNNs functions from W r ∞ (S d−1 ) with small r. On the other hand, as stated in Remark 2, for an additive ridge function on S d−1 in the family (2.4), deep CNNs followed by a fully connected layer can extract linear features {y j } m j=1 and then approximate the function efficiently, with the same order of network free parameters as that for approximating a univariate function by fully connected DNNs. This demonstrates the superiority of deep CNNs in approximating functions with structures. It would be of great interest to explore other structures of multivariate functions for which deep CNNs together with network architectures like pooling and parallel channels may have super performance in function approximations and representations. Applying deep CNNs to some practical or empirical problems involving additive ridge functions (2.4) would also help understand advantages of convolutional structures of deep learning in some practical domains.

Proof of the Main Results
This section is devoted to the proof of our main analysis. Our analysis for the error f −f is carried out by means of the bounds for f − L n (f ) ∞ in Lemma 1, L n (f )− L y n,m (f ) ∞ in Lemma 2, and L y n,m (f )−f ∞ in Lemma 3.

Proving the lemma on discretization
To complete our analysis, we first prove Lemma 2 and Lemma 3. The proof of Lemma 2 is based on the following probability inequality for random variables with values in a Hilbert space which can be found in [26].
be independent random drawers of ρ. Then for any 0 < δ < 1, we have with confidence 1 − δ, Proof of Lemma 2. Recall that L n (f ) is defined by (3.6) with f ∈ W r ∞ (S d−1 ) and τ > 0. In applying Lemma 4 we take the Sobolev space W s 2 (S d−1 ) with the smoothness index s = τ + d−1 2 to be the Hilbert space H and the random variable ξ on S d−1 , σ d with values in H given by Then E(ξ) = L n (f ) and 1 m m i=1 ξ(y i ) = L y n,m (f ). To bound the norm ξ = ξ W s 2 , we recall the norm of W s 2 (S d−1 ) given by (3.4) with p = 2 and find for y ∈ S d−1 , . Then by the orthogonality and reproducing properties, where we have used the identity Z k (y, y) = N(k, d) found in [6] as Corollary 1. 2.7 and N(k, d) is the dimension of spherical harmonics H d k . Notice that for k ∈ N, k 2 < 1 + λ k ≤ dk 2 . We find (1 + λ k ) s−r ≤ d max{s−r,0} k 2(s−r) for either s − r ≥ 0 or s − r < 0. Since 0 ≤ η(t) ≤ 1 for t ∈ [0, 2], we can apply (3.1) to estimate the summation as Combining this with the definitions of the norm f W r ∞ (S d−1 ) and the function Λ τ (n), we know that ξ(y) 2 W s 2 can be bounded as This verifies (3.10) by the embedding Proposition 1 with p = 2 and s = τ

Proving the lemma on ridge approximation
The proof of Lemma 3 about approximating the function L y n,m (f ) is conducted by approximating the ridge functions l n ( y i , x ) in (3.9) with y i ∈ S d−1 ⊂ R d by deep CNNs. A key idea in our analysis is to use the inner product form (3.3) of the reproducing kernel of H d n and then to apply convolutional factorizations to realize the generated linear features, which enables us to conduct analysis after removing the restriction on large regularity index r. This idea might be applied to some other learning theory problems [8,10,17,34].
We first apply the following two lemmas proved in [32] implying that the linear function y i , x = y i · x can be realized by deep CNNs by factorizing y i regarded as a sequence into convolutions of filters supported in {0, 1, . . . , S}.
We then construct a fully connected layer to approximate the univariate function l n by continuous piecewise linear functions (splines) spanned by {σ(· − t i )} N i=1 with t i = −1 + i−2 N , based on the following well known result in approximation by splines which can be found in [7] and [31, Lemma 6].
Now we construct bias vectors in the neural networks. We denote for j = 2, · · · , J. The bias vectors satisfy b Hence the components of h (J) (x) satisfy where B (J) = Π J p=1 w (p) 1 . Applying the downsampling operator (1.6) leads to Hence d ≥ m.
We turn to expressing the last two fully connected layers. Of them, h (J+1) is given by with the connection matrix F ( where t := {t 1 < · · · < t 2N +3 } is given in Lemma 7. Note that F (J+1) is a determined matrix without free parameters. Then the first fully-connected layer h (J+1) (x) ∈ Rd (2N +3) of the deep network is for j = 1, . . . , m, while the other blocks are zero vectors.
Take the vector Θ N ∈ R 2N +3 in the connection matrix F (J+2) = Ξ T D 2 ,Θ N of the second fully-connected layer stated in (2.3) in terms of the linear operator L N as , then by the identity (5.4), for j = 1, . . . , m, the jth entry of the product The other entries of the product F (J+2) h (J+1) (x) vanish. Thus, by taking we see from the homogenous property σ(u/N) = σ(u)/N that the last layer h (J+2) is given by which is bounded by c ′′ r,d Λ d−1−r (n) with a positive constant c ′′ r,d depending only on r and d. It follows that ω(ζ n,r , 1 N ) ≤ c d c ′′ r,d n 2 Λ d−1−r (n)/N. Combining this with (5.9), Lemma 7 and the embedding Proposition 1 yields

General error bounds
With the proved bounds for f − L n (f ) ∞ in Lemma 1, L n (f ) − L y n,m (f ) ∞ in Lemma 2, and L y n,m (f ) −f ∞ in Lemma 3, the following bounds for the error f −f follows immediately.

Proving the main results
We are in a position to derive our main results from the general error bounds in Theorem 3.
The proof of Theorem 1 is complete.
Remark 3. When r = d − 1, from the above proof, we can see by taking N = ⌊n d+1 log(n + 1)⌋ that the statement of Theorem 1 still holds except that the bound for the number of free parameters should be replaced by N ≤ (3S + 3) J + 2J L t (g j ) ( y j , x ) .
Combining this with the additive ridge form (2.4) of f and Lemma 7, we know that for x ∈ S d−1 , Then the desired error bound is verified. The total number of free parameters N in the network is the sum of J(S + 1) contributed by w, J(2S + 1) by the bias vectors in the first J layers, 1 by the parameter B (J) in the fully-connected layer, and 2N +1 by the vector {g j (t i )} 2N +2 This proves Theorem 2.

Conclusion and Discussion
In this paper spherical harmonic analysis is conducted rigorously for the approximation theory of deep CNNs followed by downsampling and one fully connected layer or two on spheres. Our analysis provides rates of uniformly approximating functions f ∈ W r ∞ (S d−1 ) with r > 0 by deep CNNs followed by two fully connected layers. To approximate a Lipschitz function in a special additive ridge form, a network with one fully connected layer can be as fast as one for approximating a univariate Lipschitz function, which demonstrates the super power of deep CNNs in approximating or representing functions with special structures. Our spherical analysis relies on a special property of the reproducing kernel of H d n on the sphere. It would be interesting to extend our technique to approximation of non-smooth functions on [−1, 1] d and to L p approximation with 1 ≤ p < ∞.