Approximation with CNNs in Sobolev Space: with Applications to Classification
Authors: GUOHAO SHEN
Yuling Jiao
Yuanyuan Lin
Jian Huang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Approximation
error bound
smooth functions
classification
neural networks

Abstract: We derive a novel approximation error bound with explicit prefactor for Sobolev-regular functions using deep convolutional neural networks (CNNs). The bound is non-asymptotic in terms of the network depth and filter lengths, in a rather flexible way. For Sobolev-regular functions which can be embedded into the H\"older space, the prefactor of our error bound depends on the ambient dimension polynomially instead of exponentially as in most existing results, which is of independent interest. We also establish a new approximation result when the target function is supported on an approximate lower-dimensional manifold. We apply our results to establish non-asymptotic excess risk bounds for classification using CNNs with convex surrogate losses, including the cross-entropy loss, the hinge loss (SVM), the logistic loss, the exponential loss and the least squares loss. We show that the classification methods with CNNs can circumvent the curse of dimensionality if input data is supported on a neighborhood of a low-dimensional manifold.

Approximation with CNNs in Sobolev Space: with Applications to Classification
Guohao Shen"
Department of Applied Mathematics, The Hong Kong Polytechnic University Hung Hom, Kowloon, Hong Kong SAR, China guohao shen@polyu edu .k
Yuling Jiao
School of Mathematics and Statistics and Hubei Key Laboratory of Computational Science Wuhan University, Wuhan 430072, China yulingj aomath@whu. edu.
Yuanyuan Lint
Department of Statistics, The Chinese University of Hong Kong Shatin, New Territories, Hong Kong SAR, China ylin@sta. cuhk. edu. hk
Jian Huang
Department of Applied Mathematics, The Hong Kong Polytechnic University Hung Hom, Kowloon, Hong Kong SAR, China j huang@polyu. edu. hk
Abstract
We derive a novel approximation error bound with an explicit prefactor for Sobolev- regular functions using deep convolutional neural networks (CNNs). The bound is non-asymptotic in terms of the network depth and filter lengths, in rather flexible way. For Sobolev-regulat regullrr functions which be embedded into the Hölder space, the prefactor of our error bound depends on the ambient dimension polynomially in most existing results, which is of independent interest.
instead of exponentially We also establish a new approximation result when the target function is supported approximate lower-dimensional manifold. We apply our results establish non-asymptotic excess risk bounds for classification using CNNs with convex surrogate losses, including the cross-entropy loss, the hinge loss, the logistic loss, the exponential loss and the least squares loss. We show that the classification methods with CNNs can cireumvent the curse of dimensionality if input data supported on neighborhood of cow-dimensional manifold.
Introduction
Classification methods with hypothesis spaces specified through deep neural networks have achieved remarkable successes in variety of machine learning tasks (36]. In particular, convolutional neural
"Guohao Shen and Yuling Jiao contributed equally to this work *Corresponding authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

networks (CNNs) have demonstrated outstanding performance in many applications, including computer vision (35), natural language processing [57], and sequence analysis bioinformatics [[]
However, to the best of our knowledge, there have only been limited studies on the approximation properties with CNNs and non-asymptotic excess risk bounds for various classification methods using CNNs.
65
1.1 Related work
There has been much effort devoted understanding the approximation properties of deep neural networks in recent years. Many interesting results have been obtained concerning the approximation power of deep neural networks for multivariate functions; some examples of important recent works
13 28]. These works focused on the approximation power for ReLU activated feedforward neural networks (FNNs) on different kinds of smooth functions.
include [59] 60 40
49
53
54
The approximation power of CNNs has been studied in limited works. 2 studied the approximation power of the composited CNNs, where the network consists of fully-connected CNNs followed by fully-connected layer. They proved that under suitable conditions, convolution neural networks can inherit the universal approximation property of its last fully connected layers. [48] showed that for translation equivariant functions, all upper and lower approximation bounds are equivalent between FNNs and CNNs with the same order of network length and size. [47) showed that ResNet-type CNNs, a special CNN architecture with skip-layer connections (or identity connections between inconsecutive layers), can replicate the learning ability of FNNS having block-sparse structures. The ResNet-type CNN in 47. as claimed, can be dense, and its width, channel size, and filter size are constant with respect to sample size rather than the diverging one in 48
In addition, a series of papers studied the approximation power of deep CNNs with Toeplitz type convolutional matrices [66] 64 [3]. The universality of such CNNs was established in [64] for target functions restricted to the Sobolev space (Rd) with 3 2 d/2 + 2. The approximation error is of the order OLL-1/2-1/00 (up to a logarithmic factor), where L is the number of layers of such CNNs. But the CNN defined in (64] has width increasing linearly with respect depth. To overcome the difficulty in theoretical analysis of such CNNs, (63 introduced a downsampling operator to reduce the widths and the approximation power of downsampled CNNs for special class of functions (3-Hölder continuous ridge function) was studied. The approximate rate is shown to be O(N-8) by downsampled CNNs with uniform filter length s O 6) and width W O(N) for positive integer N. Further, it was shown that a downsampled CNN can compute the same function as FNN does, with the total number of free parameters of downsampled CNN being at most times of that of FNN. For the CNNs considered by [66, 16 63) and [64], each convolutional layer has only one filter with size and the weight matrix is of special Toeplitz type with shape (din + s) x din and no fully-com cully-connected layer is allowed in hidden layers. Approximation properties of convolutional architectures for target functions defined on infinite time domains tailored temporal sequence data were studied in 27
To mitigate the curse of dimensionality and show the advantages of CNNs in classification problems, several works studied the approximation as well as the statistical learning theories under some low-dimensional assumptions on the target function or the data distribution. In [32 33 the posterior probability function is assumed to be Hölder smooth satisfying hierarchical max- maxxppooiing model. In [34], the target function is assumed to be spatially rotation invariant. In [8] and [38], input data is assumed to be supported on spheres and manifolds. respectively. Under different structural assumptions on the target function, similar results have also been proved for FNNs 77] 5T [2] If data is assumed to be supported on oowdiieesioona manifolds, the curse of dimensionality can also
be mitigated for FNNs (50 44 12
1.2 Our contributions
We study the approximation power of CNNs for functions in Sobolev spaces, including the special case of Hölder class and apply our new approximation results to establish non-asymptotic error bounds for several important classification methods using CNNs. Our main contributions are as follows.
We derive a novel error bound for approximating Sobolev-regular functions using deep CNNs, with the error bound explicitly expressed in terms the network parameters and model parameters.

---

The error bound depends on the network depth and filter lengths in rather flexible way. For functions which can be embedded into Hölder space, the prefactor of our error bound depends on the ambient dimension polynomially instead of exponentially as in existing results. We also establish a novel approximation result when the target function supported on an approximate lower-dimensional manifold, which shows that CNNs are capable of mitigating the curse of dimensionality under such a distributional condition.
iii As an application of our CNN approximation results, we establish non-asymptotic bounds for the stochastic and approximation errors of classification methods with general class of convex surrogate losses Sobolev space using CNNs. Our main results are also applicable to other problems that use CNNs approximations.
(iii) We apply our general results to establish the non-asymptotic excess risk bounds for classification using CNNs with convex surrogate losses in Sobolev space, including the cross-entropy loss, the hinge loss (SVM), the logistic loss, the exponential loss, and the least squares loss. We show that classification methods with CNNs can circumvent the curse of dimensionality if the input data is supported on a neighborhood of low-dimensional manifold embedded in the ambient space.
Table I: comparison some recent convolutional neural network approximation results.
Network
Target function
Flexible filter length
Explicit prefactor
Low-dimensional Result
48
CNN
FNN
X
47
ConvResNet
FNN
X
64
CNN
Sobolev
X
3
CNN
Hölder
X
X
38
ConvResNer
Besov
X
This peper
CNN
Sobolev and Hölder
In Table 1 we summarize and compare some recent and most related work on CNN approximation results for various function spaces.
The statistical convergence properties the excess risk of the empirical risk minimizer (ERM) for the misclassification 0-1 loss have been studied extensively under various conditions. Different types of hypothesis spaces have been used in these approaches, including the linear space, the reproducing
kernel Hilbert space and the class of tree-based models, see, for example, p 55 42
6
29 g and
[62]. However, there are limited studies worked on deep binary classifications by FNNs 46
25 30
ResNet (26 45 and CNNs 32 33 38
Approximation power of CNNS
2.1 Convolutional neural networks
Convolutional networks are special type of structured sparse feedforward neural network (FNN) that use convolution in place of general matrix multiplication in at least one of their layers [21]. There are different formulations of CNNs in the literature 22 66 47 37 63 64 33
32 38) In this paper, we consider ReLU activated downsampled CNNs with bias vectors in the convolutional layers defined in [63]. We do not require the norm of network parameters (weight and bias) to be uniformly bounded.
We consider general CNN function fCNN + R, where X' Rd.. For simplicity, we take X' 1).. Suppose fCNN has L number of hidden layers, then it can be expressed as
fexx (x) Ar++1 o A. .... A2 o (1 X.
(1)
where o denotes the functional composition. The A;'s 's's are either convolutional operators or down- sampling operators. For convolutional layers, (x) = o (W bf), where W E 24 the structured sparse Toeplitz type weight matrix induced by the convolutional filter (w, (4) ( Jj=u with filter
length (1) E N+ and bf E Rd. is bias vector, and is the rectified linear unit (Rel.U) activation function applying each component of the input vector.
3

---

For downsampling layers, for any A()) D(()) (()m:))==1 ) where D, Rd, xd,-1 the downsampling operator with scaling parameter m, d in the i-th layer. We
introduce the convolutional operation and downsampling operation 663 in details in Appendix ??.
We focus the function class consisting of deep CNNs, denoted by FONN which is defined
FONN = =[ONN defined in over all possible choice A, = ,....,,+111.
(2)
For general function class F and any f E F, define the || 11x0 metric on F by supzex Il loe- Then let B su Il denote the bound of the functions in FCNN- Let L be the number of hidden layers and S be the total number of parameters for networks in FeNN and let Smin and 8max be the minimum and maximum filter length over convolutional layers respectively.
2.2 Approximation in Sobolev space
We use the Sobolev and Hölder classes for the target functions in our approximation results since they are well-established formulations for describing smooth functions in the literature. Indeed, earlier works on approximation theory of neural networks have been developed for Sobolev functions
(59 64
24 and for Hölder functions [33 55..
Let No be the set of non-negen non-negative integers and No- The Sobolev class of functions WD*(X)
with X' (0, 1)d defined as
(xP((x) { ( D E (2) for all a Ng with ||l||1 s $.
(3)
where 1 S P S co. Da = g..... .a. with = (ai,..., oa) E Ng. and
||al|i Ei= For I E wDr(X) and s m s B, define the norm Ilf (f) = (Eogllalism D fll 1/p for 1 I op, and define [Ifllm
maxog]lalli@m I (x))
In the remainder of the paper, for any positive integers M, N E N+ let FONN be the class of CNNs defined in (2) with depth L, size S and filter length specified as follows:
W-1 1,
L S 42([3] + 1)2M logz (8M))
(4)
5min
2 S smnn S Smax W,
(5)
S < 8WL,
(6)
where
W 38 ( + (118)+1)+000 1)* [8gg)
(7)
denotes the maximum incremental width (number of neurons) for consecutive layers in the network and [a] denotes the smallest integer no less than a.
Theorem 2.1. Assume that f E W (X) with 1 No. 1 00 and [f [P I Bo
Bn O. For any M, N E N+ there exists a function feNN E FeNN defined in with depth and filter lengths and size S specified in (4) ( and (6). such that for = 0,
||
wwp.llmmwpp ((X) Cold, (NM) =
2(8-
where Cold, 8.p) 37 223-2d/p B 1)33 {क 4/2 1 (1 +Vdddd' Here I'()) is the gamma function.
Our result is new for approximating Sobolev-regular functions in S.PP(2) for a positive integer 3 E N+ with respect to the Sobolev norms ||- [[wmar(x) for m 0, 1 in terms of explicitly defined approximation error prefactor, clearly defined and flexible network parameters, as well as an fast approximation rate comparable with (2). A toy example is provided in Appendix D to illustrate the approximation power of CNNs and examine how the approximation error varies according to the filter size and depth of the networks.
In 24 an approximation result on 3-smooth functions by networks with squared ReLU activation
function is also provided under the norm || [[w.r((x) for positive integer < B. In (22.. the

---

approximation rates of ReLU DNN for Sobolev-regular functions with respect to the weaker Sobolev norms [[ for E [0. 1] were analyzed, which can be seen as a generalization of the result in [59 Approximation results on Sobolev-regular functions (X)) by networks with general activation functions are derived in 23 where the enror is with respect
(x for some
integer m < 3.
By the general Sobolev inequality, see Theorem 6 in Chapter 5 of [5]. W (X)) with kp >> d can be embedded into a Hölder class 7 (X, Bo) (with 3 = k [d/pl 1) defined as
H (X (x,,B) Bo) = {1 X - R.
max [
| fo I Bp and max sup Sayy
D D f(x)
I Bn
r 211
(8)
where B > 0 and [8] E No denotes the largest integer strictly smaller than B. Because of the extra regularity on the Hölder class, much improved prefactor Co in the error bound of Theorem 2.1 can be obtained.
Theorem 2.2. Ler f E (X, Bo) be defined in & and let X E Rd be a random vector whose probability distribution is supported on X = (0, 1 and absolutely continuous with respect to the Lebesgue measure. For any M, N N++ there exists a function fcaN E FeNN defined in (2) with
depth L and filter lengths and size S specified in ( (5) and (6). such that
Blf(X) fcNN(X)] ()(M)) 23/d
where Co(d, 18B6(B + ()) Here v max a, b} for a, E IR
The convergence rate (NMM) -29/d in Theorems 2.1 and 2.2 with respect to the network depth and filter lengths specified by M and N, is in line with the nearly optimal rate of ReLU FNNs on smooth functions under Sobolev norm in (24] and on Hölder smooth functions under L norm in [28]. The prefactor 18B, (10(((+++((++)))))) d)) of approximation error depends on the dimension d polynomially, different from the exponential dependence in many existing neural network approximation results mentioned in Section 1.1
2.3 Approximation with a lower-dimensional support
In many modern machine learning problems, the ambient dimension d of the input data could be very large, which results in an extremely slow convergence rate. This fact is known as the curse of dimensionallty. Fortunately, many types of data have low-dimensional latent structure, that is. although the ambient dimension d is large, the distribution of the data is approximately supported on a low-dimensional subset of Rdd, in which case the approximation error bound can be substantially improved. We establish an approximation result for CNNs in Sobolev spaces under a low-dimensional support assumption.
Assumption 2.3. The distribution of X is supported Ma p-neighborhood of M C X, where M is a compact dd-ddimnsionnal Riemannian submanifold and M, = {I E X inf - y vll2 y E M) < p} for p E (0, 1).
In real-world applications, data are hardly observed to locate on an exact manifold, instead they could be more realistically viewed as consisting latent part supported on a low-dimensional manifold
M plus noises. Therefore, Assumption 2.3 is more realistic than the exact manifold assumption
50 12 38
Define
d: = Od log(d/e)), E (0, 1), Pe = CNM) 28/4, (3 12 x [(d/de) +1 (1 -1- 1)
(9)
(10)
In our error bound results below, it is the de that will affect the convergence rate. Since is often the case that dm & d and therefore d. & d. the manifold assumption will lead to better convergence rate than those in Theorems 2 and 2.2 In addition, we require p S Pe-
Theorem 2.4. Suppose that Assumption 2.3 holds, I E H , Ba) and the distribation of X is absolutely continuous with respect to the Lebesgue measure. Let de and pe be defined in
5

---

and (10), respectively. Assume that S Pe. Then, for any M, N E N there exists a CNN function fCNN FewN with depth L and filter lengths and size S specified in and (6) with W = 38 (13] + 1) 2201+2 N2 [8g) such that
B fcNN(X)1 (NN, 23/d.
where C(d, (18 C2) - (3 + / 2012
Since the intrinsic dimension de can be much smaller than the ambient dimension d, the rate (M -28dd in Theorem 2.4 greatly improved compared with the rate (NM))-25 -2//d in Theorem 2.2 and the curse of dimensionality is mitigated. The result here is of independent interest and can be useful in other problems that involve the use of CNNs.
3 Excess risk in classification
In this section, we present the application of the approximation results Theorems 2.1 and 2.4 to the error analysis of classification with CNNs.
Consider a binary classification problem with predictor X E X C Rd and its binary label Y E {1, -13. We are interested in learning classifier h X' + {1, [1,-1} from class of functions, or hypothesis space, denoted by H. Let the joint distribution of (X, Y be I.. The goal is to find classifier that minimizes the misclassification error or the 0-1 risk: R. (h) = P(h(()())
Y), h E H. Denote the misclassification risk minimizer at the population level by hg = argmin, messurable R. (h). For any h H. the excess risk of h is (2)h) (ho), the difference between the misclassification errors of h and hg-
Since the probability measure IP is unknown in practice, the classifier h will be learned based on random sample 5 {(X,, 2 from P, where n the sample size. The empirical risk minimizer (ERM) is defined by
hn argmin NEW
I(M(x.)+)))
(11)
VL
However, the empirical risk function based on the 0-1 loss is non-continuous and non-convex, thus this minimization problem is typically computationally intractable.
Rather than minimizing the non-smooth 0-1 loss, many popular methods adopt a proper loss function to train classifiers with computational efficiency that can be done in polynomial time. Moreover, proper surrogate convex loss functions have been shown to be consistent with the 0-1 loss function for binary classification problems [61 5)
3.1 Convex surrogate loss functions
Let be given convex univariate loss function á R (0). We consider the risk function with respect to the loss Ø
R(f) R$ = ((X))
(12)
where for simplicity of notation and without causing confusion we omit the superscript & in R, similarly for for and fo defined below. For a given random sample S = ((X,, Y:) we denote the ERM over JONN with given loss o by
fn E arg min JEFeN
Σ (Y 1=1
(13)
Based on the ERM f.. a classifier hn(x)) = sign(fn(x)) for x E can be defined. As shown in 61 5], for a properly chosen d. f. can help reduce the excess risk R2 (h... R. (hu). Specifically, define the measurable minimizer of R in 122 as
fo argmin E ((X)))
(14)
f memsurable

---

and the corresponding minimal ø-risk as Ro R(fo). Then for proper ø. we have (R,,),
R, (ho)) I R(fa) R(fu), where [-1,1] + [0, oo) is nonnegative continuous function, invertible on [0, 1), and achieves its minimum at O with x) = 0. A variety of classification methods based this tactic. Generally, classification cetiicatiooncllibbateedd & considered in this paper is non-increasing and convex; details are given the Supplementary Materials.
Define the conditional probability
7(z) P(Y = = x), E.Y
(15)
Let the conditional ø-risk of f given X = x be denoted by Ry(x) == B(o(Yf(X)) | = z). SVM and cross entropy, two important examples of Φ. and the corresponding fo. R(Jo), & and its inverse on 10, 1] in Table 2 in the appendix. For the form of 1b Theorem 34 in [1] shows that if & is convex, (0) > exists and ø' < 0, then (b)))= u²
Table 2: Minimizer and minimal conditional risk under SVM and cross entropy loss functions Φ Bound ΦB of Φ. Lipschitz constant Bg and (T( for the truncated fo under SVM hinge loss function restricted [-B, for < T I B and cross entropy loss function restricted to B, for T < B < 0.5.
SVM
Cross entropy
o(a)
max a. 0}
log + +a
fo(x)
sign 2n 1)
1) 0.5
Rio (x)
22 1
1) log(1) - (1 - 17) log - 1))
(0)
/2
on
B #*
log 18)
Bg
10.5.5 B)) log + (T 0.5))
AT(T)
Note: The conditional probability (/z)) defined in 15 is written as ry for notational simplicity. "*e" stands for "does not exist"
4 Non-asymptotie error bounds
For the ERM fn defined in 13 first state basic incquality for bounding the excess risk of fn- Lemma 4.1. For any loss à and any random sample = {(X,, Y:))==> the excess d-risk of the ERM fn satisfies R(fa) R(fo) S StoErr + AppErr, where
StoErr = 2 sup R(f) - Rn)()), AppErr = inf R(f) - R(fo).
(16)
feF
feF
Therefore, the excess risk of f. is bounded by the sum of two terms: the stochastic error and the approximation error, For given loss function Φ the upper bound no longer depends on the ERM fn. but the function class F and the random sample S. The stochastic error (16) depends on complexity of F and the approximation error in (16) depends on the approximation power of the class F for fo-
4.1 Stochastic error
We bound the stochastic error in terms of the pseudo-dimension of the downsampled CNNs defined in particularly, further bound its pseudo-dimension and express the bound terms of quantities
2
re related to CNNs.
Theorem 4.2. /Srochastic error bound] Suppose that convex and non-increasing, For any N E N let FCNN be the class of CNNs defined in (2) with B > 0, depth L and size S and let
ΦB == su ((a). Then, for any 8 10. with probability at least 1 8, the stochastic error
in 16 satisfies
20B Vn
StoErr < (Co/SLlog(S)) + vlog(1/6)).
where Co > 0 is universal constant.

---

The quantity Øg for common loss functions are presented in Table It worth noting that the error bound here does not require the norm of the CNN parameters (of weight and bias) be uniformly bounded. In comparison, those stochastic error bounds based on the covering number generally assume an uniformly bounded norm on CNN parameters, which may hinder the approximation power of network since most approximation results need the norm of network parameters to tend to infinity as the approximation error tends to zero.
4.2 Approximation error
We derive an upper bound of the approximation eтrоr by relating inf fe R(f) R(fo) to inf feFew Il full under proper conditions on and n,, where R defined in 12 The tar- get function fo may be non-smooth or unbounded, which poses extra difficulty. Most of the existing studies on the approximation properties of networks assume smooth and bounded target functions. As shown in 2 the target function fo for SVM is non-continuous; for the cross entropy loss, the loss unbounded on (-0.5, 0.5]. For logistic loss and exponential loss, we have fo(z) E {+000- -x) once r)(x) {0, }.. We overcome these difficulties by imposing mild conditions on the conditional probability 77 and the loss function 6, and use the truncation technique to analyze the approximation.
Assumption 4.3. (a) The conditional probability 77()) = P(Y = | X = x) is continuous on the support of X' and the probability measure of X is absolutely continuous with respect the Lebesgue measure. (b) The loss function ő R + [0, oo) glassification-calibaad convex, non- non-increasing and continuously differentiable on its support.
Assumption 4.3 (a) and (b) are regular conditions ensuring that the target function fo is continu- ous and the loss ø is Lipschitz on bounded intervals. The absolute continuity assumption of the probability measure of X with respect to the Lebesgue measure is reasonable for the approximate low-dimensional manifold case but incompatible with the exact low-dimensional manifold condition. This assumption is for deriving better Lp approximation error bound, without which the error bound in term of the Lo norm can still be established, but at the price of a wider neural network and a larger prefactor.
be verified that commonly used loss functions, such as the cross entropy, the logistic and the exponential loss functions, satisfy Assumption 4.3 (b).
To deal with the approximation of unbounded target function, truncate the target So by constant T, where T may depend on n. Let forr be the truncated version of fo defined as
(o. = {
fo(x); Tsign(fo(z)))
fo(x)) $ T. if fo(x) > T.
Denote the error of the loss function @ due to truncation by
(T) inf (aa) inf ((a). aeRan(fo)
(17)
Ja|ST
where Ran(fo) is the range of the target function fo. This error decreases as T increases. Then, the approximation error can be decomposed into two terms that are easier to deal with.
Lemma 4.4. Id-approximation error] Suppose that Assumption 4.3 holds and T S B. Then, the d-approximation error inf JEFom R(f)) R(fo) with respect to the loss function à satisfies
inf R(f) - R(fo) <Bo inf BIf(X) - (x) + (T))).
fEFeux
JeJcm
where By is defined the Lipschitz constant of o on the interval B).
We list B3 and (T( for hinge and cross entropy loss functions in Table 2 A detailed table including other loss functions are given in the appendix.
Theorem 4.5. /Approximation error bound] Suppose that Assumption 4.3 holds and fo E H 11s Bo). For any M,N E N+ let FCNN be the class of CNNs defined in (2) with T < B. depth L and filter lengths specified in 4 and (5). Then, the approximation error defined in (16)
satisfies AppErr S (NNM) 28/d (T))), where C(d, 3) 18B (Bv1
There is trade-off since T < B and A (TT)) deceases in T' but C(d, (3) increases in B& (or B).

---

4.3 Non-asymptotic excess risk bound
Combining Theorems and 4.5
we obtain the excess error bound.
Theorem 4.6. [Non-asymptorie excess ø-risk bound] Suppose that Assumption 4.3 holds and fo E
H 11 Bo)- For any M, N E N+ let FeNN be the class of CNNs defined in 2 with T B.
depth L and filter lengths specified in (4) and (5) Then, for any 8 E (0, 1), with probability at least
1 6, the ERM fn defined in 13 satisfies
R(fa) R(fo) SStoErr + AppErr,
(18)
with
20B Vn
StoErr
Cov SL log( (5) (S) log(n) /log(1/0)) AppErr Cld,3) + (T),,,
where ()d, 1oBB + + 1)3 and Co > 0 is universal constant.
The upper bound of the excess ø-risk R(f.) R(fo) in Theorem 4.6 is sum of two error terms, the stochastic error and the approximation error. To achieve the optimal error rate, we need to balance the trade-off between them. On one hand, the bound for the stochastic error StoError increases with the size and the depth of FeNN. On the other hand, the bound for the approximation error AppError decreases with the depth and the upper bound of filter lengths of FeNN.
4.4 Circumventing the curse of dimensionality
We state a theorem that provides a non-asymptotic excess risk bound under the approximate low- dimensional manifold assumption.
Theorem 4.7 (Cireumventing the curse of dimensionality). Suppose that Assumptions 2.3 4.3
hold, and fo E H 1]sh Bo). For any M,N N+, let FONN be the class of CNNs defined in 12) with
B, depth and filter lengths and size S specified in 4 (5) and ( with W
38
1) 222 [loga (8N))2 Suppose p in Assumption 2.3 satisfies p Pen where Pa is
defined in 10p. Then for any E (0, 1). with probability least 8, the ERM fn defined in
13
satisfies
R(fx) - R(fo) SStoErr. + AppErr..
(19)
with
2dB V
StoErr,
(C1 SL log( + (oogggnn)+//ol///// /log(1/))).
AppErr, = (18 -(11=
C2)
(1 =) (B + 1)2d2/203812) x (NM)-228) 28/d. + AT)))
Bo
where C1, C2 > 0 are universal constants.
For nigh-dimensional input X with large d, de satisfies dMs de d for (0, For the stochastic error StoErr., comparing with the bound (18) in Theorem [.6] we see that StoErr. = StoErr, that is, the stochastic error does not change under the approximate low-dimensional manifold assumption. For the approximation error AppErr. see that the convergence rate (NM) 28/dd, only depends on de, which Icads to a much faster convergence rate.
-
Examples
In this section, we illustrate the applications of Theorems 4.6 and 4.7 to obtaining non-asymptotic error bounds for the excess risk in classification. We apply the general excess risk bounds established in these theorems several important classification methods with CNNs when specific form of is given. We present the results for the cross entropy loss below. The non-asymptotic error bounds for the hinge, the logistic, the exponential and the least squares losses are given in Appendix ??.
For the cross entropy loss p(a) log a), the Lipschitz constant B& on [-0.5, 0.5) is not bounded. As the minimizer of ş-rissk - 0.5 is bounded, we can choose B 0.5 n (22++18)) Then (T)) < n- -8(26-11)) and B& (224+11))

---

Denote En = n 22(244)))) Take N = 1 in and M = [E] in (4) and let FCNN be the class
of CNNs in with depth L S 378 ( + 1) + [ [loga ( (8( (Smin 1). filter
lengths 2 v Smin I Smax I 9 x 38 (18] + 1)d and size S I 8WL I 42 * 8 * 92
(L8] + 1400++(++++ [Ex]] (1og ()/(s)mmm
1). Theorem 4.6 imipllss that, with probability
at least 1 exp(-Ei) the excess ø-risk of the ERM fn defined in 13 satisfies
R(fx) - R(fo)) SOn -8((248(()))111 (log n)
where C' = (B + ()) (5min 1)) is constant independent of n.
Let T -B 0.5 (log m) -1 Using modified cross entropy loss <(aa max log(0.5 7) with - -log(1 (logn) the excess é-risk of the ERM fn can be improved to O(n-B/(++2) B/(d+28) (log).)
the approximate low-dimensional manifold Assumption holds and for any E (0, 1), the radius of the neighborhood p in Assumption 2.3 satisfies p S Pc: where Pe is defined in (10), then Theorem 4.7 implies that the rate of convergence can be improved:
R(fx)) RR(f)) S On +2/24(4))) (logn)²
where C' is a constant independent of n.
The above discussion shows that deep binary classifications with CNNs are adaptive to the low dimensional structure of the data and the smoothness of the target. Moreover, the prefactor C depends the ambient dimension polynomially, which improves the prefactors depending on d
exponentially in the existing excess risk bounds [46] 25 30 26 45
32
33 38 Moreover, the filter
lengths here are more flexible comparing with those requiring certain filter lengths in [3 33 48
6 Conclusion
In this work, we derive new approximation error bounds with explicit prefactor in terms of network parameters for Sobolev-regular functions and Hölder smooth functions using deep convolutional networks. New approximation result when the target function is supported on an approximate lower-dimensional manifold established. Different from existing results, the prefactor of our error bound depends on the ambient dimension polynomially instead of exponentially for Hölder smooth functions. The new approximation results are applied to establish non-asymptotic excess risk bounds for class of classification methods using CNNs.
An important limitation of our work that we only considered binary classification problems in applying our approximation results using deep convolutional networks. It would be interesting to apply the results this work to other settings involving CNN approximation, such as the multiclass classification and regression problems. In addition, our work only partially explains the empirical successes of CNNs practice. For image data, the assumption of approximate lower-dimensional support does not capture all the structural information. For example, spatial invariance is likely to be expected in some problems such as image classification. We believe that if such properties are taken into account, the theoretical bounds can be further improved. We hope to study this in the future.
Acknowledgements
The authors wish to thank three anonymous reviewers for their comments and suggestions that helped improve the paper significantly.
G. Shen is partially supported by the research grant P0041243 from The Hong Kong Polytechnic University. Y. Jiao is supported in part by the National Science Foundation of China under Grant 11871474, the research fund of KLATASDSMOE, and the Fundamental Research Funds for the Central Universities NO. 2042022k10071. Y. Lin is supported by the Hong Kong Research Grants Council (Grant Nos. 14306219 and 14306620), the National Natural Science Foundation China (Grant No. 11961028) and Direct Grants for Research, The Chinese University of Hong Kong. J. Huang is partially supported by the research grant PO042888 from The Hong Kong Polytechnic University.
10

---

References
[1] Babak Alipanahi, Andrew Delong, Matthew T Weirauch, and Brendan J Frey. Predicting the sequence specificities of dna-and ma-binding proteins by deep learning. Nature biotechnology. 33(8):831-838, 2015.
[2] Chenglong Bao, Qianxiao Li, Zuowei Shen, Cheng Tai, Lei Wu, and Xueshuang Xiang. Approximation analysis of convolutional neural networks. 2014.
[3] Richard G. Baraniuk and Michael B. Wakin. Random projections of smooth manifolds. Found, Comput. Math., 91):51-77, 2009.
[4] Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. J. Mach. Learn. Res., 20:Paper No. 63, 17, 2019.
[5] Peter L. Bartlett, Michael Jordan, and Jon McAuliffe. Convexity, classification, and risk bounds. J. Amer. Statist. Assoc., 101(473):138 156, 2006.
[6] Peter Bartlet and Shahar Mendelson. Empirical minimization. Probability theory and related fields. 135(3)311-334, 2006.
[7] Benedikt Bauer Michael Kohler. On deep learning as remedy for the curse of dimensionality in nonparametric regression. Ann. Statist., 47(4))2261122 2002261-222,200000 2019.
[8] Shai Ben-David and Ruth Urner. The sample complexity of agnostic learning under deterministic labels. In Conference on Learning Theory, pages 527-542. PMLR, 2014.
[9] Anselm Blumer, Andrzej Fhrenfeucht, David Haussler, and Manfred K Warmuth, Leamability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929-965, 1989.
[10] Susanne C Brenner and Ridgway Scott. The Mathematical Theory of Finite Element Methods. Springer, 2008.
[11] Di-Rong Chen, Qiang Wu, Yiming Ying, and Ding-Xuan Zhou. Support vector machine soft margin classifiers: error analysis. The Journal of Machine Learning Research, 5:1 1:11431117,, 2004.
[12] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Nonparametric regression on low- dimensional manifolds using deep relu networks. arXiv preprint arXiv: 2019.
[13] Minshuo Chen, Haoming Jiang, and Tuo Zhao. Efficient approximation of deep relu networks for functions on low dimensional manifolds. Advances in Neural Information Processing Systems, 2019.
[14] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning. 20(3):273-297, 1995.
[15] Lawrence C Evans. Partial Differential Equations. Rhode Island, USA, 1998.
[16] Zhiying Fang. Han Feng, Shuo Huang, and Ding-Xuar Xuan Zhou. Theory of deep convolutional neural networks Spherical analysis. Neural Networks, 131:154-162, 2020.
[17] Charles Fefferman. Whitney's extension problem for c" Annals of Mathematics., 164(1):313 319339999999 2006.
[18] Han Feng, Shuo Huang, and Ding-Xuan Zhou Generalization analysis of cans for classification spheres. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[19] Yoav Freund, Rohert E. Schapire, et al. Experiments with a new boosting algorithm. In icml, volume 96, pages 148-156. Citeseer, 1996.
[20] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Additive logistic regression: a statistical view of boosting. Ann. Statist., 28(2)337-407, 2000.
[21] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, Cambridge, MA, 2016.
[22] Ingo Gühring, Gitta Kutyniok, and Philipp Petersen. Error bounds for approximations with deep relu neural networks in w P norms. Analysis and Applications, 18005)8803-85, 2020.
[23] Ingo Gühring and Mones Raslan. Approximation rates for neural networks with encodable weights in smoothness spaces. Neural Nenworks, 134:107-134 2021.
[24] Sean Hon and Haizhao Yang. Simultaneous neural network approximations in sobolev spaces. arXiv preprint 20X002200..0161,, 2021.

---

[25] Tianyang Hu, Zuofeng Shang. and Guang Cheng, Sharp rate of convergence for deep neural network classifiers under the teacher-student setting, arXiv preprini arXiv:2001.06892, 2020.
[26] Furong Huang, Jordan Ash, John Langford, and Robert Schapire. Learning deep resnet blocks sequentially using boosting theory. In International Conference on Machine Learning, pages 2058 2067. PMLR, 2018.
[27] Haotian Jiang, Zhong Li, and Qianxiao Li. Approximation theory of convolutional architectures for time series modelling. In International Conference on Machine Learning, pages 4961-49700 PMLR, 2021.
[28] Yuling Jiao, Guohao Shen, Yuanyuan Lin, and Jian Huang. Deep nonparametrie regression on approxi- mately low- dimensional manifolds. arXiv preprint arXiv 2104.06708, 2021.
[29] Matti Kääriäinen. Active learning in the non-realizable case. In International Conference on Algorithmic Learning Theory, pages 63-77. Springer, 2006.
[30] Yongdai Kim, Ilsang Ohn, and Dongha Kim. Fast convergence rates of deep neural networks for classifica- tion. Neural Networks, 138: 1 199-197, 2021.
[31] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint
arXiv: 14t..1412666 2,800, 2014.
[32] Michael Kohler, Krzyzak, and Benjamin Walter. On the rate of convergence of image classifiers based on convolutional neural networks. arXiv preprint arXiv:2003.0152 2020.
[33] Michael Kohler and Sophie Langer. Statistical theory for image classification using deep convolutional neural networks with cross-entropy loss. arXiv preprint urXiv:2011.1300, 2020.
[34] Michael Kohler and Benjamin Walter. Analysis of convolutional neural network image classifiers in rotationally symmetric model. arXiv preprint wrXiv:2205.055000 2022.
[35] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
[36] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521 444, 2015.
[37] Shan Lin and Jingwei Zhang, Generalization bounds for convolutional neural networks. arXiv preprint arXiv:1910.01487.22 2019.
[38] Hao Liu, Minshuo Chen, Tuo Zhao, and Wenjing Liao. Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks. In International Conference on Machine Learning, pages
PMLR, 2021.
[39] Jianfeng La, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions. SIAM Journal on Mathematical Analysis, (3(5):5465-5506 2021.
[40] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. arXiv preprint arXiv:1709.02544 2017.
[41] Enno Mammen and Alexandre B Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 1888888888 1999.
[42] Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34(5):2326 2366, 2006.
[43] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, Cambridge, MA, 2018
[44] Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and estimation of deep neural network with intrinsic dimensionality. arXiv preprint arXiv: 2019.
[45] Atsushi Nitanda and Taiji Suzuki, Functional gradient boosting based on residual network perception. In International Conference on Machine Learning, pages 3819-3822 PMLR, 2018.
[46] Ilsang Ohn and Yongdai Kim. Smooth function approximation by deep neural networks with general activation functions. Entropy, 21(7))627, 2019.
[47] Kenta Oono and Taiji Suzuki. Approximation and non parametric estimation of resnet-type convolutional neural networks. In International Conference on Machine Learning, pages 4922 1931. PMLR, 2019.
12

---

[48] Philipp Petersen and Felix Voigtlaender. Equivalence of approximation by convolutional neural networks and fully-connected networks. Proceedings the Americun Mathematical Society, 148(4):1567-1581 2020.
[49] Maithra Raghu, Ben Poole, Jon Kleinberg. Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power deep neural networks, In International Conference on Machine Learning, pages 2847-2854. PMLR, 2017.
[50] Johannes Schmidt- Hieber.. Deep ReLU network approximation of functions on manifold. arXiv preprint arXiv: 00695, 2019.
[51] Johannes Schmidt-Hiebee Nonparametric regression using deep neural networks with ReLU activation function (with discussion). Ann. Statist., 48(4):1875-1897, 2020.
[52] Guohao Shen, Yuling Jiao, Yuanyuan Lin, Joel L Horowitz, and Jian Huang. Deep quantile regression: mitigating the curse of dimensionality through composition. arXiv preprint arXiv:2107 2021.
[53] Zuowei Shen, Haizhao Yang, and Shijun Zhang. Nonlinear approximation via compositions. Neural Networks, 19::74-84, 2019.
[54] Zuowei Shen, Haizhao Yang. and Shijun Zhang. Deep network approximation characterized by number of neurons. Commun. Comput. Phys., 28(5):1768-1811 2020.
[55] Alexandre B. Tsybakov. Optimal aggregation of classifiers in statistical learning. Ann. Statist., 32(1):135- 166, 2004.
[56] Qiang Wu, Yiming Ying. and Ding-Xuan Zhou. Multi-kernel regularized classifiers. Journal of Complexity, 23(1):108-134, 2007.
[57] Yonghui Wa, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's 's neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint 4rXiv:160900814, 2016.
[58] Yuhong Yang. Minimax nonparametric classification. i. rates of convergence. IEEE Transactions on Information Theory, 45(7):2271-2884, 1999.
[59] Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Newral Networks, 94:103-114, 2017.
[60] Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference on Learning Theory, pages 639-649. PMLR, 2018.
[61] Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimiza- tion. Ann. Statist., 3261) 2004.
[62] Nikita Zhivotovskiy and Steve Hanneke. Localization of ve classes: Beyond local rademacher complexxies.. Theoretical Computer Science, 742:27-49, 2018.
[63] Ding-Xur Xuan Zhou Theory of deep convolutional neural networks: Downsampling. Neural Nenworks, 124:319-327, 2020.
[64] Ding- Xuan Zhou. Universality of deep convolutional neural networks. Appl. Comput. Harmon. Anal., 48(2):787-794, 2020.
[65] Jian Zhou and Olga G Troyanskaya. Predicting effects of noncoding variants with deep learning-based sequence model. Nature methods, 12(10)9331934, 2015.
[66] Pan Zhou and Jiashi Feng, Understanding generalization and optimization performance of deep cnns. In International Conference on Machine Learning, pages 5960-59600 PMLR, 2018.
13


Reviews:
[{"review_id": "Mhm3Yau5do0", "reviewer": "Reviewer_QP4m", "summary": "In this paper the authors have constructed new error bounds for approximating functions in Sobolev and Holder space using deep CNNs. While such bounds have been constructed before, the authors show that there is more flexibility in decreasing these bounds by controlling network depth and filter size in comparison to previous studies. Furthermore, the new error bounds have been shown to depend on the functions’ ambient space dimension polynomially instead of exponentially. In this way the new bounds are much tighter. They also show that if the target function is approximately supported over a lower dimensional manifold, then the tightness of the error bound is further increased phenomenally, thus mitigating the curse of dimensionality and providing faster convergence.\nNext, they apply the new approximation error bounds to error analysis of binary classification tasks using deep CNNs. If Y is the target binary label, and f(X) is the function modeled by a deep CNN to estimate Y, the task is to find an appropriate function from the functional space where f(X)  minimizes the expected value of some convex loss function of Y and f(X). As relevant probability distributions over f(X) and Y are unknown  beforehand, an empirical version of the misclassification risk is minimized. The authors show that the difference between the expected misclassification risk and the empirical one is lower bounded by a sum of a stochastic error and an approximation error. They further calculate upper bounds on these two error terms as well.\nThe stochastic error depends on the complexity of the space of f(X). Sobolev space ensures some degree of smoothness in this case. The approximation error depends on the approximating power of f(X). Furthermore, they show that the bounds on stochastic error don’t require the parameters of the CNN to be uniformly bounded. Earlier studies have enforced such constraints. Thus, the authors’ bounds aid in providing more flexibility over the range of parameter values. Then, the authors show that the bound on approximation error can be further controlled by the controlling overall bound of f(X) itself. The bound for the stochastic error increases with the size and the depth of CNN while that of approximation error decreases.\nFinally in their detailed appendix, the authors construct these bounds explicitly for common loss functions for binary classification namely, least squares, hinge, logistic and exponential loss. \n", "questions": "1. Why did not the authors include more real functional approximation/regress including denoising and such where smoothness issues are front and center  rather than binary function cases?\n", "limitations": "As noted in the last rubric, the authors’ derivations depend on binary misclassification risk. However, CNNs may have numerous objectives including multivariate classification and regression tasks. The authors admit these limitations. While deriving bounds for multivariate classifications could be straightforward, it would be far more important  to see  similar tighter bounds  for regression tasks in general.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The work is original and provides a  good set of  references \nThe authors have provided detailed substantiation of the results  presented in the paper. They have also provided detailed calculations of the relevant bounds for common loss functions used in binary classification tasks.\n\nQuality: The paper appears sound and is clear in stating the objectives and results.\nThe work is of potential  significance.\nThe bounds presented apply to a large class of deep CNN’s used for binary classification. \nHowever, the work is presented only for binary classification tasks, and the authors appear to have overlooked some recent work on exactly the same topic  H. Jiang, Z. Li  and Q. Li and P. Combettes and J.C. Pesquet.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "8X9CrlPCwD", "reviewer": "Reviewer_aFh9", "summary": "The authors consider deep convolutional neural networks (CNNs) for classification. Their main results include rates of approximating Sobolev smooth functions by CNNs in L_p spaces (Theorems 2.1-2.4 and 4.5), sample error bounds (Theorem 4.2), and estimates for the excess misclassification error of the induced classification algorithm (Theorems 4.6 and 4.7). ", "questions": "Some questions have been asked in the previous section. ", "limitations": "Yes, they admit in Assumption 4.3 that they require the loss \\phi to be C^1, hence the hinge loss is not included. ", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "CNNs are the most important family of structured deep neural networks used in practice which are particularly efficient for image classification. Because of the convolutional structure, their analysis is different from that for fully-connected networks. Recently there are some results on CNNs for classification such as those of Kohler et.al. and Feng-Huang-Zhou (Generalization Analysis of CNNs\nfor Classification on Spheres, IEEE TNNLS, in press). \n\nWhat is nice in this paper under review is the treatment of the approximation error when the target function f_0 is unbounded or not Lipschitz. The authors use a truncation operator to estimate the approximation error. \n\nAnother interesting idea of the paper is to consider an almost manifold structure of the input space and to derive learning rates in Theorem 4.7 which depend on the ambient dimension weakly. The authors should comment on the absolute continuity of the marginal distribution with respect to the Lebesgue measure. \n\nIn the proof of Theorem 4.5, the set \\{x: |f_{0, T}(x)| \\leq T\\} is obviously the whole input space, which should be a typo. The author might mean the set \\{x: |f_{0}(x)| \\leq T\\}. Please comment on the Hoelder smoothness of f_0 on this subset. \n\nThe parameter {\\mathcal W} defined in Equation (4) should be given a network meaning. Does it stand for the maximum network width?\n\nFor the comparison theorem in terms of \\psi mentioned on page 6, a simple form valid for almost all loss functions is one with \\psi(u)=u^2 given by Chen-Wu-Ying-Zhou (Support vector machine soft margin classifiers: Error analysis, JMLR 5 (2004), 1143–1175). \n\nThe authors have compared their results on approximation error with the existing ones. They should do the same for the excess misclassification error. \n\nOverall, this is an excellent paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4ZaG-l_HZzC", "reviewer": "Reviewer_ZFjR", "summary": "This paper shows new error bounds for approximating functions in Sobolev spaces with deep convolutional neural networks. The estimates depend on the dimension of the space in a polynomial way only, and explicitly show the relation to the depth and filter length of the network. By assuming that the domain of the function is well-approximated by a low-dimensional manifold, the authors can improve the error bounds significantly and thus address the curse of dimensionality. This result is exploited for deriving an error bound on the excess risk in classification tasks by separately bounding the stochastic and the approximation error, and subsequently exemplified by making the bound more concrete for the cross-entropy loss. ", "questions": "- Please address whether a toy example for comparing theoretical and practical bounds would be feasible. \n- Please briefly motivate the consideration of Sobolev functions (and/or their remaining gap to common CNN applications). ", "limitations": "The authors have suitably addressed limitations of their work. I do not think a potential negative societal impact applies for this work. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Without being an expert on the topic, this appears to be a nice contribution to me. Despite the technical nature of the paper, it is well-written and the authors make their results more accessible to non-experts by clearly defining all mathematical objects (even more standard one like Sobolev spaces). Furthermore, I like the structure of explaining the general bounds first and utilizing/exemplifying them in increasingly concrete applications (excess risk in classification; then cross-entropy in particular + more losses in the appendix). Finally, not assuming a strict manifold structure of the domain, but rather an approximate one is a strength as this assumption is surely more realistic. \n\nDue to my limited background in the area I cannot judge how novel/significant the contribution is in comparison to prior work. From a practical perspective, I would have liked to see a toy example for some (artificial) problem on which the theoretical function approximation bounds could have been compared to numerical ones in order to get an impression of how tight or loose such estimates are. A second thing I am mostly just wondering about is if the 'approximate low dimensional manifold' assumption and the generic space of Sobolev functions is enough to capture why CNNs work well? The theoretical results in the paper partly say 'yes' (in the sense of the polynomial behavior), but practitioners often argue for CNNs if some (approximate) type of spatial invariance makes sense for the particular application. This could suggest that a much more restricted setting allow to still improve the bounds significantly (which is also the reason why I'd still expect a large gap between the derived theory and many practical applications of CNNs). \n\nTypos: \"choiceof\" (without space) in equation (2); \"be th number\" two lines below (2). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept