# Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional
Neural Networks

Guohao Shen<EMAIL_ADDRESS>
Department of Statistics
The Chinese University of Hong Kong
Hong Kong, China Yuling Jiao∗<EMAIL_ADDRESS>
School of Mathematics and Statistics
Wuhan University
Wuhan, Hubei, China 430072 Yuanyuan Lin<EMAIL_ADDRESS>
Department of Statistics
The Chinese University of Hong Kong
Hong Kong, China Jian Huang<EMAIL_ADDRESS>
Department of Statistics and Actuarial Science
University of Iowa
Iowa City, Iowa 52242, USA Guohao Shen and Yuling Jiao contributed equally to
this work

###### Abstract

In this paper, we consider the problem of binary classification with a class
of general deep convolutional neural networks, which includes fully-connected
neural networks and fully convolutional neural networks as special cases. We
establish non-asymptotic excess risk bounds for a class of convex surrogate
losses and target functions with different modulus of continuity. An important
feature of our results is that we clearly define the prefactors of the risk
bounds in terms of the input data dimension and other model parameters and
show that they depend polynomially on the dimensionality in some important
models. We also show that the classification methods with CNNs can circumvent
the curse of dimensionality if the input data is supported on an approximate
low-dimensional manifold. To establish these results, we derive an upper bound
for the covering number for the class of general convolutional neural networks
with a bias term in each convolutional layer, and derive new results on the
approximation power of CNNs for any uniformly-continuous target functions.
These results provide further insights into the complexity and the
approximation power of general convolutional neural networks, which are of
independent interest and may have other applications. Finally, we apply our
general results to analyze the non-asymptotic excess risk bounds for four
widely used methods with different loss functions using CNNs, including the
least squares, the logistic, the exponential and the SVM hinge losses.111This
version submitted to arXiv on May 01, 2021

Keywords: Approximate Low-dimensional Manifold, Covering Number, Curse of
Dimensionality, Deep Neural Networks, Function Approximation

##  1 Introduction

Consider a binary classification problem with a predictor
$X\in\mathcal{X}\subset\mathbb{R}^{d}$ and its binary label $Y\in\\{1,-1\\}$.
We are interested in learning a deterministic function
$h:\mathcal{X}\to\\{1,-1\\}$ from a certain class of measurable functions
$\mathcal{H}$. The class $\mathcal{H}$ is usually referred to as a hypothesis
set and any function $h\in\mathcal{H}$ a classifier. A classifier $h$ can be
used for predicting the label of a new observation. Let the joint distribution
of $(X,Y)$ be denoted by $\mathbb{P}$. The main goal of classification is to
find a classifier that minimizes the misclassification error or the 0-1 risk:

$R(h):=\mathbb{E}\big{\\{}\mathbbm{1}(h(X)\not=Y)\big{\\}}=\mathbb{P}\big{\\{}h(X)\not=Y\big{\\}},h\in\mathcal{H},$
(1)

where $\mathbbm{1}(E)$ is the indicator function of the set $E$ that is $1$ if
event $E$ occurs and $0$ otherwise. Let the measurable function
$h_{0}:\mathcal{X}\to\\{1,-1\\}$ be the misclassification risk minimizer at
the population level, i.e.,

$h_{0}:=\arg\min_{h\in\mathcal{H}}R(h).$ (2)

For any $h\in\mathcal{H}$, the excess risk of $h$ is the difference
$R(h)-R(h_{0})$ between the misclassification error of $h$ and $h_{0}$.

Since the probability measure $\mathbb{P}$ is unknown in practice, the
classifier $h$ will be learned based on a random sample
$S=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$ from $\mathbb{P}$, where $n$ is the sample
size. By minimizing the empirical excess risk over $\mathcal{H}$, the
empirical risk minimizer (ERM) is defined by

$\hat{h}_{n}\in\arg\min_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}(h(X_{i})\not=Y_{i}).$
(3)

However, the empirical risk function based on the $0$-$1$ loss is non-
continuous and non-convex in its argument, thus the minimization is typically
NP-hard and computational intractable.

Rather than minimizing the non-smooth 0-1 loss, many popular methods adopt a
proper convex loss function to train classifiers with computational efficiency
that can be done in polynomial time, e.g., logistic regression (Cox, 1958;
Kleinbaum et al., 2002), support vector machine (SVM) (Boser et al., 1992;
Cortes and Vapnik, 1995), and boosting (Freund et al., 1996). Moreover, proper
(classification calibrated) surrogate convex loss functions have been shown to
be consistent with the 0-1 loss function by Zhang (2004) and Bartlett et al.
(2006), in the sense that the minimizer of proper surrogate convex loss can
also produce a minimizer of the generic 0-1 loss for binary classification
problems. Nock and Nielsen (2008) and Masnadi-Shirazi and Vasconcelos (2009)
gave convincing arguments that the choice of surrogate loss function for the
classification problem depends on the joint distribution of $(X,Y)$. Further
developments on the surrogate convex loss methods were reported by Ben-David
et al. (2012), Masnadi-Shirazi and Vasconcelos (2015) and Telgarsky et al.
(2015), among others. A critical issue that affects performance in
classification is what hypothesis set $\mathcal{H}$ to choose (Mohri et al.,
2018). Popular choices for the hypothesis set have included those based on
reproducing kernels (Cristianini and Shawe-Taylor, 1999; Scholkopf and Smola,
2018) and tree structured models (Breiman et al., 1984; Hastie et al., 2001).

With the rapid developments in deep learning, various classification methods
with hypothesis sets specified through deep neural networks have achieved
remarkable successes in a variety of machine learning tasks (LeCun et al.,
2015; Schmidhuber, 2015). In particular, convolutional neural networks (CNN)
have demonstrated outstanding performance in many applications, including
computer vision (Krizhevsky et al., 2012), natural language processing (Wu et
al., 2016), and sequence analysis in bioinformatics (Alipanahi et al., 2015;
Zhou and Troyanskaya, 2015). However, to the best of our knowledge, there have
been no systematic studies on the properties of various classification methods
using CNNs in terms of the non-asymptotic bounds for the excess risks.

The excess risk of an empirical risk minimizer over CNNs is controlled by two
types of error: estimation error and approximation error. Zhang (2004),
Bartlett et al. (2006) and Mohri et al. (2018) established upper bounds on the
estimation error for a class of convex surrogate losses. In recent years,
several studies have provided insights into the empirical successes of CNNs
from a theoretical standpoint in terms of the capacity of CNNs and their
approximation power. Bartlett et al. (2017) and Golowich et al. (2020) derived
upper bounds for the covering number and Rademacher complexity of fully
connected neural networks without the bias term. Based on the same technique,
Lin and Zhang (2019) proved an upper bound of general convolutional neural
networks which allows arbitrarily ordered fully connected layers and
convolutional layers without bias. A similar result was proved by Zhou and
Feng (2018) for the fully convolutional networks with the last layer being
fully connected. Li et al. (2018) studied generalization error bounds of CNNs
composed of orthogonal filters. Arora et al. (2018) also gave complexity
bounds for deep networks via a compression approach. We provide a more
detailed discussion of the related works in Section 6 below.

###  1.1 Our contributions

In this paper, we consider the problem of binary classification with the
hypothesis set $\mathcal{H}$ specified using general deep convolutional neural
networks, which includes fully-connected neural networks and fully
convolutional neural networks as special cases. Our main contributions are as
follows.

  1. (i)

We establish non-asymptotic excess risk bounds for a class of classification
methods using CNNs. Our results are derived for a general class of convex
surrogate losses and target functions with different modulus of continuity.
They are applicable to many widely used classification methods in
applications, including those with the least squares, the logistic (cross-
entropy), the exponential and the SVM hinge loss functions.

  2. (ii)

An important feature of our risk bounds is that we clearly define the
prefactors in terms of the input data dimension $d$ and other model
parameters. Our risk bounds significantly improve over the currently available
ones in the sense that they depend polynomially on the dimensionality $d$ in
some important models including the logistic regression and SVM. This is
important since the prefactors can dominate the error bounds in high-
dimensional problems. However, the prefactor of the excess risk bound with the
exponential loss depends on $d$ exponentially. We provide an explanation for
the differences in the characteristics of the prefactors in terms of the
Lipschitz constants of these loss functions.

  3. (iii)

We show that the classification methods with CNNs can circumvent the curse of
dimensionality if the input data is supported on a neighborhood of a low-
dimensional manifold embedded in the ambient space $\mathbb{R}^{d}$.

  4. (iv)

We establish an upper bound for the covering number for the class of general
convolutional neural networks with a bias term in each convolutional layer,
and derive new results on the approximation power of CNNs for any uniformly-
continuous target functions. These results provide further insights into the
complexity and the approximation power of general convolutional neural
networks, which are of independent interest and may have applications in other
machine learning tasks involving CNNs.

  5. (v)

We apply our general results to analyze the non-asymptotic excess risk bounds
for four widely used classification methods with different losses using CNNs,
including the least squares, the logistic (cross-entrop), the exponential, and
the SVM hinge loss functions.

The rest of the paper is organized as follows. In section 2 we describe the
setup of the problem and the basic framework of convex surrogate loss
functions for classification. We also introduce a general class of
convolutional neural networks to be used in estimating the discriminant
function. In section 3 we present a basic inequality for the excess risk in
terms of the estimation error and the approximation errors. An upper bound for
the covering numbers of CNNs with bias terms in each of its layers is derived
for analyzing these errors. In section 4 we establish the consistency and an
explicit bound for the excess risk of empirical risk minimizer based on the
surrogate loss and its induced classifier under mild conditions, with and
without the approximate low-dimensional manifold assumption on the
distribution of the input data. We also derive an upper bound on the
approximation error of CNNs for any uniformly-continuous target functions
under the approximate low-dimensional manifold assumption. Several important
examples, including the logistic, the SVM and the exponential losses are
provided to illustrate our general convergence results in Section 5. In
Section 6 we discuss related works and comment on the differences of our work
with the existing ones. Discussions and closing remarks are given in section
7. Technical proofs are deferred to Appendix.

##  2  Preliminaries

In this section, we present the basic setup of the binary classification
problem and define the excess risk. We also introduce the convex surrogate
loss function and describe the structure of convolutional neural networks to
be used in the estimation of the discriminant function.

###  2.1 Misclassification error

The performance of a classification method is determined by the following
three factors: (i) the joint distribution of $X$ and $Y$, which determines how
well $X$ can predict $Y$; (ii) the loss function $\ell$ and the hypothesis set
$\mathcal{H}$; and (iii) the prediction rule. There are two possible scenarios
for the relationship between $X$ and $Y$: a deterministic relationship and a
stochastic one. In the deterministic scenario, it is assumed that
$Y=f_{0}(X)$, i.e., $Y$ is completely determined by $X$ through a
deterministic function $f_{0}:\mathcal{X}\to\\{1,-1\\}$. While in the
stochastic scenario, the label $Y$ cannot be solely decided by $X$, and the
relationship between $Y$ and $X$ is described by the conditional probability

$\eta(x):=\mathbb{P}(Y=1\mid X=x),\ x\in\mathcal{X}.$ (4)

As will be seen below, this conditional probability function plays a central
role in our analysis. The stochastic scenario is more realistic and general.
In this case, one cannot correctly predict the label of $X$ with certainty
unless $\eta$ only takes 1 or 0 on $\mathcal{X}$, for which the stochastic
scenario reduces to the deterministic one.

To elaborate, for any $x\in\mathcal{X}$ with $\eta(x)\in(0,1)$, the label $Y$
for a given $X=x$ could be $1$ or $-1$. Let ${\rm sign}(\cdot)$ be the sign
function, i.e., ${\rm sign}(x)=1$ if $x\geq 0$ and ${\rm sign}(x)=-1$
otherwise. Then, the best prediction for $Y$ for a given $X=x$ that achieves
minimal prediction error is the Bayes classifier

$h_{0}(x)={\rm sign}(\eta(x)-1/2)=\arg\max_{y\in\\{1,-1\\}}\mathbb{P}(Y=y\mid
X=x).$

However, one may still have $\min\\{\eta(x),1-\eta(x)\\}$ chance of making a
mistake in the prediction. When $\eta(x)=1/2$, the predicted label being $1$
or $-1$ makes no difference in terms of the probability of making a mistake.
Correspondingly, for each $x\in\mathcal{X}$, we define the noise function
${\rm noise}(x):=\min\\{\eta(x),1-\eta(x)\\}$. The noise is a characteristic
of the learning task indicative of its level of difficulty, and the Bayes
classifier achieves the minimal possible risk $R_{0}\equiv
R(h_{0})=\mathbb{E}\\{{\rm noise}(X)\\}$. The risk of the Bayes classifier is
often viewed as a benchmark. Our goal is to to find an $h\in\mathcal{H}$ that
minimizes $R(h)-R_{0}$.

However, the minimization problem (3) is computational intractable, as the
empirical risk function is non-continuous and non-convex in its argument.
Therefore, it is difficult to solve this empirical minimization problem in
practice. One of the prominent methods to alleviate this problem is to work
with a surrogate for the $0$-$1$ loss, so that the associated optimization
problem can be solved efficiently (Lin, 2004; Lugosi and Vayatis, 2004; Zhang,
2004; Bartlett et al., 2006).

###  2.2 Convex surrogate loss functions

We next give a brief review of the convex surrogate loss functions and discuss
the connection between the excess risk with respect to the $\phi$-loss and
that of 0-1 loss (Zhang, 2004; Bartlett et al., 2006).

Let $\phi$ be a given convex univariate function
$\phi:\mathbb{R}\to[0,\infty)$. Instead of minimizing the excess risk $R$ over
$\mathcal{H}$, we consider minimizing the risk with respect to the loss $\phi$
($\phi$-risk)

$\displaystyle R^{\phi}(f):=\mathbb{E}\\{\phi(Yf(X))\\}$

over a certain class of functions $\mathcal{F}$, where
$\phi:\mathbb{R}\to[0,\infty)$ is some generic loss function. For the special
case when $\mathcal{H}=\\{h:h(x)={\rm sign}(f(x)),f\in\mathcal{F}\\}$ and
$\phi(\cdot)$ is a step function, i.e., $\phi(x)=1$ if $x<0$ and $\phi(x)=0$
if $x\geq 0$, then to minimize ${R}$ over $\mathcal{H}$, it suffices to
minimize $R^{\phi}$ over $\mathcal{F}$. Given
$S=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$, let
$R^{\phi}_{n}(f):=\sum_{i=1}^{n}\phi(Y_{i}f(X_{i}))/n$ be the empirical risk
of $f$ w.r.t the $\phi$-loss, and define the empirical risk estimator (ERM) as

$\hat{f}^{\phi}_{n}\in\arg\min_{f\in\mathcal{F}}R^{\phi}_{n}(f).$ (5)

Based on the ERM $\hat{f}^{\phi}_{n}$, a classification rule or a classifier
$\hat{h}_{n}^{\phi}(x):={\rm sign}(\hat{f}^{\phi}_{n}(x))$ for
$x\in\mathcal{X}$ can be induced which aims at minimizing the 0-1 risk in (3).
As shown in Zhang (2004) and Bartlett et al. (2006), for a properly chosen
$\phi$, $\hat{f}^{\phi}_{n}$ can indeed help reduce the excess risk
$R(\hat{h}^{\phi}_{n})-R_{0}$. More precisely, let $R^{\phi}_{0}:=\inf_{f{\
\rm measurable}}R^{\phi}(f)$, then for a proper $\phi$, we have

$\psi(R(\hat{h}^{\phi}_{n})-R_{0})\leq
R^{\phi}(\hat{f}_{n}^{\phi})-R^{\phi}_{0},$

where $\psi:[-1,1]\to[0,\infty)$ is a nonnegative continuous function,
invertible on $[0,1]$, and achieves its minimum at $0$ with $\psi(0)=0$. A
wide variety of popular classification methods are based on this tactic. For
instance, when $\phi(a)=\log\\{1+\exp(-a)\\}$, it is the logistic regression
(Friedman et al., 2000); when $\phi(a)=\max\\{1-a,0\\}$, it becomes the SVM
(Cortes and Vapnik, 1995); when $\phi(a)=\exp(-a)$ is the exponential loss, it
is the AdaBoost algorithm (Freund et al., 1996); when $\phi(a)=(1-a)^{2}$, it
is the least squares method for classification, and so on.

Define the measurable minimizer of $R^{\phi}$ as

$f^{\phi}_{0}=\arg\min_{f{\ \rm measurable}}\mathbb{E}\\{\phi(Yf(X))\\},$ (6)

and the corresponding minimal $\phi$-risk as
$R^{\phi}_{0}=R^{\phi}(f^{\phi}_{0})$. Clearly, the optimal $f^{\phi}_{0}$
depends on the loss function $\phi$. If $\phi$ is not properly chosen, the
resulting $f^{\phi}_{0}$ can be poor and thus the classifier
${h}_{0}^{\phi}(x)={\rm sign}({f}^{\phi}_{0}(x))$ based on $f^{\phi}_{0}$ can
be invalid. To study the basic conditions imposed on $\phi$, so as to produce
a valid classifier towards minimizing the 0-1 loss, we need a thorough
understanding of the risk $R^{\phi}$.

Let the conditional $\phi$-risk of $f$ given $X=x$ be denoted by
$R_{x}^{\phi}(f):=\mathbb{E}\\{\phi(Yf(X))\mid X=x\\}$. Recall that
$\eta(x)=\mathbb{P}\\{Y=1\mid X=x\\}$ as defined in (4). We have

$R_{x}^{\phi}(f)=\eta(x)\phi(f(x))+\\{1-\eta(x)\\}\phi(-f(x)),\
x\in\mathcal{X}.$

For a good classifier, if $\eta(x)>1/2$, it is naturally expected that
$f_{0}^{\phi}(x)>0$ and $h_{0}^{\phi}(x)={\rm sign}(f^{\phi}_{0}(x))=1$
(correct sign); thus to encourage $f_{0}^{\phi}(x)>0$, we should at least
require $\phi(f_{0}^{\phi}(x))<\phi(-f_{0}^{\phi}(x))$ to minimize the
conditional risk $R^{\phi}_{x}$. Similarly, if $\eta(x)<1/2$, we expect that
the contrary happens. A rigorous definition for such an ideal $\phi$ is given
in Definition 1 of Bartlett et al. (2006).

######  Definition 1 (Classification-calibrated)

For $\eta\in[0,1]$ and $a\in\mathbb{R}$, define
$H^{\phi}(\eta,a)=\eta\phi(a)+(1-\eta)\phi(-a)$. Then, we say that $\phi$ is
classification-calibrated if for any $\eta\not=1/2$,

$\inf_{a\in\mathbb{R}}H^{\phi}(\eta,a)<\inf_{a\in\mathbb{R}:a(2\eta-1)\leq
0}H^{\phi}(\eta,a).$

With a classification-calibrated loss $\phi$, it is guaranteed that the
“incorrect” label ${\rm sign}(f(X))$ in the sense that it is inconsistent with
the Bayes estimator ${\rm sign}(2\eta(X)-1)$) results in a strictly larger
loss under $\phi$. It was shown by Bartlett et al. (2006) that, the surrogate
loss function $\phi$ is able to produce the optimal Bayes classifier. For ease
of reference, we state this result as Lemma 2 below.

######  Lemma 2 (Theorem 1 of Bartlett et al. (2006))

For any nonnegative loss function $\phi:\mathbb{R}\to[0,\infty)$, any
measurable $f:\mathcal{X}\to\mathbb{R}$, its induced classifier $h_{f}={\rm
sign}(f):\mathcal{X}\to\\{\pm 1\\}$, and any probability measure $\mathbb{P}$
of $(X,Y)$ on $\mathcal{X}\times\\{\pm 1\\}$,

$\psi(R(h_{f})-R_{0})\leq R^{\phi}(f)-R^{\phi}_{0},$

where $\psi:[-1,1]\to[0,\infty)$ is the Fenchel-Legendre biconjugate of
$\tilde{\psi}:[-1,1]\to\mathbb{R}$, and

$\tilde{\psi}(\theta)=\inf_{a\in\mathbb{R}:a(2\eta-1)\leq
0}H(\frac{1+\theta}{2})-\inf_{a\in\mathbb{R}}H(\frac{1+\theta}{2}).$

Besides, if $\phi$ is classification-calibrated, then for any sequence
$\\{a_{m}\\}$ in $[0,1]$, $\psi(a_{m})\to 0$, if and only if $a_{m}\to 0$.

Lemma 2 has some important implications. First, for any nonnegative $\phi$,
$\psi$ is simply the functional convex hull (the greatest convex minorant) of
$\tilde{\psi}$. Both $\psi$ and $\tilde{\psi}$ are continuous on $[-1,1]$, and
$\psi$ is nonnegative that attains its minimum at 0 with $\psi(0)=0$. Second,
if the loss $\phi$ is nonnegative and classification-calibrated, then
$\psi(\theta)>0$ for all $\theta\in(0,1]$ and $\psi$ is invertible on $[0,1]$.
In this case, we have $R(h_{f})-R_{0}\leq\psi^{-1}(R^{\phi}(f)-R^{\phi}_{0})$.
Third, if $\phi$ is nonnegative convex and classification-calibrated, then
$\psi(\theta)=\phi(0)-\inf_{a\in\mathbb{R}}H^{\phi}((1+\theta)/2,a)$, which
gives an easy way to compute the function $\psi$.

Next, we present several examples of $\phi$, and the corresponding
$f_{0}^{\phi}$, $R^{\phi}(f_{0}^{\phi})$, $\psi$ and its inverse on $[0,1]$ in
Table 1.

Table 1: Minimizer and minimal conditional risk under different loss functions
$\phi$.

| Least squares | SVM | Exponential | Logistic
---|---|---|---|---
$\phi(a)$ | $(1-a)^{2}$ | $\max\\{1-a,0\\}$ | $\exp(-a)$ | $\log\\{1+\exp(-a)\\}$
$f^{\phi}_{0}(x)$ | $2\eta-1$ | ${\rm sign}(2\eta-1)$ | $\frac{1}{2}\log(\frac{\eta}{1-\eta})$ | $\log(\frac{\eta}{1-\eta})$
$R^{\phi}_{x}(f^{\phi}_{0})$ | $4\eta(1-\eta)$ | $1-|2\eta-1|$ | $2\sqrt{\eta(1-\eta)}$ | $-\eta\log(\eta)-(1-\eta)\log(1-\eta)$
$\psi(\theta)$ | $\theta^{2}$ | $|\theta|$ | $1-\sqrt{1-\theta^{2}}$ | $\frac{1+\theta}{2}\log(\frac{1+\theta}{1-\theta})+\log(1-\theta)$
$\psi^{-1}(\theta)$ | $\sqrt{\theta}$ | $|\theta|$ | $\sqrt{1-(1-\theta)^{2}}$ | ***

Note: $\eta(x)$ is written as $\eta$ for notational simplicity. “***” stands
for no explicit form.

###  2.3 Convolutional neural networks

As indicated by their name, CNNs employ a mathematical operation called
convolution. Convolutional networks are a specialized type of structured
sparse feedforward neural network (FNN) that use convolution in place of
general matrix multiplication in at least one of their layers (Goodfellow et
al., 2016). There are different formulations of CNNs in the literature (Bao et
al., 2014; Zhou and Feng, 2018; Oono and Suzuki, 2019; Lin and Zhang, 2019;
Zhou, 2020a, b). In this paper, we consider a generic formulation of CNNs with
bias vectors in the convolutional layers, which is a generalization of that
defined in Lin and Zhang (2019) and covers the multi-layer perceptions (MLP),
fully convolutional neural networks (FCNNs) and general convolutional neural
networks (CNNs), i.e neural networks with arbitrarily ordered and mixed layers
(each layer can be fully convolutional layer or fully-connected layer).

For a general neural network, let $L$ denote the number of layers and
$(\sigma_{1},\ldots,\sigma_{L})$ denote the activation functions, such as the
rectified linear unit (ReLU) and max pooling function. In this paper, it is
assumed that $\sigma_{i}(0)=0$ and $\sigma_{i}$ is $\rho_{i}$-Lipschitz for
$i=1,\ldots,L$. Besides, let $d_{i}$ denote the width (the number of neurons
or computational units) of the $i$-th layer, $i=1,\ldots,L$, and
$\mathcal{W}=\max\\{d_{1},\ldots,d_{L}\\}$ denote the maximum width among
layers. In our present classification problem, $d_{1}=d$ (the dimension of the
input $X$) and $d_{L}=1$ (the dimension of the output $Y$).

Next, we describe the architectures of MLPs, FCNNs and CNNs.

  * •

The architecture of a MLP $f_{MLP}:\mathbb{R}^{d}\to\mathbb{R}$ can be
expressed as a composition of a series of linear transformations: for any
$x\in\mathbb{R}^{d}$,

$f_{MLP}(x)=\sigma_{L}(W_{L}\sigma_{L-1}(\cdots\sigma_{2}(W_{2}\sigma_{1}(W_{1}x+b_{1})+b_{2})\cdots)+b_{L}),$
(7)

where $W_{i}\in\mathbb{R}^{d_{i+1}\times d_{i}}$ is a fully connected weight
matrix, and $b_{i}\in\mathbb{R}^{d_{i+1}}$ is a bias vector in the $i$-th
linear transformation. Usually, the activation functions
$(\sigma_{1},\ldots,\sigma_{L})$ are the ReLU activation, where
$\mbox{ReLU}(x)=\max\\{0,x\\}$ for any $x\in\mathbb{R}$ (defined for each
component of $x$ if $x$ is a vector).

  * •

The architecture of a FCNN $f_{FCNN}:\mathbb{R}^{d}\to\mathbb{R}$ is similar
to that of MLP, but with structured sparse weight matrix. For any
$x\in\mathbb{R}^{d}$,

$f_{FCNN}(x)=\sigma_{L}(W^{c}_{L}\sigma_{L-1}(\cdots\sigma_{2}(W^{c}_{2}\sigma_{1}(W^{c}_{1}x+b^{c}_{1})+b^{c}_{2})\cdots)+b^{c}_{L}),$
(8)

where $b^{c}_{i}\in\mathbb{R}^{d_{i+1}}$ is the bias vector, and
$W^{c}_{i}\in\mathbb{R}^{d_{i+1}\times d_{i}}$ is the structured weight matrix
induced by the convolutional weights $C_{i}\in\mathbb{R}^{r_{i}\times s_{i}}$
which contains $r_{i}$ convolutional filters, each of which has dimension (or
size) $s_{i}$, $i=1,\ldots,L$. For FCNN, the activation functions are taken to
be the ReLU or the max pooling function. We elucidate what the max pooling
function is and how the convolutional weight $C_{i}$ generates $W^{c}_{i}$
later in this subsection.

  * •

The formulation of a CNN $f_{CNN}:\mathbb{R}^{d}\to\mathbb{R}$ is essentially
a combination of the architectures of MLP and FCNN,

$f_{CNN}=\sigma_{L}\circ A_{L}\cdots\circ\sigma_{2}\circ
A_{2}\circ\sigma_{1}\circ A_{1},$ (9)

where $\circ$ denotes the functional composition and $A_{i}$ is a linear
operation, $i=1,\ldots,L$. The form of $A_{i}$ is either

$A_{i}(x)=W_{i}x+b_{i},$

where $W_{i}\in\mathbb{R}^{d_{i+1}\times d_{i}}$ and
$b_{i}\in\mathbb{R}^{d_{i+1}}$, or

$A_{i}=W^{c}_{i}x+b^{c}_{i},$

where $W^{c}_{i}\in\mathbb{R}^{d_{i+1}\times d_{i}}$ is the structured sparse
weight matrix induced by the convolutional weights
$C_{i}\in\mathbb{R}^{r_{i}\times s_{i}}$, and
$b^{c}_{i}\in\mathbb{R}^{d_{i+1}}$ is bias vector. Basically, each layer of a
CNN is either a fully connected layer or a convolutional layer.

Now, we illustrate how structured weight matrices are generated by convolution
operations for convolutional layers. Consider a single convolutional layer,
let $C=(c_{1},\ldots,c_{r})\in\mathbb{R}^{r\times s}$ denote the $r$
convolutional filters with the same dimension $s$, and $X\in\mathbb{R}^{d}$ be
an input vector. For each filter $c_{i}$, the convolutional operation performs
$M$-times inner product on $c_{i}$ and an $s$-dimensional subvector of the
$d$-dimensional covariate $X$. For the $m$-th operation, let
$S_{m}\in\mathbb{N}_{+}^{s}$ be the index set consisting of the indices of the
$s$-dimensional subvector $X_{S_{m}}$ of $X$. Then, the $m$-th linear
combination for the filter $c_{i}$ is

$c_{i}^{\top}X_{S_{m}}=c_{i,S_{m}}^{\top}X,$

where $c_{i,S_{m}}\in\mathbb{R}^{d}$ is expanded $c_{i}$, i.e. elements of
$c_{i,S_{m}}$ are re-arranged to the places indexed by $S_{m}$ while filling
the other places with zeros. For a better understanding, an example as in Lin
and Zhang (2019) is illustrated here. Consider a 2-D convolutional filter
$c\in\mathbb{R}^{2\times 2}$ (with dimension or size 4) and a 2-D input (2
channels) $X\in\mathbb{R}^{3\times 4}$ as follows:

$c=\left[\begin{matrix}c_{1,1}&c_{1,2}\\\
c_{2,1}&c_{2,2}\end{matrix}\right],{\ \rm and\
}X=\left[\begin{matrix}X_{1,1}&X_{1,2}&X_{1,3}&X_{1,4}\\\
X_{2,1}&X_{2,2}&X_{2,3}&X_{2,4}\\\
X_{3,1}&X_{3,2}&X_{3,3}&X_{3,4}\end{matrix}\right].$

A standard convolution operation with stride (or step size) one performs $m=6$
times linear combination orderly. To help understand the operations here,
imagine $c$ as a pad sliding on the surface of another pad $X$ each step for
one time, from the top-left (when $c_{1,1}$ aligns with $X_{1,1}$ and
$c_{2,2}$ aligns with $X_{2,2}$) to the bottom-right (when $c_{1,1}$ aligns
with $X_{2,3}$ and $c_{2,2}$ aligns with $X_{3,4}$). For each slide, we move
$c$ by one step (one grid of matrix), match the respective elements of $c$ and
$X$, calculate their inner product, and save the result into a proper element
of the resulting matrix. Finally, the resulting matrix is

$c*X\equiv\left[\begin{matrix}\sum_{i=1,j=1}^{2}c_{i,j}X_{i,j}\ \
&\sum_{i=1,j=1}^{2}c_{i,j}X_{i,j+1}\ \ &\sum_{i=1,j=1}^{2}c_{i,j}X_{i,j+2}\\\
\sum_{i=1,j=1}^{2}c_{i,j}X_{i+1,j}&\sum_{i=1,j=1}^{2}c_{i,j}X_{i+1,j+1}&\sum_{i=1,j=1}^{2}c_{i,j}X_{i+1,j+2}\\\
\end{matrix}\right].$

Here, $c*X$ denotes the convolution of matrix $c$ and $X$.

Let
$X^{\prime}=(X_{1,1},X_{1,2},X_{1,3},X_{1,4},X_{2,1},X_{2,2},X_{2,3},X_{2,4},X_{3,1},X_{3,2},X_{3,3},X_{3,4})^{\top}$
be the 1-D vector of reshaped $X$. Then, the induced weight matrix $W^{c}$ of
$c$ is

$W^{c}=\left[\setcounter{MaxMatrixCols}{12}\begin{matrix}c_{1,1}&c_{1,2}&0&0&c_{2,1}&c_{2,2}&0&0&0&0&0&0\\\
0&c_{1,1}&c_{1,2}&0&0&c_{2,1}&c_{2,2}&0&0&0&0&0\\\
0&0&c_{1,1}&c_{1,2}&0&0&c_{2,1}&c_{2,2}&0&0&0&0\\\
0&0&0&0&c_{1,1}&c_{1,2}&0&0&c_{2,1}&c_{2,2}&0&0\\\
0&0&0&0&0&c_{1,1}&c_{1,2}&0&0&c_{2,1}&c_{2,2}&0\\\
0&0&0&0&0&0&c_{1,1}&c_{1,2}&0&0&c_{2,1}&c_{2,2}\\\ \end{matrix}\right].$

Note that $W^{c}X^{\prime}\in\mathbb{R}^{6}$ is the 1-D vector of the reshaped
$c*X$. With the above notation, the induced weight matrix $W^{c}$ of a
convolutional matrix $C=(c_{1},\ldots,c_{r})$ with $r$ filters, each of which
performs $m$ operations, can be written as

$W^{c}=(c_{1,S_{1}},\ldots,c_{1,S_{m}},c_{2,S_{1}},\ldots,c_{2,S_{m}},\ldots,c_{r,S_{1}},\ldots,c_{r,S_{m}})^{\top}\in\mathbb{R}^{d_{out}\times
d_{in},}$

where $d_{in}$ is the dimension of the input of this layer, $d_{out}$ is the
dimension of the output of the layer and $d_{out}=rm$. For 3-D or tensor data
with channels more than 2, the filters can be designed to accommodate them
without further difficulty, and the induced weight matrix can be formulated in
a similar fashion.

Max-pooling function is a mapping from a finite-dimensional vector space
(possibly arranged as matrices or tensors) to another one. Given a vector
$U=(u_{1},\ldots,u_{d_{in}})^{\top}\in\mathbb{R}^{d_{in}}$, the max-pooling
operator iterates over a collection of sets of indices $\mathcal{I}$ and
outputs $V=(v_{1},\ldots,v_{d_{out}})^{\top}\in\mathbb{R}^{d_{out}}$, where
the cardinality of $\mathcal{I}$ equals to the dimension of the output
$d_{out}$. For each element $I_{i}\in\mathcal{I}$, the $i$-th component of the
output $V$ is the maximal entry of the input $U$ over index $I_{i}$, i.e.
$V_{i}:=\max_{j\in I_{i}}U_{j}.$

As shown in Lemma A.2 in Bartlett et al. (2017), the Lipschitz constant of the
max-pooling operators depends on the number of times each coordinate is
accessed across elements of $\mathcal{I}$. To be precise, if each coordinate
of the input appears in at most $m$ elements of the collection $\mathcal{I}$,
then the max-pooling operator is $m^{1/p}$-Lipschitz w.r.t the $L_{p}$-norm
$\|\cdot\|_{p}$ for any $p\geq 1$. The max-pooling operator is 1-Lipschitz
whenever $\mathcal{I}$ forms a partition. In practice, for computer vision
tasks, the number of times $m$ in the max-pooling operator is often a small
constant.

##  3 Excess $\phi$-risk

In this section, we present a basic inequality for the excess $\phi$-risk and
focus the discussions on the stochastic error and approximation error.

###  3.1 Excess risk decomposition

With a nonnegative, convex and classification-calibrated surrogate loss
function $\phi$, it is no longer necessary to minimize the excess 0-1 risk
$R(h_{f})-R_{0}$, instead we turn to minimize the excess $\phi$-risk
$R^{\phi}(f)-R^{\phi}_{0}$ and rest assured that

$R(h_{f})-R_{0}\leq\psi^{-1}(R^{\phi}(f)-R^{\phi}_{0}).$

From now on, we assume that $\phi$ is nonnegative, convex and classification-
calibrated, and focus our study on the excess $\phi$-risk
$R^{\phi}(f)-R^{\phi}_{0}$.

To begin with, for any estimator $f$ belonging to a certain class of functions
$\mathcal{F}$, its excess $\phi$-risk can be decomposed as (Mohri et al.,
2018)

$R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})=\left\\{R^{\phi}(f)-\inf_{f\in\mathcal{F}}R^{\phi}(f)\right\\}+\left\\{\inf_{f\in\mathcal{F}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})\right\\},$

where $f^{\phi}_{0}$ is defined in (6). The first term of the right hand side
is the estimation error, and the second term is the approximation error. The
estimation error depends on the estimator $f$, which measures the difference
of the error of $f$ and the best one in $\mathcal{F}$. The approximation error
only depends on the function class $\mathcal{F}$, which measures how well the
function $f_{0}^{\phi}$ can be approximated using $\mathcal{F}$ with respect
to the loss $\phi$. For a complex and rich function class $\mathcal{F}$, the
approximation error is likely to be small, while at the same time the
estimation error is likely to be large.

For the classification problem under investigation, $f$ is the ERM
$\hat{f}^{\phi}_{n}$ defined in (5). A general upper bound on the excess risk
of $\hat{f}_{n}^{\phi}$ is given below.

###### Lemma 3

For any loss $\phi$ and any random sample $S=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$,
the excess $\phi$-risk of the ERM $\hat{f}^{\phi}_{n}$ satisfies

$\displaystyle R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f^{\phi}_{0})\leq$
$\displaystyle
2\sup_{f\in\mathcal{F}}|R^{\phi}(f)-R^{\phi}_{n}(f)|+\inf_{f\in\mathcal{F}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0}).$
(10)

The excess risk of $\hat{f}_{n}^{\phi}$ is bounded above by the sum of two
terms: the stochastic error
$2\sup_{f\in\mathcal{F}}|R^{\phi}(f)-R^{\phi}_{n}(f)|$ and the approximation
error $\inf_{f\in\mathcal{F}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$. Notice that
the upper bound no longer depend on the ERM, but the function class
$\mathcal{F}$, the loss function $\phi$ and the random sample $S$. The first
term $2\sup_{f\in\mathcal{F}}|R^{\phi}(f)-R^{\phi}_{n}(f)|$ is closely related
to the complexity of $\mathcal{F}$ and the second term
$\inf_{f\in\mathcal{F}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$ measures the
approximation power of the function class $\mathcal{F}$ for $f_{0}^{\phi}$.

Throughout the paper, we choose $\mathcal{F}$ to be a function class
$f:\mathcal{X}\to\mathbb{R}$ consisting of convolutional neural networks,
denoted by $\mathcal{F}_{CNN}$. To give a mathematical definition of the
function class $\mathcal{F}_{CNN}$, more notations are needed. Let
$(\sigma_{1},\ldots,\sigma_{L})$ be fixed Lipschitz mappings (each
$\sigma_{i}$ is $\rho_{i}$-Lipschitz). Let $\mathcal{L}_{F}$ be a subset of
indices $\\{1,\ldots,L\\}$ and
$\mathcal{L}_{C}=\\{1,\ldots,L\\}\backslash\mathcal{L}_{F}$ be its complement,
and let $A=(A_{1},\ldots,A_{L})$ be $L$ linear operators with their respective
input dimension $(d_{1},\ldots,d_{L})$. Here, for $l\in\mathcal{L}_{F}$,
$A_{l}(X)=W_{l}X+b_{l}$ with fully connected weights
$W_{l}\in\mathbb{R}^{d_{l}\times d_{l+1}}$ and bias
$b_{l}\in\mathbb{R}^{d_{l+1}}$; for $l\in\mathcal{L}_{C}$,
$A_{l}(X)=W^{c}_{l}X+b^{c}_{l}$ with $W^{c}_{l}\in\mathbb{R}^{d_{l}\times
d_{l+1}}$ induced by convolutional weights $C_{l}\in\mathbb{R}^{r_{i}\times
s_{i}}$ and bias $b^{c}_{l}\in\mathbb{R}^{d_{l+1}}$. Let $m_{l}$ denote the
number of operations performed by each of the $r_{l}$ filters in convolutional
layer $l\in\mathcal{L}_{C}$. Let $(a_{1},\ldots,a_{L})$ be positive numbers
uniformly bounded by $B_{a}>0$ and let
$(\mathcal{A}_{1},\ldots,\mathcal{A}_{L})$ be sets with
$\mathcal{A}_{l}=\\{A_{l}:\|W_{l}\|_{F}+\|b_{l}\|_{F}\leq a_{l}\\}$ for
$l\in\mathcal{L}_{F}$ and
$\mathcal{A}_{l}=\\{A_{l}:\|C_{l}\|_{F}+\|b^{c}_{l}\|_{F}\leq a_{l}\\}$ for
$l\in\mathcal{L}_{C}$, where $\|\cdot\|_{F}$ is the Frobenius norm. For a
general function class $\mathcal{F}$ and any $f_{1},f_{2}\in\mathcal{F}$,
define the $\|\cdot\|_{\infty}$ metric on $\mathcal{F}$ by
$\sup_{X\in\mathcal{X}}\|f_{1}(X)-f_{2}(X)\|_{\infty}$. Then, the function
class consisting of CNNs is defined as

$\mathcal{F}_{CNN}=\\{f:\mathcal{X}\to\mathbb{R}^{d_{L}}:f=\sigma_{L}\circ
A_{L}\cdots\circ\sigma_{1}\circ A_{1},A_{l}\in\mathcal{A}_{l}{\ \rm for\
}l=1,\ldots,L\\}.$ (11)

Let $\mathcal{B}:=\sup_{f\in\mathcal{F}_{CNN}}\|f\|_{\infty}$ denote the bound
of functions in $\mathcal{F}_{CNN}$,
$\mathcal{S}=\sum_{l\in\mathcal{L}_{F}}(d_{l-1}+1)\times
d_{l}+\sum_{l\in\mathcal{L}_{C}}(s_{i}+m_{i})\times r_{l}$ be the number of
parameters for networks in $\mathcal{F}_{CNN}$ and let
$\mathcal{W}=\max\\{d_{1},\ldots,d_{L}\\}$ be the maximum width among layers.

For a given sample $S=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$, with a slight abuse of
notation, we still denote the ERM over $\mathcal{F}_{CNN}$ w.r.t loss $\phi$
by

$\hat{f}^{\phi}_{n}\in\arg\min_{f\in\mathcal{F}_{CNN}}\frac{1}{n}\sum_{i=1}^{n}\phi(Yf(X_{i})).$
(12)

###  3.2 Estimation error

In this subsection, we focus on the estimation error of ERM based on CNNs and
give an upper bound on the estimation error. To this end, we first establish
an upper bound for the covering numbers of CNNs with a bias term in each of
its layers.

######  Theorem 4 (Covering number of CNNs)

Let $\mathcal{F}_{CNN}$ be the class of functions defined in (11). Then, for
any $\epsilon>0$,

$\log\mathcal{N}(\mathcal{F}_{CNN},\epsilon,\|\cdot\|_{\infty})\leq
2\mathcal{S}\log\Big{(}1+\frac{L\mathcal{B}}{\epsilon}\Big{)},$

where $\mathcal{N}(\mathcal{F}_{CNN},\epsilon,\|\cdot\|_{\infty})$ denotes the
covering number of $\mathcal{F}_{CNN}$ under metric $\|\cdot\|_{\infty}$ with
radius $\epsilon$.

The covering number in Theorem 3.2 is derived by an approach similar to that
in Bartlett et al. (2017), Golowich et al. (2020) and Lin and Zhang (2019). In
these works, the covering number of a given neural network is upper bounded by
terms relevant to the complexity measures depending on the Lipschitz constants
of the activation functions and the norms of weight matrices. Similar to Lin
and Zhang (2019) but different from many other methods, our upper bound of the
covering number is represented by parameters of the general convolutional
neural networks that contain both fully-connected layers and convolutional
layers, and the complexity is bounded by the norm of convolutional weights
rather than the induced weight matrix. In addition, unlike many existing
works, the general convolutional neural networks considered in this paper
allow for the bias term in each layer.

###### Remark 5

Upper bounds for the covering numbers of a single fully-connected layer or a
single convolutional layer are also given in Lemma 16 and 17 in Appendix A. In
particular, let $X\in\mathbb{R}^{d_{in}}$ be an input vector of the layer with
a bounded norm, i.e. $\|X\|_{F}=\|X\|_{2}<\infty$, and let $\sigma$ be a
$\kappa$-Lipschitz activation function. For a convolutional layer with
convolutional weights $C=(c_{1},\ldots,c_{r})\in\mathbb{R}^{r\times s}$ (with
$r$ filters of size $s$, each of which performs $m$ times operation, i.e.
$d_{out}=r\times m$), induced weight matrix $W^{c}\in\mathbb{R}^{d_{out}\times
d_{in}}$, and bias vector $b^{c}\in\mathbb{R}^{d_{out}}$ satisfying
$\|C\|_{F}+\|b^{c}\|_{F}\leq a$, then the covering number of the function
class
$\mathcal{F}^{C}_{a}(X):=\\{\sigma(W^{c}X+b^{c})\in\mathbb{R}^{d_{out}}:\|C\|_{F}+\|b^{c}\|_{F}\leq
a\\}$ under metric $\|\cdot\|_{\infty}$ with radius $\epsilon$ satisfies

$\log\mathcal{N}(\mathcal{F}^{C}_{a}(X),\epsilon,\|\cdot\|_{\infty})\leq
r\times(s+m)\log\left\\{1+\frac{2a\kappa(\sqrt{m}\|X\|_{F}+1)}{\epsilon}\right\\}.$

To make a fair comparison, for a single fully-connected layer with weight
matrix $W\in\mathbb{R}^{d_{out}\times d_{in}}$ and bias vector
$b\in\mathbb{R}^{d_{out}}$, we consider the covering number of its output
space subject to $\|W\|_{F}/\sqrt{m}+\|b\|_{F}\leq a$, i.e.
$\mathcal{F}^{F}_{a}(X):=\\{\sigma(WX+b)\in\mathbb{R}^{d_{out}}:\|W\|_{F}/\sqrt{m}+\|b\|_{F}\leq
a\\}$. It has been shown that the upper bound of the covering number of
$\mathcal{F}^{F}_{a}(X)$ under metric $\|\cdot\|_{\infty}$ with radius
$\epsilon$ is

$\log\mathcal{N}(\mathcal{F}^{F}_{a}(X),\epsilon,\|\cdot\|_{\infty})\leq
d_{out}\times(d_{in}+1)\log\left\\{1+\frac{2a\kappa(\sqrt{m}\|X\|_{F}+1)}{\epsilon}\right\\}.$

It can be seen that the upper bound of the covering number of a single layer
depends on the number of nonzero parameters in the layer. For a convolutional
layer (CL) and a fully connected layer (FCL) with equal input and output
dimensions, as long as the number of filters $r\leq d_{out}$ and each filter
size $s\leq d_{in}$, the covering number of CL will be smaller than that of
FCL. In various image classification tasks (the data usually have special
structures), FCLs generally performs no better than CLs in terms of their
approximation powers or feature extraction ability, although $d_{out}\gg r$
and $d_{in}\gg s.$ In such cases, the use of CNNs could dramatically reduce
the networks complexities without sacrificing the performance and boosts the
computational efficiency.

Based on Theorem 4, we are now in a position to give an upper bound on the
estimation error in terms of the covering number or the parameters of the
function class $\mathcal{F}_{CNN}$. We assume that the loss function $\phi$
satisfies the following assumption.

###### Assumption 1

The loss function $\phi:\mathbb{R}\to[0,\infty)$ is convex and classification-
calibrated. Moreover, $\phi$ is $B_{\phi}$-Lipschitz on any bounded interval
$M\subset[-\mathcal{B},\mathcal{B}]$, i.e.,

$|\phi(x)-\phi(y)|\leq B_{\phi}|x-y|,$

for any $x,y\in M\subset[-\mathcal{B},\mathcal{B}]$.

The Lipschitz constants $B_{\phi}$ for several common $\phi$ loss functions
are given in Table 2.

###### Theorem 6

Suppose that Assumption 1 holds. Let $\mathcal{F}_{CNN}$ be the function class
defined in (11), $\mathcal{B}:=\sup_{f\in\mathcal{F}_{CNN}}\|f\|_{\infty}$
denote the bound of functions in $\mathcal{F}_{CNN}$ and let
$\mathcal{S}=\sum_{l\in\mathcal{L}_{F}}(d_{l-1}+1)\times
d_{l}+\sum_{l\in\mathcal{L}_{C}}(s_{i}+m_{i})\times r_{l}$ denote the number
of parameters for the networks in $\mathcal{F}_{CNN}.$ Then, the empirical
$\phi$-risk minimizer $\hat{f}^{\phi}_{n}$ defined in (12) satisfies, for any
$\delta\in(0,1)$, with probability at least $1-\delta$,

$\sup_{f\in\mathcal{F}_{CNN}}|R^{\phi}(f)-R^{\phi}_{n}(f)|\leq\frac{8\sqrt{2}B_{\phi}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{\sqrt{n}}+B_{\phi}\mathcal{B}\sqrt{\frac{2\log(1/\delta)}{n}},$

and

$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f^{\phi}_{0})\leq\frac{16\sqrt{2}B_{\phi}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{\sqrt{n}}+2B_{\phi}\mathcal{B}\sqrt{\frac{2\log(1/\delta)}{n}}+\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0}).$

According to Lemma 3, the estimation error
$R^{\phi}(\hat{f}_{n}^{\phi})-\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)$ is
bounded by $2\sup_{f\in\mathcal{F}}|R^{\phi}(f)-R^{\phi}_{n}(f)|$ and can be
further bounded by the complexity of $\mathcal{F}_{CNN}$ with high
probability. In Theorem 6, the complexity of $\mathcal{F}_{CNN}$ is measured
by Rademacher complexity; by Dudley’s integral, it can be further contained by
the covering number, which is represented in terms of the network parameters
$\mathcal{B},\mathcal{S}$ and $L$. This leads to an upper bound for the
prediction/generalization error by the sum of the estimation error and the
approximation error of $\mathcal{F}_{CNN}$ to $f^{\phi}_{0}$.

###  3.3 Approximation error

The approximation error
$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$ describes how
well $R^{\phi}(f^{\phi}_{0})$ can be approximated by CNNs in
$\mathcal{F}_{CNN}$. The existing works on the approximation power of neural
networks mainly focus on multi-layer perceptions, with a particular interest
on the quantity $\inf_{f\in\mathcal{F}_{MLP}}\|f-f^{\phi}_{0}\|$ for a certain
norm $\|\cdot\|$ and some smooth target function $f^{\phi}_{0}$ defined on a
bounded compact set, e.g. $[0,1]^{d}$. In classification tasks, especially
image classification, the support $\mathcal{X}$ of the input $X$ is exactly
$[0,1]^{d}$. Thereafter, we focus our discussion on those target functions
$f^{\phi}_{0}$ defined on $\mathcal{X}=[0,1]^{d}.$

We derive an upper bound of the approximation error
$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$ by leveraging
the recent powerful approximation theories for deep neural networks. First, we
relate $\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$ to
$\inf_{f\in\mathcal{F}_{CNN}}\|f-f^{\phi}_{0}\|$. Second, the target function
$f^{\phi}_{0}$ may be non-smooth or unbounded, which poses extra difficulty in
studying $\inf_{f\in\mathcal{F}_{CNN}}\|f-f^{\phi}_{0}\|$, as most of the
existing studies on the approximation properties of deep neural networks
assume smooth and bounded target functions. As shown in Table 1, the target
function $f^{\phi}_{0}$ for SVM is non-continuous; for the exponential and
logistic loss, their corresponding $f^{\phi}_{0}$ can be unbounded if
$\eta(x)$ can be arbitrarily close to 0 or 1 for some $x\in\mathcal{X}.$ If
the unboundedness problem cannot be solved satisfactorily, then even under
deterministic scenario, we have $f_{0}^{\phi}(x)\in\\{+\infty,-\infty\\}$ for
all $x\in\mathcal{X}$, which is nonsensical.

We overcome these difficulties by imposing mild and reasonable assumptions on
the conditional probability $\eta$ and the loss function $\phi$.

###### Assumption 2

  * (a)

The conditional probability $\eta(x)=\mathbb{P}\\{Y=1\mid X=x\\}$ is
continuous on the support of $\mathcal{X}=[0,1]^{d}$ and the probability
measure of $X$ is absolutely continuous with respect to the Lebesgue measure.

  * (b)

The loss function $\phi:\mathbb{R}\to[0,\infty)$ is continuously
differentiable on its support.

Under Assumptions 1-2, we consider truncating the target function
$f_{0}^{\phi}$ by a constant $T>0$, where $T$ may depend on $n$. Let
$f_{0,T}^{\phi}$ be the truncated target function $f_{0}^{\phi}$, i.e.,

$f_{0,T}^{\phi}(x)=\left\\{\begin{array}[]{lr}f_{0}^{\phi}(x),\ \text{ if
}|f_{0}^{\phi}(x)|\leq T,\\\ T,\ \ \ \ \ \ \,\text{ if
}|f_{0}^{\phi}(x)|>T.\end{array}\right.$ (13)

Let $\bar{\mathbb{R}}=\mathbb{R}\cup\\{+\infty,-\infty\\}$ be the extended
real line. Then, the approximation error can be decomposed into two terms that
are easier to deal with.

###### Theorem 7

Suppose that Assumptions 1-2 hold and $T\leq\mathcal{B}$. Then, the
$\phi$-approximation error
$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$ with respect
to the loss function $\phi$ satisfies

$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})\leq
B_{\phi}\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}|f(X)-f^{\phi}_{0,T}(X)|+\inf_{|a|\leq
T}\phi(a)-\inf_{a\in\bar{\mathbb{R}}}\phi(a),$

where $f_{0,T}^{\phi}$ is the truncated target function and is continuous on
$[0,1]^{d}$.

By Theorem 7, the $\phi$-approximation error
$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$ is bounded by
the sum of two terms:
$B_{\phi}\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}|f(X)-f^{\phi}_{0,T}(X)|$ and
$\Delta_{\phi}(T):=\inf_{|a|\leq
T}\phi(a)-\inf_{a\in\bar{\mathbb{R}}}\phi(a)$. We list the Lipschitz constant
$B_{\phi}$ and $\Delta_{\phi}(T)$ for several commonly-used $\phi$ loss
functions in Table 2.

Table 2: $\Delta_{\phi}(T)$, Lipschitz constant $B_{\phi}$ under different
loss functions $\phi$ restricted to $[-\mathcal{B},\mathcal{B}]$ for $0<1\leq
T\leq\mathcal{B}$, and modulus of continuity $\omega_{f^{\phi}_{0,T}}$ of the
truncated $f^{\phi}_{0}$.

| Least squares | SVM | Exponential | Logistic
---|---|---|---|---
$\phi(a)$ | $(1-a)^{2}$ | $\max\\{1-a,0\\}$ | $\exp(-a)$ | $\log\\{1+\exp(-a)\\}$
$f^{\phi}_{0}(x)$ | $2\eta-1$ | ${\rm sign}(2\eta-1)$ | $\frac{1}{2}\log(\frac{\eta}{1-\eta})$ | $\log(\frac{\eta}{1-\eta})$
$B_{\phi}$ | $2\mathcal{B}$ | 1 | $\exp(\mathcal{B})$ | $1/\\{\exp(-\mathcal{B})+1\\}$
$\Delta_{\phi}(T)$ | 0 | 0 | $\exp(-T)$ | $\log\\{1+\exp(-T)\\}$
$\omega_{f^{\phi}_{0,T}}$ | $2\omega_{\eta}$ | *** | $\\{\exp(T)+\exp(-T)\\}^{2}\frac{\omega_{\eta}}{2}$ | $\\{\exp(T/2)+\exp(-T/2)\\}^{2}{\omega_{\eta}}$

Note: $\eta(x)$ is written as $\eta$ for notational simplicity. ”***” stands
for no explicit form or not applicable.

It is worthwhile to note that the loss function $\phi$ of SVM does not satisfy
Assumption 2 part (b); but under Assumption 2 part (a), we can obtain a
minimizer $f_{0}^{\phi}$ that is a step function. To be specific, for the SVM
risk function, $f_{0}^{\phi}(x)$ can be defined as any value in $[-1,1]$ when
$\eta(x)=1/2$. Hence, we define $f_{0}^{\phi}(x)={\rm sign}(2\eta(x)-1)$ if
$\eta(x)\not=1/2$, otherwise define $f_{0}^{\phi}(x)=c$ for some $c\in[-1,1]$
such that $f_{0}^{\phi}$ is a step function on $[0,1]^{d}$.

By Theorem 7, the approximation error can be controlled by properly choosing
$T$ to bound $\Delta_{\phi}(T)$ and
$B_{\phi}\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}|f(X)-f^{\phi}_{0,T}(X)|$. For
the latter, we can apply existing approximation results of neural networks to
handle it. Based on the existing approximation theories, the upper bound of
$\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}|f(X)-f^{\phi}_{0,T}(X)|$ depends on
$\mathcal{F}_{CNN}$ through its parameters and related to $f^{\phi}_{0}$
through its modulus of continuity. The modulus of continuity $\omega_{f}$ of a
function $f:[0,1]^{d}\to\mathbb{R}$ is defined by

$\omega_{f}(r):=\sup\\{|f(x)-f(y)|:x,y\in[0,1]^{d},\|x-y\|_{2}\leq r\\},{\rm
for\ any\ }r\geq 0.$ (14)

For a uniformly continuous function $f$, $\lim_{r\to
0}\omega_{f}(r)=\omega_{f}(0)=0$. In addition, based on the modulus of
continuity, different equi-continuous families of functions can be defined.
For instance, the modulus $\omega_{f}(r)=Lr$ describes the $L$-Lipschitz
continuity; the modulus $\omega_{f}(r)=\lambda r^{\alpha}$ with
$\lambda,\alpha>0$ describes the Hölder continuity and so on.

In our classification problem, we can view
$f_{0}^{\phi}=g_{0}^{\phi}\circ\eta$ as a composition of a function
$g_{0}^{\phi}$ and the conditional probability function $\eta$ defined in (4).
For example, $g_{0}^{\phi}(\eta)=2\eta-1$ for the least squares loss;
$g_{0}^{\phi}(\eta)=\log\\{\eta/(1-\eta)\\}$ for the logistic loss;
$g_{0}^{\phi}(\eta)=\log(\eta/(1-\eta))/2$ for the exponential loss; and
$g_{0}^{\phi}(\eta)={\rm sign}(2\eta-1)$ for the SVM. For the composite
function $f_{0}^{\phi}=g_{0}^{\phi}\circ\eta$, its modulus of continuity is
given by $\omega_{f_{0}^{\phi}}=\omega_{g_{0}^{\phi}}\circ\omega_{\eta}$.
Moreover, the modulus of continuity of the truncated function $f^{\phi}_{0,T}$
is bounded by that of the target function $f^{\phi}_{0}$. The modulus of
continuity of $f^{\phi}_{0,T}$ for the least squares, the logistic, the
exponential, and the SVM are given in Table 2, which are a function of
$\omega_{\eta}$, the modulus of continuity of $\eta$. Assumptions 1-2 imply
that $f^{\phi}_{0,T}$ is uniformly continuous, the proof is included in the
proof of Theorem 7 in Appendix). Therefore, our results are expressed in terms
of the modulus of continuity of $f^{\phi}_{0,T}$.

##  4 Non-asymptotic error bounds

Theorems 6 and 7 provide the theoretical basis for establishing the
consistency and non-asymptotic excess risk bounds. In this section, we first
give an explicit upper bounds for the excess $\phi$-risk
$R^{\phi}(\hat{f}_{n})-R^{\phi}(f^{\phi}_{0})$ with a general loss function
$\phi$ satisfying Assumptions 1 and 2. We also show that classification with
CNN is able to circumvent the curse of dimensionality under an approximate
lower-dimensional manifold support assumption on the distribution of the input
data $X$.

###  4.1 Non-asymptotic excess risk bound

######  Theorem 8 (Non-asymptotic excess $\phi$-risk bound)

Suppose that Assumptions 1 and 2 hold. For any $M,N\in\mathbb{N}^{+}$, let
$\mathcal{F}_{CNN}$ be the class of CNNs defined in (11) with
$B_{a}\leq\max\\{M^{2}N^{2},2^{M+1}\\}$,
$f^{\phi}_{0,T}(\textbf{0})+\omega_{f^{\phi}_{0,T}}(\sqrt{d})\leq\mathcal{B}$,
depth $L\leq 12M+14$ and width $\mathcal{W}\leq\max\\{4d\lfloor
N^{\frac{1}{d}}\rfloor+3d,12N+8\\}$, where $\lfloor a\rfloor$ denotes the
largest integer strictly smaller than $a$. Then, for any $\delta\in(0,1)$,
with probability at least $1-\delta$, the ERM $\hat{f}^{\phi}_{n}$ defined in
(12) satisfies

$\displaystyle R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\text{EstError}+\text{AppError},$ (15)

where the estimation error

$\text{EstError}=16\sqrt{2}B_{\phi}\mathcal{B}\frac{\mathcal{S}^{1/2}L^{1/4}}{\sqrt{n}}+2B_{\phi}\mathcal{B}\frac{\sqrt{2\log(1/\delta)}}{\sqrt{n}},$

and the approximation error

$\text{AppError}=18\sqrt{d}B_{\phi}\omega_{f^{\phi}_{0,T}}(N^{-2/d}M^{-2/d})+\inf_{|a|\leq
T}\phi(a)-\inf_{a\in\bar{\mathbb{R}}}\phi(a).$

The upper bound of the excess $\phi$-risk
$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})$ in Theorem 8 is a sum of
two error terms, the estimation error and the approximation error. It is
worthwhile to note the following two aspects.

  * •

First, the error bound (15) is non-asymptotic and explicit in the sense that
no unclearly defined constant are involved. The prefactor $18\sqrt{d}B_{\phi}$
in the upper bound of approximation error (the first item in AppError) depends
on the dimension $d$ sub-linearly, different from the exponential dependence
in many existing neural network approximation results.

  * •

Second, the approximation rate $(NM)^{-2/d}$ is in terms of the width
$\mathcal{W}\leq\max\\{4d\lfloor N\rfloor^{1/d}+3d,12N+8\\}$ and depth $L\leq
12M+14$, rather than just the size $\mathcal{S}$ of the network. This offers
some insights into how the excess risk relates to the network structure.

To achieve the optimal error rate, we need to balance the trade-off between
the estimation error and the approximation error. On one hand, the bound for
the estimation error EstError increases with the size and the depth of
$\mathcal{F}_{CNN}.$ On the other hand, the bound for the approximation error
AppError decreases with the depth and the width of $\mathcal{F}_{CNN}.$
Notably, the choice of the bound $\mathcal{B}$ is also crucial to balance the
errors and achieve good rate of convergence. As a result, proper design of the
network architecture is of key importance to ensure good convergence rate of
the excess $\phi$-risk.

Theorem 8 immediately yields the following consistency result for the ERM
$\hat{f}^{\phi}_{n}.$

######  Theorem 9 (Consistency)

Suppose that Assumptions 1 and 2 hold. Let $\mathcal{F}_{CNN}$ be the function
class of CNNs defined in (11) with
$f^{\phi}_{0,T}(\textbf{0})+\omega_{f^{\phi}_{0,T}}(\sqrt{d})\leq\mathcal{B}.$
If

$\displaystyle\mathcal{S}\to\infty,\
\sqrt{d}B_{\phi}\omega_{f^{\phi}_{0,T}}(\mathcal{S}^{-2/d})\to 0,\
\frac{B^{\phi}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{\sqrt{n}}\to 0{\rm\ and\
}\inf_{|a|\leq T}\phi(a)-\inf_{a\in\bar{\mathbb{R}}}\phi(a)\to 0,$

as $n\to\infty$, then the ERM $\hat{f}^{\phi}_{n}$ w.r.t the loss $\phi$
defined in (12) and the 0-1 loss excess risk of $\hat{h}_{n}={\rm
sign}(\hat{f}^{\phi}_{n})$ satisfy

$\displaystyle R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\to
0{\rm\quad and\quad}R(\hat{h}_{n})-R_{0}\to 0$

in probability.

###  4.2 Circumventing the curse of dimensionality

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 even if there is a large sample size. This fact is known as the curse of
dimensionality. However, many types of data have a low-dimensional latent
structure, that is, although the ambient dimension $d$ is large, the
distribution of the data is approximately support on a low-dimensional subset
of $\mathbb{R}^{d}$ . Apparently, it is desirable to incorporate such a latent
structure in the theoretical analysis. In Theorem 7, the approximation error
$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$ is actually
defined with respect to the probability measure $\mathbb{P}$. In light of
this, a proper and realistic assumption on the support of $X$ can help lessen
the curse of dimensionality. Although $f^{\phi}_{0}$ is fixed and its domain
is high dimensional, when the support of $X$ is concentrated on a neighborhood
of a low-dimensional manifold, the upper bound of the approximation error can
be substantially improved in terms of the exponent of the convergence rate
(Shen et al., 2020).

###### Assumption 3

The covariate $X$ is supported on $\mathcal{M}_{\rho}$, a $\rho$-neighborhood
of $\mathcal{M}\subset[0,1]^{d}$, where $\mathcal{M}$ is a compact
$d_{\mathcal{M}}$-dimensional Riemannian submanifold and
$\mathcal{M}_{\rho}=\\{x\in[0,1]^{d}:\inf\\{\|x-y\|_{2}:y\in\mathcal{M}\\}\leq\rho\\}$
for $\rho\in(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 of a
latent part supported on a low-dimensional manifold $\mathcal{M}$ plus noises.
Therefore, Assumption 3 is more reasonable compared with the exact manifold
assumption assumed in Schmidt-Hieber (2019); Nakada and Imaizumi (2019); Chen
et al. (2019a).

Before stating the main theorem in this subsection, we first present a result
on the approximation power of CNNs under an approximate low-dimensional
manifold support assumption. This result is of independent interest and can be
useful in other problems that involve the use of CNNs. Let $f^{\phi}_{0,T}$ be
defined as in (13).

###### Lemma 10

Suppose that Assumptions 1-3 hold.  For any $M,N\in\mathbb{N}^{+}$, let
$\mathcal{F}_{CNN}$ be the class of CNNs defined in (11) with
$B_{a}\leq\max\\{M^{2}N^{2},2^{M+1}\\}$,
$f^{\phi}_{0,T}(\textbf{0})+\omega_{f^{\phi}_{0,T}}(\sqrt{d})\leq\mathcal{B}$,
depth $L\leq 12M+14$ and  width $\mathcal{W}\leq\max\\{4d_{\varepsilon}\lfloor
N^{\frac{1}{d_{\varepsilon}}}\rfloor+3d_{\varepsilon},12N+8\\}$, where
$d_{\varepsilon}=O(d_{\mathcal{M}}\frac{\log(d/\varepsilon)}{\varepsilon^{2}})$
for $\varepsilon\in(0,1).$ Suppose the radius of the neighborhood $\rho$ in
Assumption 3 satisfies $\rho\leq
N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}(1-\varepsilon)/\\{2(\sqrt{d/d_{\varepsilon}}+1-\varepsilon)\\}.$
Then, we have

$\inf_{f\in\mathcal{F}_{\text{CNN}}}\mathbb{E}|f(X)-f^{\phi}_{0,T}(X)|\leq(18\sqrt{d_{\varepsilon}}+2)\omega_{f^{\phi}_{0,T}}(N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}).$

The following theorem provides a non-asymptotic excess risk bound under the
approximate low-dimensional manifold assumption.

######  Theorem 11 (Circumventing the curse of dimensionality)

Suppose that Assumptions 1-3 hold.  For any $M,N\in\mathbb{N}^{+}$, let
$\mathcal{F}_{CNN}$ be the class of CNNs defined in (11) with
$B_{a}\leq\max\\{M^{2}N^{2},2^{M+1}\\}$,
$f^{\phi}_{0,T}(\textbf{0})+\omega_{f^{\phi}_{0,T}}(\sqrt{d})\leq\mathcal{B}$,
depth $L\leq 12M+14$ and  width $\mathcal{W}\leq\max\\{4d_{\varepsilon}\lfloor
N^{\frac{1}{d_{\varepsilon}}}\rfloor+3d_{\varepsilon},12N+8\\}$, where
$d_{\varepsilon}=O(d_{\mathcal{M}}\frac{\log(d/\varepsilon)}{\varepsilon^{2}})$
for $\varepsilon\in(0,1).$ Suppose the radius of the neighborhood $\rho$ in
Assumption 3 satisfies $\rho\leq
N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}(1-\varepsilon)/\\{2(\sqrt{d/d_{\varepsilon}}+1-\varepsilon)\\}.$
Then for any $\delta\in(0,1)$, with probability at least $1-\delta$, the ERM
$\hat{f}^{\phi}_{n}$ defined in (12) satisfies

$\displaystyle R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\text{EstError}_{*}+\text{AppError}_{*},$ (16)

where the estimation error

$\text{EstError}_{*}=16\sqrt{2}B_{\phi}\mathcal{B}\frac{\mathcal{S}^{1/2}L^{1/4}}{\sqrt{n}}+2B_{\phi}\mathcal{B}\frac{\sqrt{2\log(1/\delta)}}{\sqrt{n}},$

and the approximation error

$\text{AppError}_{*}=(18\sqrt{d_{\varepsilon}}+2)B_{\phi}\omega_{f^{\phi}_{0,T}}(N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}})+\inf_{|a|\leq
T}\phi(a)-\inf_{a\in\bar{\mathbb{R}}}\phi(a).$

For a high-dimensional input $X$ with a large $d$,
$d_{\varepsilon}=O(d_{\mathcal{M}}{\log(d/\varepsilon)}/{\varepsilon^{2}})$
satisfies $d_{\mathcal{M}}$$\leq d_{\varepsilon}<d$ for $\varepsilon\in(0,1)$.
Comparing with the bound (15) in Theorem 8, we see that
$\textit{EstError}_{*}=\textit{EstError}$, that is, the estimation error does
not change under the approximate low-dimensional manifold assumption. The
change is in the approximation error term $\textit{AppError}_{*}$. Comparing
with AppError in (15) of Theorem 8, we see that it only depends on
$d_{\varepsilon},$ which leads to a much faster convergence rate. Therefore,
Theorem 11 significantly improves the error bound in comparison with the error
bound in Theorem 8 without any assumption on the support of $X$. Theorem 11
shows that classification with CNNs can circumvent the curse of dimensionality
if the input data $X$ is supported on an approximate low-dimensional manifold.

##  5 Examples

In this section, we illustrate the applications of Theorems 8 and 11 to
obtaining convergence rates of excess risk in classification. We apply the
general excess risk bounds established in these theorems to several important
classification methods with CNNs in details when the specific form of $\phi$
is given, including those with the least squares, the logistic, the
exponential, and the SVM losses.

We make mild assumptions on the modulus of continuity of the condition
probability function $\eta$ defined in (4), i.e., there exist $\lambda\geq 0$
and $\alpha>0$ such that $|\eta(x)-\eta(y)|\leq\lambda\|x-y\|_{2}^{\alpha}$
for any $x,y\in\mathcal{X}\subset[0,1]^{d}$. With the Hölder-continuity
assumption on $\eta$, its modulus of continuity $\omega_{\eta}(r)=\lambda
r^{\alpha}$ based on its definition (14). Typically, as in many machine
leaning tasks, we assume the input dimension $d\gg\alpha$ by default. For the
examples given below, the network is chosen to be fixed-width networks, thus
the optimal convergence rate can be achieved with the minimal size (number of
parameters) due to the fact that the network size must satisfy
$\mathcal{S}\leq\mathcal{W}^{2}L$. A detailed discussion on this point can be
found in Jiao et al. (2021).

###  5.1 Example 1: Least squares

For the least squares loss $\phi(a)=(1-a)^{2}$, the approximation error

$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})=\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}|f(X)-f^{\phi}_{0}(X)|^{2}.$

Let $\mathcal{F}_{CNN}$ be the class of CNNs defined in (11) with $1+2\lambda
d^{\alpha/2}\leq\mathcal{B}$, with the number of layers $L\leq 12\lfloor
n^{d/2(d+2\alpha)}\rfloor+14$, width $\mathcal{W}\leq\max\\{7d,20\\}$ and size
(number of parameters)
$\mathcal{S}\leq\mathcal{W}^{2}L\leq\max\\{49d^{2},400\\}\times\\{\lfloor
n^{d/2(d+2\alpha)}\rfloor+14\\}.$ Suppose that Assumptions 1 and 2 hold.
Theorem 8 implies that, with probability at least
$1-\exp\\{-n^{(d-2\alpha)/(d+2\alpha)}\\}$, the excess $\phi$-risk of the ERM
$\hat{f}^{\phi}_{n}$ defined in (12) satisfies

$\displaystyle R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\Big{\\{}(32\sqrt{2}c+4\sqrt{2})\mathcal{B}^{2}+4\cdot
18^{2}\lambda^{2}d\mathcal{B}(\max\\{7d,20\\})^{-\frac{4\alpha}{d}}\Big{\\}}n^{-\frac{2\alpha}{(d+2\alpha)}},$
(17)

where $c=O(d)$ is a constant independent of $n,\mathcal{B},\alpha$ and
$\lambda$. Alternatively, (17) can be simply written as

$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq
C(d)n^{-\frac{2\alpha}{(d+2\alpha)}}$

for some constant $C(d)=O(d(4\lambda^{2}d^{\alpha}+1))$ independent of
$n,\mathcal{B}$. Here, the convergence rate achieves the optimal minimax rate
in Stone (1982); more importantly, the prefactor $C(d)$ depends on the
dimension $d$ at a rate no more than $O(d^{1+\alpha})$, which is much improved
than the exponential dependence $O(2^{d})$ in the existing works.

In addition, suppose the approximate low-dimensional manifold Assumption 3
also holds and for any $\varepsilon\in(0,1),$ the radius of the neighborhood
$\rho$ in Assumption 3 satisfies $\rho\leq
N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}(1-\varepsilon)/\\{2(\sqrt{d/d_{\varepsilon}}+1-\varepsilon)\\},$
where
$d_{\varepsilon}=O(d_{\mathcal{M}}{\log(d/\varepsilon)}/{\varepsilon^{2}})$ is
an integer satisfying $d_{\mathcal{M}}$$\leq d_{\varepsilon}\ll d.$ Then by
Theorem 11, the rate of convergence can be improved to

$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq
C(d_{\varepsilon})n^{-\frac{2\alpha}{(d_{\varepsilon}+2\alpha)}},$

for some constant
$C(d_{\varepsilon})=O(d_{\varepsilon}(4\lambda^{2}d_{\varepsilon}^{\alpha}+1))$
independent of $n$ and $\mathcal{B}$. Again, here the prefactor depends on $d$
at most polynomially.

###  5.2 Example 2: Logistic loss

For the logistic loss function $\phi(a)=\log\\{1+\exp(-a)\\}$, the bound of
excess risk is not tight enough, as the minimizer of $\phi$-risk
$\log\\{{\eta(x)}/{1-\eta(x)}\\}$ is unbounded with the modulus of continuity
of truncated $f^{\phi}_{0,T}$ being
$\\{\exp(T/2)+\exp(-T/2)\\}^{2}{\omega_{\eta}}$ and the error due to the
truncation $\Delta_{\phi}(T)=\log\\{1+\exp(-T)\\}$. This requires a suitable
choice of $T$ to control the two items simultaneously. A feasible choice is
$T=O(\log\log(n))$ where $n$ is the sample size.

Let $\mathcal{F}_{CNN}$ be the class of CNNs defined in (11). With a suitable
number of layers, width and size, it holds that with high probability, the
excess $\phi$-risk of the ERM $\hat{f}^{\phi}_{n}$ defined in (12) satisfies
$R^{\phi}(\hat{f}_{n})-R^{\phi}(f_{0}^{\phi})\leq C/\log(n)$ for some constant
$C>0$ not depending on $n$.

A practical way to improve the rate of convergence is to use a modified
logistic loss function, i.e. $\phi(a)=\max\\{\log\\{1+\exp(-a)\\},\tau\\}$ for
some small $\tau>0$. With the modified logistic loss, the minimum of $\phi$
can be achieved at a finite number $a^{*}(\tau)=-\log\\{\exp(\tau)-1\\}$, and
the minimizer $f^{\phi}_{0}(x)$ will be a truncated version of
$\log[\eta(x)/\\{1-\eta(x)\\}]$ (truncated by
$a^{*}(\tau)=-\log\\{\exp(\tau)-1\\}$). In light of this, under the modified
logistic loss with $\tau=\log\\{1+\exp(-T)\\}$, the corresponding measurable
minimizer defined in (6) is $f^{\phi}_{0,T}$, the truncated version of the
minimizer $f_{0}^{\phi}$ under the original logistic loss; see Table 2. As a
consequence, under the modified logistic loss, $\Delta_{\phi}(T)=0$ by
definition since the infimum of the modified logistic loss can be achieved
within $[-T,T]$. Note that

Suppose Assumptions 1 and 2 hold. Let $\mathcal{F}_{CNN}$ be the class of CNNs
defined in (11) with
$\min(|\log[\eta(\textbf{0})/\\{1-\eta(\textbf{0})\\}]|,T\\}+4\exp(T)\lambda
d^{\alpha/2}\leq\mathcal{B}$, the number of layers $L\leq 12\lfloor
n^{2d/(3d+8\alpha)}\rfloor+14$, width $\mathcal{W}\leq\max\\{7d,20\\}$ and
size $\mathcal{S}\leq\mathcal{W}^{2}L\leq\max\\{49d^{2},400\\}\times(\lfloor
n^{2d/(3d+8\alpha)}\rfloor+14)$.

Theorem 8 implies that, with probability at least
$1-\exp\\{-n^{d/(d+8\alpha/3)}\\}$, the excess $\phi$-risk of the ERM
$\hat{f}^{\phi}_{n}$ defined in (12) satisfies

$\displaystyle R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\Big{\\{}(16\sqrt{2}c+2\sqrt{2})\mathcal{B}+72\lambda\exp(T)\sqrt{d}(\max\\{7d,20\\})^{-\frac{2\alpha}{d}}\Big{\\}}n^{-\frac{\alpha}{0.75d+2\alpha}},$
(18)

where $c$ is a constant independent of $n,\mathcal{B},\alpha,\lambda$, and $c$
is independent of $d$ if $d\leq 2$ otherwise $c=O(d)$. Alternatively, (18) can
be simply written as

$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq
C(T,d)n^{-\frac{\alpha}{0.75d+2\alpha}},$

where $C(T,d)=O(d(1+4\lambda d^{\alpha/2})\exp(T))$ is a constant independent
of $n,\mathcal{B}$. Here the prefactor $C(T,d)$ depends on the dimension $d$
at a rate no more than $O(d^{\alpha/2+1})$.

In addition, suppose the approximate low-dimensional manifold Assumption 3
also holds and for any $\varepsilon\in(0,1),$ the radius of the neighborhood
$\rho$ in Assumption 3 satisfies $\rho\leq
N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}(1-\varepsilon)/\\{2(\sqrt{d/d_{\varepsilon}}+1-\varepsilon)\\},$
where
$d_{\varepsilon}=O(d_{\mathcal{M}}{\log(d/\varepsilon)}/{\varepsilon^{2}})$ is
an integer satisfying $d_{\mathcal{M}}$$\leq d_{\varepsilon}\ll d.$ Then
Theorem 11 shows that the rate of convergence can be improved to

$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq
C(T,d_{\varepsilon})n^{-\frac{\alpha}{0.75d_{\varepsilon}+2\alpha}},$

where $C(T,d_{\varepsilon})=O(d_{\varepsilon}(1+4\lambda
d_{\varepsilon}^{\alpha/2})\exp(T))$ is a constant independent of $n$ and
$\mathcal{B}$.

###  5.3 Example 3: Exponential loss

For the exponential loss function $\phi(a)=\exp(-a)$, the upper bound of the
excess risk suffers from the same problem as the logistic loss, as the
minimizer of the $\phi$-risk $\log\\{{\eta(x)}/{1-\eta(x)}\\}/2$ is unbounded.
Furthermore, for the exponential loss, the Lipschitz constant and the modulus
of continuity grows exponentially fast as $T$ grows, which makes it harder to
balance $B_{\phi}$, $\omega_{f^{\phi}_{0,T}}$ and $\Delta_{\phi}(T)$. Similar
to the logistic loss, we consider a modified exponential loss function
$\phi(a)=\max\\{\exp(-a),\tau\\}$ for some small $\tau>0$, which results in a
bounded measurable minimizer $f^{\phi}_{0}(x)$. Under modified exponential
loss with $\tau=\exp(-T)$, its corresponding measurable minimizer defined in
(6) is $f^{\phi}_{0,T}$, the truncated version of the minimizer $f^{\phi}_{0}$
under the original exponential loss; see Table 2. Also, under modified
exponential loss, $\Delta_{\phi}(T)=0$ by definition.

Suppose Assumptions 1 and 2 hold. Let $\mathcal{F}_{CNN}$ be the class of CNNs
defined in (11) with
$\min(|\log[\eta(\textbf{0})/\\{1-\eta(\textbf{0})\\}]|/2,T\\}+2\exp(2T)\lambda
d^{\alpha/2}\leq\mathcal{B}$, the number of layers $L\leq 12\lfloor
n^{2d/(3d+8\alpha)}\rfloor+14$, width $\mathcal{W}\leq\max\\{7d,20\\}$ and
size $\mathcal{S}\leq\mathcal{W}^{2}L\leq\max\\{49d^{2},400\\}\times(\lfloor
n^{2d/(3d+8\alpha)}\rfloor+14).$ Theorem 8 implies that, with probability at
least $1-\exp\\{-n^{d/(d+8\alpha/3)}\\},$ the excess $\phi$-risk of the ERM
$\hat{f}^{\phi}_{n}$ defined in (12) satisfies

$\displaystyle R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\Big{\\{}(16\sqrt{2}c+2\sqrt{2})\mathcal{B}\exp(\mathcal{B})+36\lambda\exp(2T+\mathcal{B})\sqrt{d}(\max\\{7d,20\\})^{-2\alpha/d}\Big{\\}}$
$\displaystyle\hskip 170.71652pt\times n^{-\alpha/(0.75d+2\alpha)},$ (19)

where $c$ is a constant independent of $n,\mathcal{B},\alpha$ and $\lambda$,
and is independent of $d$ if $d\leq 2$ otherwise $c=O(d)$. Alternatively,
(5.3) can be recast as

$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq
C(T,d)n^{-\alpha/(0.75d+2\alpha)},$

where $C(T,d)=O(d(1+2\lambda d^{\alpha/2})\exp(2T)\exp\\{3\exp(2T)(1+2\lambda
d^{\alpha/2})\\})$ is a constant independent of $n$ and $\mathcal{B}$. Here
the prefactor $C(T,d)=O(d^{\alpha/2+1}\exp(d^{\alpha/2}))$ depends on the
dimension $d$ exponentially.

In addition, suppose the approximate low-dimensional manifold Assumption 3
also holds and for any $\varepsilon\in(0,1),$ the radius of the neighborhood
$\rho$ in Assumption 3 satisfies $\rho\leq
N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}(1-\varepsilon)/\\{2(\sqrt{d/d_{\varepsilon}}+1-\varepsilon)\\},$
where
$d_{\varepsilon}=O(d_{\mathcal{M}}{\log(d/\varepsilon)}/{\varepsilon^{2}})$ is
an integer satisfying $d_{\mathcal{M}}$$\leq d_{\varepsilon}\ll d.$ Then
Theorem 11 shows that the rate of convergence can be improved to

$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq
C(T,d_{\varepsilon})n^{-\alpha/(0.75d_{\varepsilon}+2\alpha)},$

where $C(T,d_{\varepsilon})=O(d_{\varepsilon}(1+2\lambda
d_{\varepsilon}^{\alpha/2})\exp(2T)\exp\\{3\exp(2T)(1+2\lambda
d_{\varepsilon}^{\alpha/2})\\})$ is a constant independent of $n$ and
$\mathcal{B}$.

###  5.4 Example 4: SVM

For the support vector machine (SVM), the loss function
$\phi(a)=\max\\{1-a,0\\}$ is not differentiable at $a=1$ and thus the
$\phi$-risk minimizer $f_{0}^{\phi}(x)={\rm sign}(2\eta(x)-1)$ may not be
continuous even though $\eta$ is continuous, as $f_{0}^{\phi}(x)$ is
discontinuous when $\eta(x)=1/2$. To tackle this problem, we additionally
impose the low noise condition on $\eta$ (Mammen and Tsybakov (1999); Tsybakov
(2004)), i.e. there exist $c_{\text{noise}}>0$ and $q\in[0,\infty]$ such that
for any $t>0$,

$\mathbb{P}(|2\eta(X)-1|\leq t)\leq c_{\text{noise}}t^{q},$

where the constant $q$ is called the noise exponent.

Suppose Assumptions 1 and 2 hold. Let $\mathcal{F}_{CNN}$ be the class of CNNs
defined in (11) with $\mathcal{B}\geq 1$ with the number of layers $L\leq
12\lfloor n^{2d/\\{3d+8\alpha(q+1)\\}}\rfloor+15$, width
$\mathcal{W}\leq\max\\{7d,20\\}$ and size (number of parameters)
$\mathcal{S}\leq\mathcal{W}^{2}L\leq\max\\{49d^{2},400\\}\times[\lfloor
n^{2d/\\{3d+8\alpha(q+1)\\}}\rfloor+15]$. Theorem 11 implies that, with
probability at least $1-\exp[-n^{3d/\\{3d+8\alpha(q+1)\\}}]$, the excess
$\phi$-risk of the ERM $\hat{f}^{\phi}_{n}$ defined in (12) satisfies

$\displaystyle R^{\phi}(\hat{f}_{n})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\Big{\\{}16\sqrt{2}c+2\sqrt{2}+144\times 4^{q}\lambda
c_{noise}\sqrt{d}(\max\\{7d,20\\})^{-\frac{2\alpha}{d}}\Big{\\}}n^{-\frac{4\alpha(q+1)}{3d+8\alpha(q+1)}},$

where $c$ is a constant independent of $n,\mathcal{B},\alpha$ and $\lambda$,
and is independent of $d$ if $d\leq 2$ otherwise $c=O(d)$, or simply

$R^{\phi}(\hat{f}_{n})-R^{\phi}(f_{0}^{\phi})\leq
C(d)n^{-4\alpha(q+1)/\\{3d+8\alpha(q+1)\\}},$

where $C(d)$ is a constant independent of $n,\mathcal{B}$ and $\alpha$, and
$C(d)=O(\sqrt{d})$ if $d\leq 2$ otherwise $C=O(d)$. We note that the excess
risk bound depends on $q$, the noise exponent.  When $q=0$ (high noise), the
convergence rate with respect to the sample size is
$n^{-\alpha/(0.75d+2\alpha)}$, which is exactly the same as Modified Logistic
or exponential examples; When $q=+\infty$ (no noise), the rate will be
significantly improved to $n^{-1/2}$. A similar result can be found in Theorem
3.3 of Kim et al. (2021).

In addition, suppose the approximate low-dimensional manifold Assumption 3
also holds and for any $\varepsilon\in(0,1),$ the radius of the neighborhood
$\rho$ in Assumption 3 satisfies $\rho\leq
N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}(1-\varepsilon)/\\{2(\sqrt{d/d_{\varepsilon}}+1-\varepsilon)\\},$
where
$d_{\varepsilon}=O(d_{\mathcal{M}}{\log(d/\varepsilon)}/{\varepsilon^{2}})$ is
an integer satisfying $d_{\mathcal{M}}$$\leq d_{\varepsilon}\ll d.$ Then
Theorem 11 shows the rate of convergence can be improved to

$R^{\phi}(\hat{f}_{n})-R^{\phi}(f_{0}^{\phi})\leq
C\sqrt{d_{\varepsilon}}n^{-4\alpha(q+1)/\\{3d_{\varepsilon}+8\alpha(q+1)\\}}.$

The proofs for the above four examples are deferred to Appendix.  It is
interesting to note that the excess bounds are different for different loss
functions. First, the exponents in the risk bounds depend on the
dimensionality $d$ differently. For least squares, the approximation error is
of a special form
$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})=\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}|f(X)-f^{\phi}_{0}(X)|^{2},$
which leads to an improved exponent $n^{-2\alpha/(d+2\alpha)}$ rather than
$n^{-2\alpha/(1.5d+4\alpha)}$ of the modified logistic or the exponential
loss. Due to the low noise condition, the exponent of SVM risk bound
$n^{-4\alpha(q+1)/\\{3d+8\alpha(q+1)\\}}$ is even more special, the worst case
is $n^{-2\alpha/(1.5d+4\alpha)}$ when $q=0$ (high noise) and achieves the best
possible rate $n^{-1/2}$ when $q=+\infty$ (no noise). Second the prefactors
are also different for different loss functions. For least squares, its
prefactor depends on the dimension $d$ by $O(d^{\alpha+1})$; for modified
logistic, it is $O(d^{\alpha+1})$; for exponential loss (even modified), the
dependence could be exponential type $O(d^{\alpha/2+1}\exp(d^{\alpha/2}))$;
and for SVM the dependence is at most $O(d)$. These differences mainly come
from the differences of Lipschitz constants of these loss functions on bounded
intervals. On bounded interval $[-\mathcal{B},\mathcal{B}]$, the Lipschitz
constants is $\mathcal{B}^{2}$ for the least squares loss; for modified
logistic and exponential loss, it is $\exp(\mathcal{B})$; and for the SVM, the
prefactor of the generalization rate does not depends on $\mathcal{B}$, since
the SVM loss function is piecewise constant.

##  6 Related works

Binary classification is a basic and important problem in machine learning and
statistics. There is a vast literature on this problem and many methods have
been developed in the literature, including the logistic regression (Cox,
1958; Kleinbaum et al., 2002), the probit model (Amemiya, 1978), the decision
tree (Safavian and Landgrebe, 1991), the support vector machine (Cortes and
Vapnik, 1995), the $\psi$-learning (Shen et al., 2003; Liu and Shen, 2006),
and the random forests (Breiman, 2001), among others. When the inputs are
assumed to be uniformly distributed on the surface of a sphere, Kalai et al.
(2008) derived non-asymptotic bounds for efficient binary prediction with half
spaces by minimizing the misclassification error rate directly. Under the
assumption that the conditional distribution of the label $Y$ given the input
$X$ is monotonic in $w^{\top}X$ for some $w\in\mathbb{R}^{d}$, Kalai and
Sastry (2009) provided an numerical efficient algorithm for minimizing the
misclassification error. The convergence properties of the excess risk of the
ERM for the misclassification 0-1 loss have been studied extensively under
various conditions (Tsybakov, 2004; Massart and Élodie Nédélec, 2006; Bartlett
and Mendelson, 2006; Blumer et al., 1989; Zhivotovskiy and Hanneke, 2018; Ben-
David and Urner, 2014; Kääriäinen, 2006).  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. However,
these earlier works did not consider the excess risk of classification using
CNNs. We refer to Boucheron et al. (2005) for an excellent review on the
theoretical results for classification.

###  6.1 Approximation power of CNNs

There have been intensive efforts devoted to understanding the theoretical
properties of deep neural networks in recent years. Many remarkable results
have been obtained concerning the approximation power of deep neural networks
for multivariate functions; some examples of important recent works include
Yarotsky (2017, 2018); Lu et al. (2017); Raghu et al. (2017); Shen et al.
(2019, 2020); Nakada and Imaizumi (2019); Chen et al. (2019b).  These works
focused on the approximation power for ReLU activated feedforward neural
networks, but did not consider the special structures of CNNs.

The approximation power of CNNs has been studied by several authors, see, for
example, Bao et al. (2014); Zhou and Feng (2018); Oono and Suzuki (2019); Zhou
(2020a) and Zhou (2020b). Universality of approximation by ReLU activated deep
CNNs was established in Zhou (2020b) for target functions restricted to
Sobolev space $H^{\alpha}(\mathbb{R}^{d})$ with $\alpha>2+d/2$, i.e. the
target function $f$ and all its partial derivatives up to order $\alpha$ are
square integrable on $\mathbb{R}^{d}$. The approximation error satisfies
$\|f-f_{FCNN}\|_{\infty}\leq C\sqrt{\log(L)}L^{-1/2-1/d}$, where $c$ is an
absolute constant depending on the Sobolev norm of $f$ and $f_{FCNN}$ is a
$L$-layer fully convolutional neural network. Approximation power of
downsampled convolutional neural networks on a special class of functions
(ridge function) was studied by Zhou (2020a), where the target function is
assumed to be of the form $f(x)=g(\xi^{\top}x)$, $g$ is a univariate Hölder
continuous function of order $\alpha$, $\xi\in\mathbb{R}^{d}$ satisfying
$\|\xi\|_{2}\leq 1$. The downsampling operators (the same as a pooling
operator) are applied between layers, who takes input from the previous layer
and outputs a subvector of the input vector. The approximate rate is shown to
be $\|f-f_{DCNN}\|_{\infty}\leq cN^{-\alpha}$, where $f_{DCNN}$ is a
downsampled convolutional neural network with uniform filter length
$s=O(4N+6)$ and width $\mathcal{W}=O(N)$. Further, it was also proved that a
downsampled CNN $f_{DCNN}$ can compute the same function as a MLP $f_{MLP}$
does, with the total number of free parameters of $f_{DCNN}$ being at most 8
times of that of the $f_{MLP}$. However, this cannot fully explain the
approximation advantage of CNN over MLP.

Note that the CNNs defined in these works are different from ours in terms of
the convolutional operation. In the CNNs considered by Zhou and Feng (2018);
Fang et al. (2020); Zhou (2020a) and Zhou (2020b), each convolutional layer
has only one filter with size $s$ and the induced weight matrix is of a
special Toeplitz type with shape $(d_{in}+s)\times d_{in}$ and no fully-
connected layer is allowed in hidden layers. Such a framework may not be
general enough to cover the CNNs that have been successfully applied in modern
machine learning tasks.

For general CNNs as considered in this work, Bao et al. (2014) studied the
approximation power of the composited CNN $f_{CNN}=H\circ f_{FCNN}$, where $H$
is a fully-connected layer and $f_{FCNN}$ is a $L$-layer fully convolutional
neural network. They proved that the composited CNN $f_{CNN}$ has similar
approximation power as an MLP for a certain class of functions in the sense
that, to achieve approximation accuracy $\epsilon$, the numbers of parameters
needed for $f_{CNN}$ and MLP have the same order in terms of $\epsilon$. Oono
and Suzuki (2019) showed the approximation power of ResNet-type convolutional
neural networks are at least as good as MLPs with its number of parameters
having the same order.

###  6.2 Error bounds in regression and classification

Several stimulating papers have studied the statistical convergence properties
of least squares estimators using feedforward neural networks in the context
of nonparametric regression (Bauer and Kohler, 2019; Schmidt-Hieber, 2020;
Chen et al., 2019a; Kohler et al., 2019; Nakada and Imaizumi, 2019; Farrell et
al., 2021; Jiao et al., 2021). They showed that nonparametric regression using
feedforward neural networks with a polynomial-growing network width
$\mathcal{W}=O(d^{\beta})$ achieves the optimal rate of convergence (Stone,
1982) up to a $\log n$ factor, however, with a prefactor $C_{d}=O(a^{d})$ for
some $a\geq 2$ that grows exponentially with the dimensionality $d$, unless
the network width $\mathcal{W}=O(a^{d})$ and size $\mathcal{S}=O(a^{d})$ grow
exponentially as $d$ grows. For a general review on generalization and uniform
convergence of deep learning models, see Bartlett et al. (2021).

When the inputs are assumed to be uniformly distributed on the surface of a
sphere, Kalai et al. (2008) derived non-asymptotic bounds for efficient binary
prediction with half spaces by minimizing the misclassification error rate
directly. Kim et al. (2021) studied the excess risk of empirical risk
minimizer for classification under the hinge loss (SVM) using deep neural
networks. They aimed to establish the convergence rate under the Tsybakov
noise condition (Mammen and Tsybakov, 1999; Tsybakov, 2004) in three different
cases: smooth decision boundary, smooth conditional class probability $\eta$
and margin conditions.  However, Kim et al. (2021) focused on the use of deep
feedforward neural networks, instead of deep CNNs, and placed restrictions on
the shapes of the networks where the network is only allowed to have $O(\log
n)$ depth and $O(n^{\nu})$ width for some $\nu>0$. Their convergence rate
results did not clearly describe the prefactors in the error bounds and they
also did not address the conditions for circumventing the curse of
dimensionality.

There are numerous studies on the convergence rate of excess misclassification
0-1 risk for binary classifications, see, e.g., Vapnik and Chervonenkis
(1974); Talagrand (1994); Boucheron et al. (2005); Tsybakov (2004); Massart
and Élodie Nédélec (2006); Bartlett and Mendelson (2006). For the well-
specified case assuming that the Bayes classifier $h_{0}$ belongs to the
hypothesis class $\mathcal{H}$ with a finite VC dimension $d_{VC}$, the
convergence rate of excess risk (stochastic error) for ERM can achieve the
best possible $O(\sqrt{d_{VC}/n})$ without any specific assumptions on
$\mathcal{H}$ or on the distribution of the data (Vapnik and Chervonenkis,
1974; Talagrand, 1994; Boucheron et al., 2005). If one further assumes the
relationship between the predictor and the label is deterministic, Vapnik and
Chervonenkis (1974); Blumer et al. (1989) showed that the optimal rate is
$O(d_{VC}/n)$ up to a logarithmic factor and it can be achieved by the ERM.
Later, for the well-specified case, Massart and Élodie Nédélec (2006) proposed
the bounded noise or Massart’s margin condition where $|2\eta-1|$ is bounded
away from 0, i.e $|2\eta-1|\geq\xi$ for some $\xi>0$, and it is shown that the
expected excess risk (stochastic error) of ERM is upper bounded by
$O(d_{VC}\log(n\xi^{2}/d_{VC})/(n\xi))$ and the lower bound can be found in
Massart and Élodie Nédélec (2006); Zhivotovskiy and Hanneke (2018). Also, for
the well-specified case, Mammen and Tsybakov (1999); Tsybakov (2004) proposed
the Tsybakov noise condition, i.e., there exist $c_{\text{noise}}>0$ and
$q\in[0,\infty]$ such that for any $t>0$, $\mathbb{P}(|2\eta(X)-1|\leq t)\leq
c_{\text{noise}}t^{q}.$ Under Tsybakov noise condition, Tsybakov (2004) showed
that the minimax lower bound is
$O(n^{-\beta(q+1)/\\{\beta(q+2)+(d-1)(q+1)\\}})$ over all smooth Bayes
classifiers, where their decision boundaries are generated by finite many
$\beta$-Hölder smooth functions. Still under the Tsybakov noise condition,
Audibert et al. (2007) showed that the minimax lower bound of the excess risk
is $O(n^{-\alpha(q+1)/\\{\alpha(q+2)+d\\}})$ when $\eta$ belongs to the class
of $\alpha$-Hölder smooth functions. For the agnostic or misspecified case
that the Bayes classifier $h_{0}$ does not belong to the hypothesis class
$\mathcal{H}$, Ben-David and Urner (2014) further assumed a deterministic
scenario and proved a faster excess rate $O(d_{VC}/n)$ up to logarithm factors
under the condition of the finite combinatorial diameter $D$ on $\mathcal{H}$
($D(\mathcal{H})=\sup_{h,h^{\prime}\in\mathcal{H}}|\\{x:h(x)\not=h^{\prime}(x)\\}|$).
But, in this case the ERM may suffer a slow rate and thus is not optimal.
Kääriäinen (2006) later showed that for the misspecified case, as long as the
diameter $D$ is infinite, any estimator (including ERM) may have the slow rate
$O(1/\sqrt{n})$. Bousquet and Zhivotovskiy (2019) considered a specific
learning algorithm with a reject option, namely Chow’s reject option model,
and they showed that it can achieve a faster rate $O(D/(n\xi))$ up to
logarithm factors with the bounded noise condition $\xi$ and finite class
diameter $D$ of $\mathcal{H}$.

For the relationship between the error bounds of regression and binary
classification, Yang (1999) studied the gap between minimax estimation of the
conditional probability $\eta$ and the direct minimax estimation of the Bayes
classifier $h_{0}$. For any estimator $\hat{\eta}$ of the true conditional
probability, one can use the “plug-in” rules to induce a classifier
$\hat{h}={\rm sign}(2\hat{\eta}-1)$, and an upper bound on the $L_{2}$ risk
for estimating $\eta$ gives an upper bound on the excess misclassification
risk for classification(estimating $h_{0}$). He showed that the two problems
are in fact of the same difficulty in terms of rates of convergence under a
sufficient condition, which is satisfied when $\eta$ belongs to some function
classes, including Besov (Sobolev), Lipschitz, and bounded variation. Marron
et al. (1983) considered the multiclassification problem with known prior
probabilities. This work assumed the unknown underlying densities
corresponding to the various classes satisfy some smoothness condition, and
demonstrated that the optimal minimax rates of multiclassification excess risk
is the same as that of the nonparametric regression in Stone (1982), which is
$n^{-2\alpha/(d+2\alpha)}$ where $\alpha$ is the smoothness index.

To the best of our knowledge, there have not been systematic studies on the
non-asymptotic excess risk bounds for classification with a general surrogate
convex loss using CNNs. Our work contributes to the understanding of this deep
learning method and filling the gap on this important topic.

##  7 Conclusion

In this work, we establish non-asymptotic excess risk bounds for a class of
classification methods using CNNs. Our results are derived for a general class
of convex surrogate losses and target functions with different modulus of
continuity and are applicable to many widely used classification methods in
practical machine learning tasks, including those with the least squares, the
logistic, the exponential and the SVM hinge losses. An important feature of
our results is that we clearly define the prefactors in terms of the input
data dimension $d$ and other model parameters. Our obtained excess risk bounds
significantly improve over the currently available ones in the sense that, the
prefactors of our obtained bounds depend on the dimensionality $d$
polynomially in some important models, including the logistic regression and
SVM. However, the prefactor of the excess risk bound with the exponential loss
depends on $d$ exponentially, similar to the results in the existing works on
nonparametric regression using deep neural networks. It is important to
clearly describe the prefactors since they may dominant the error bounds in
high-dimensional problems with a large $d$. We also show that the
classification methods with CNNs can circumvent the curse of dimensionality if
the input data is supported on a neighborhood of a low-dimensional manifold
embedded in the ambient space $\mathbb{R}^{d}$.

To establish the non-asymptotic excess risk bounds, we need to develop an
upper bound for the covering number for the class of general convolutional
neural networks with a bias term in each convolutional layer, and derive new
results on the approximation power of CNNs for any uniformly-continuous target
functions. These results provide further insights into the complexity and the
approximation power of general convolutional neural networks, which are of
independent interest and may have applications in other problems involving
CNNs.

Some important future problems include generalizing the theoretical results
and techniques developed in this work to other types of classification methods
such as the distance weighted discrimination (Marron et al., 2007; Wang and
Zou, 2016) and unsupervised learning problems that use CNNs for data
representation and function approximation.

Acknowledgments

The work of Y. Jiao is supported in part by the National Science Foundation of
China grant 11871474 and by the research fund of KLATASDSMOE of China. The
work of Y. Lin is supported by the Hong Kong Research Grants Council (Grant
No. 14306219 and 14306620), the National Natural Science Foundation of China
(Grant No. 11961028) and Direct Grants for Research, The Chinese University of
Hong Kong. The work of J. Huang is partially supported by the U.S. NSF grant
DMS-1916199.

## Appendix

This appendix contains additional technical details and the proofs of the
lemmas and theorems stated in the paper.

##  A Covering number of CNNs

In this section, to give upper bounds of the estimation error, we study the
covering number bounds for the class of functions implemented by CNNs.
Firstly, the definitions of covering number and packing number are given
below.

######  Definition 12 (Covering number)

Let $(K,\|\cdot\|)$ be a metric space, let $C$ be a subset of $K$, and let
$\epsilon$ be a positive real number. Let $B_{\epsilon}(x)$ denote the ball of
radius $\epsilon$ centered at $x$. Then $C$ is called a $\epsilon$-covering of
$K$, if $K\subset\cup_{x\in C}B_{\epsilon}(x).$ The covering number of the
metric space $(K,\|\cdot\|)$ with any radius $\epsilon>0$ is the minimum
cardinality of any $\epsilon$-covering, which is defined by
$\mathcal{N}(K,\epsilon,\|\cdot\|)=\min\\{|C|:C{\rm\ is\ a\ }\epsilon{\rm-
covering\ of\ }K\\}$.

######  Definition 13 (Packing number)

Let $(K,\|\cdot\|)$ be a metric space, let $P$ be a subset of $K$, and let
$\epsilon$ be a positive real number. Let $B_{\epsilon}(x)$ denote the ball of
radius $\epsilon$ centered at $x$. Then $P$ is called a $\epsilon$-packing of
$K$, if $\\{B_{\epsilon}(x)\\}_{x\in P}$ is pairwise disjoint. The
$\epsilon$-packing number of the metric space $(K,\|\cdot\|)$ with any radius
$\epsilon>0$ is the maximum cardinality of any $\epsilon$-packing, which is
defined by $\mathcal{M}(K,\epsilon,\|\cdot\|)=\max\\{|P|:P{\rm\ is\ a\
}\epsilon{\rm-packing\ of\ }K\\}$.

###### Lemma 14

Let $(K,\|\cdot\|)$ be a metric space, and for any $\epsilon>0$, let
$\mathcal{N}(K,\epsilon,\|\cdot\|)$ and $\mathcal{M}(K,\epsilon,\|\cdot\|)$
denote the $\epsilon$-covering number and $\epsilon$-packing number
respectively, then

$\mathcal{M}(K,2\epsilon,\|\cdot\|)\leq\mathcal{N}(K,\epsilon,\|\cdot\|)\leq\mathcal{M}(K,\epsilon,\|\cdot\|).$

Proof  For simplicity, we write
$\mathcal{N}_{\epsilon}=\mathcal{N}(K,\epsilon,\|\cdot\|)$ and
$\mathcal{M}_{\epsilon}=\mathcal{M}(K,\epsilon,\|\cdot\|)$. We firstly proof
$\mathcal{M}_{2\epsilon}\leq\mathcal{N}_{\epsilon}$ by contradiction. Let
$P=\\{p_{1},\ldots,p_{\mathcal{M}_{2\epsilon}}\\}$ be any maximal
$2\epsilon$-packing of $K$ and
$C=\\{c_{1},\ldots,c_{\mathcal{N}_{\epsilon}}\\}$ be any minimal
$\epsilon$-covering of $K$. If
$\mathcal{M}_{2\epsilon}\geq\mathcal{N}_{\epsilon}+1$, then we must have
$p_{i}$ and $p_{j}$ belonging to the same $\epsilon$-ball
$B_{\epsilon}(c_{k})$ for some $i\not=j$ and $k$. This means that the distance
between $p_{i}$ and $p_{j}$ cannot be more than the diameter of the ball, i.e.
$\|p_{i}-p_{j}\|\leq 2\epsilon$, which leads to a contradiction since
$\|p_{i}-p_{j}\|>2\epsilon$ by the definition of packing.

Secondly, we prove $\mathcal{N}_{\epsilon}\leq\mathcal{M}_{\epsilon}$ by
showing that each maximal $\epsilon$-packing
$P=\\{p_{1},\ldots,p_{\mathcal{M}_{\epsilon}}\\}$ is also a
$\epsilon$-covering. Note that for any $x\in K\backslash P$, there exist a
$p_{i}\in P$ such that $\|x-p_{i}\|\leq\epsilon$ (if this does not hold, then
we can construct a bigger packing with $p_{\mathcal{M}_{\epsilon}+1}=x$). Thus
$P$ is also a $\epsilon$-covering and we have
$\mathcal{N}_{\epsilon}\leq\mathcal{M}_{\epsilon}$ by the definition of
covering.

###### Lemma 15

Let $a\geq 0$ and $K=\\{x:x\in\mathbb{R}^{d},\|x\|_{2}\leq a\\}$ where
$\|\cdot\|_{2}$ is the $L_{2}$ norm of a vector, then for any $\epsilon>0$,
the covering number of $K$ is bounded by

$\log\mathcal{N}(K,\epsilon,\|\cdot\|_{2})\leq d\log(1+\frac{2a}{\epsilon}).$

Proof  Let $P$ be a maximal $\epsilon$-packing of $K$ with packing number
$\mathcal{M}_{\epsilon}$, then $\cup_{x\in P}B_{\epsilon/2}(x)\subset
B_{a+\epsilon/2}(0)$ by the definition of packing. To compare the volume of
these two sets, we have
$\mathcal{M}_{\epsilon}(\epsilon/2)^{d}\leq(a+\epsilon/2)^{d}$, and thus

$\mathcal{N}(K,\epsilon,\|\cdot\|_{2})\leq\mathcal{M}(K,\epsilon,\|\cdot\|_{2})\leq(1+\frac{2a}{\epsilon})^{d}.$

Define $\|\cdot\|_{F}$ as the Frobenius norm of a matrix, i.e.
$\|A\|_{F}=\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}^{2}}$ for a matrix
$A=(a_{ij})\in\mathbb{R}^{m\times n}$, and define $\|\cdot\|_{2}$ as the
spectral norm of a matrix , i.e. $\|A\|_{2}$ is the largest singular value of
$A$ or the square root of the largest eigenvalue of the matrix $A^{\top}A$.
For matrix $A=\in\mathbb{R}^{m\times n}$ of rank $r$, we have
$\|A\|_{2}\leq\|A\|_{F}\leq\sqrt{r}\|A\|_{2}$, and $\|A\|_{F}=\|A\|_{2}$ when
$A$ is a vector. Next, we give covering number upper bounds for single fully
connected layer, single convolutional layer and general CNNs.

######  Lemma 16 (Covering number of a single fully connected layer)

Let $W\in\mathbb{R}^{d_{out}\times d_{in}}$ and $b\in\mathbb{R}^{d_{out}}$ be
the weight matrix and bias vector for a fully connected layer respectively,
which satisfy $\|W\|_{F}+\|b\|_{F}\leq a$. Let $X\in\mathbb{R}^{d_{in}}$ be an
input with bounded norm, i.e. $\|X\|_{F}=\|X\|_{2}<\infty$, and let
$\mathcal{F}_{a}(X)=\\{\sigma(WX+b)\in\mathbb{R}^{d_{out}}:\|W\|_{F}+\|b\|_{F}\leq
a\\}$, where $\sigma$ is the ReLU activation function or an activation
function being $\kappa$-Lipschitz, then we have the following covering number
bound

$\log\mathcal{N}(\mathcal{F}_{a}(X),\epsilon,\|\cdot\|_{2})\leq(d_{in}+1)\times
d_{out}\log(1+\frac{2a\kappa(\|X\|_{F}+1)}{\epsilon}).$

Proof  Firstly note that for each $(W,b)$ in the product space
$\mathbb{R}^{d_{out}\times d_{in}}\times\mathbb{R}^{d_{out}}$, the norm
$\|(W,b)\|_{F}:=\|W\|_{F}+\|b\|_{F}$ is well-defined. Let
$C=\\{(W_{1},b_{1}),\ldots,(W_{N},b_{N})\\}$ be a minimal $\epsilon$-covering
of $K=\\{(W,b)\in\mathbb{R}^{d_{out}\times(d_{in}+1)}:\|W\|_{F}+\|b\|_{F}\leq
a\\}$ with covering number $N$. Then for any $(W,b)\in K$, there exist a
$(W_{i},b_{i})$ such that $\|(W_{i},b_{i})-(W,b)\|_{F}\leq\epsilon$, and

$\displaystyle\|\sigma(W_{i}X+b_{i})-\sigma(WX+b)\|_{F}$ $\displaystyle\leq$
$\displaystyle\kappa\|(W_{i}X+b_{i})-(WX+b)\|_{F}$ $\displaystyle\leq$
$\displaystyle\kappa\|(W_{i}-W)X\|_{F}+\|(b_{i}-b)\|_{F}$ $\displaystyle\leq$
$\displaystyle\kappa\|(W_{i}-W)\|_{2}\|X\|_{2}+\rho\|(b_{i}-b)\|_{2}$
$\displaystyle\leq$ $\displaystyle\epsilon\kappa(\|X\|_{2}+1).$

Thus $C_{x}=\\{W_{1}X+b_{1},\ldots,W_{N}X+b_{N}\\}$ is a
$\epsilon\kappa(\|X\|_{2}+1)$-covering of $\mathcal{F}_{a}(X)$. Note that
$(W,b)$ can be reshaped into a $d_{out}\times(d_{in}+1)$-dimensional vector
with its Euclidean norm $\sqrt{\|W\|_{F}^{2}+\|b\|_{F}^{2}}$ no greater than
$\|W\|_{F}+\|b\|_{F}\leq a$, then by Lemma 15,
$\log\mathcal{N}(\mathcal{F}_{a}(X),\epsilon(\|X\|_{2}+1),\|\cdot\|_{2})\leq
N\leq(d_{in}+1)\times d_{out}\log(1+\frac{2a}{\epsilon}).$ Thus we have

$\log\mathcal{N}(\mathcal{F}_{a}(X),\epsilon,\|\cdot\|_{2})\leq(d_{in}+1)\times
d_{out}\log(1+\frac{2a\kappa(\|X\|_{F}+1)}{\epsilon}).$

######  Lemma 17 (Covering number of a single convolutional layer)

Let $C=(c_{1},\ldots,c_{r})\in\mathbb{R}^{r\times s}$,
$W^{c}\in\mathbb{R}^{d_{out}\times d_{in}}$ and $b^{c}\in\mathbb{R}^{d_{out}}$
be the convolutional matrix with $c$ filters with size $s$, induced weight
matrix and bias vector for convolutional layer respectively, which satisfy
$\|C\|_{F}+\|b^{c}\|_{F}\leq a$. Suppose each filter performs $m$ times
operation, i.e. $d_{out}=r\times m$. Let $X\in\mathbb{R}^{d_{in}}$ be an input
with bounded norm, i.e. $\|X\|_{F}=\|X\|_{2}<\infty$, and let
$\mathcal{F}_{a}(X)=\\{\sigma(W^{c}X+b^{c})\in\mathbb{R}^{d_{out}}:\|C\|_{F}+\|b^{c}\|_{F}\leq
a\\}$, where $\sigma$ is the ReLU activation function or max-pooling operator
being $\kappa$-Lipschitz, then we have the following covering number bound

$\log\mathcal{N}(\mathcal{F}_{a}(X),\epsilon,\|\cdot\|_{2})\leq
r\times(s+m)\log(1+\frac{2a\kappa(\sqrt{m}\|X\|_{F}+1)}{\epsilon}).$

Proof  Firstly note that for each $(C,b^{c})$ in the product space
$\mathbb{R}^{c\times s}\times\mathbb{R}^{d_{out}}$, the norm
$\|(C,b^{c})\|=\|C\|_{F}+\|b^{c}\|_{F}$ is well-defined. Let
$V=\\{(C_{1},b^{c}_{1}),\ldots,(C_{N},b^{c}_{N})\\}$ be a minimal
$\epsilon$-covering of $K=\\{(C,b^{c})\in\mathbb{R}^{c\times
s}\times\mathbb{R}^{d_{out}}:\|C\|_{F}+\|b^{c}\|_{F}\leq a\\}$ with covering
number $N$. Then for any $(C,b^{c})\in K$, there exist a $(C_{i},b^{c}_{i})$
such that $\|C_{i}-C\|_{F}+\|b^{c}_{i}-b^{c}\|_{F}\leq\epsilon$, and

$\displaystyle\|\sigma(W^{c}_{i}X+b^{c}_{i})-\sigma(W^{c}X+b^{c})\|_{F}$
$\displaystyle\leq$
$\displaystyle\kappa\|(W^{c}_{i}X+b^{c}_{i})-(W^{c}X+b^{c})\|_{F}$
$\displaystyle\leq$
$\displaystyle\kappa\|(W^{c}_{i}-W^{c})X\|_{F}+\kappa\|(b^{c}_{i}-b^{c})\|_{F}$
$\displaystyle=$
$\displaystyle\kappa\sqrt{\sum_{i=1}^{r}\sum_{j=1}^{m}\|c_{i}^{\top}X_{S_{j}}\|_{2}^{2}}+\kappa\|(b^{c}_{i}-b^{c})\|_{F}$
$\displaystyle\leq$
$\displaystyle\kappa\|X\|_{2}\sqrt{\sum_{i=1}^{r}\sum_{j=1}^{m}\|c_{i}\|_{2}^{2}}+\kappa\|(b^{c}_{i}-b^{c})\|_{F}$
$\displaystyle=$
$\displaystyle\kappa\sqrt{m}\|X\|_{2}\|C\|_{F}+\kappa\|(b^{c}_{i}-b^{c})\|_{F}$
$\displaystyle\leq$ $\displaystyle\kappa\epsilon(\sqrt{m}\|X\|_{2}+1).$

Thus $V_{X}=\\{W^{c}_{1}X+b^{c}_{1},\ldots,W^{c}_{N}X+b^{c}_{N}\\}$ is a
$\kappa\epsilon(\sqrt{m}\|X\|_{2}+1)$-covering of $\mathcal{F}_{a}(X)$. Note
that $(C,b^{c})$ can be reshaped into a $rs+rm$-dimensional vector with its
Euclidean norm equals $\|C\|_{F}+\|b^{c}\|_{F}\leq a$, then by Lemma 15,
$\log\mathcal{N}(\mathcal{F}_{a}(X),\kappa\epsilon(\sqrt{m}\|X\|_{2}+1),\|\cdot\|_{F})\leq
N\leq(rs+rm)\log(1+\frac{2a}{\epsilon}).$ Thus we have

$\log\mathcal{N}(\mathcal{F}_{a}(X),\epsilon,\|\cdot\|_{2})\leq
r\times(s+m)\log(1+\frac{2a(\sqrt{m}\|X\|_{2}+1)\kappa}{\epsilon}).$

##  B Proof of Theorems

In this section, we prove Theorems 4, 6, 7, 8, 11 and the SVM example.

###  B.1 Proof of Theorem 4

Proof  The idea of our proof is mainly based on Lemma A.7 in Bartlett et al.
(2017). We modified it by allowing the bias vector exists in each layer of the
CNNs.

Let $(\epsilon_{1},\ldots,\epsilon_{L})$ be given positive numbers, let
$(\sigma_{1},\ldots,\sigma_{L})$ be fixed Lipschitz mappings (where
$\sigma_{i}$ is $\rho_{i}$-Lipschitz). Let $\mathcal{L}_{F}$ be a subset of
indices $\\{1,\ldots,L\\}$ and
$\mathcal{L}_{C}=\\{1,\ldots,L\\}\backslash\mathcal{L}_{F}$ be its complement,
and let $A=(A_{1},\ldots,A_{L})$ be $L$ linear operators with their
corresponding input dimension $(d_{1},\ldots,d_{L})$, where
$A_{l}(X)=W_{l}X+b_{l}$ when $l\in\mathcal{L}_{F}$ with fully connected
weights $W_{l}\in\mathbb{R}^{d_{l}\times d_{l+1}}$, bias
$b_{l}\in\mathbb{R}^{d_{l+1}}$ and $A_{l}(X)=W^{c}_{l}X+b^{c}_{l}$ when
$l\in\mathcal{L}_{C}$ with $W^{c}_{l}\in\mathbb{R}^{d_{l}\times d_{l+1}}$
induced by convolutional weights $C_{l}\in\mathbb{R}^{r_{i}\times s_{i}}$ and
bias $b^{c}_{l}\in\mathbb{R}^{d_{l+1}}$. Suppose each of the $r_{i}$ filter in
$C_{l}$ performs $m_{i}$ operations. Given positive numbers
$(a_{1},\ldots,a_{L})$, and sets $(\mathcal{A}_{1},\ldots,\mathcal{A}_{L})$,
where $\mathcal{A}_{l}=\\{A_{l}:\|W_{l}\|_{F}+\|b_{l}\|_{F}\leq a_{l}\\}$ for
$l\in\mathcal{L}_{F}$ and
$\mathcal{A}_{l}=\\{A_{l}:\|C_{l}\|_{F}+\|b^{c}_{l}\|_{F}\leq a_{l}\\}$ for
$l\in\mathcal{L}_{C}$, and assume the support of the input
$\mathcal{X}\subset\mathbb{R}^{d_{0}}$ is a bounced set, i.e.
$\sup_{X\in\mathcal{X}}\|X\|_{2}\leq B$ for $B\geq 1$. Define the function
class implemented by CNNs

$\mathcal{F}_{CNN}=\\{f:\mathcal{X}\to\mathbb{R}^{d_{L}}:f=\sigma_{L}\circ
A_{L}\cdots\circ\sigma_{1}\circ A_{1},A_{l}\in\mathcal{A}_{l}{\ \rm for\
}l=1\ldots,L\\},$

and for any $f_{1},f_{2}\in\mathcal{F}$, define the $\|\cdot\|_{\infty}$
metric on $\mathcal{F}_{CNN}$ by
$\sup_{X\in\mathcal{X}}\|f_{1}(X)-f_{2}(X)\|_{\infty}$. And let
$\mathcal{B}:=\sup_{f\in\mathcal{F}_{CNN}}\|f\|_{\infty}$ denote the bound of
functions in $\mathcal{F}_{CNN}$ and let
$\mathcal{S}=\sum_{l\in\mathcal{L}_{F}}(d_{l-1}+1)\times
d_{l}+\sum_{l\in\mathcal{L}_{C}}(s_{i}+m_{i})\times r_{l}$ denote the number
of parameters for networks in $\mathcal{F}_{CNN}.$ Then for any $\epsilon>0$,
we have

$\log\mathcal{N}(\mathcal{F}_{CNN},\epsilon,\|\cdot\|_{\infty})\leq
2\mathcal{S}\Big{(}\frac{L\mathcal{B}}{\epsilon}\Big{)}^{1/2}.$

We now inductively prove the result in four steps. For $l=1,\ldots,L$, define
$\mathcal{F}_{l}=\\{f:\mathcal{X}\to\mathbb{R}^{d_{l}}:f=\sigma_{l}\circ
A_{l}\cdots\circ\sigma_{1}\circ A_{1},A_{i}\in\mathcal{A}_{i}{\ \rm for\
}i=1\ldots,l\\}$. Note that $\mathcal{F}_{CNN}=\mathcal{F}_{L}$.

Step 1. Choose a minimal $\epsilon_{1}$-covering $K_{1}$ of $\mathcal{F}_{1}$,
thus

$|K_{1}|\leq\mathcal{N}(\mathcal{F}_{1},\epsilon_{1},\|\cdot\|_{\infty})=:\mathcal{N}_{1}.$

Step 2. For each element $f\in K_{l-1}$, we can construct an minimal
$\epsilon_{l}$-covering $K_{l}(f)$ of the set of functions
$\\{\sigma_{l}\circ{A}_{l}\circ f:A_{l}\in\mathcal{A}_{l}\\}$. Here
$f=\sigma_{l-1}\circ A_{l-1}\cdots\circ\sigma_{1}\circ
A_{1}\in\mathcal{F}_{l-1}$ for some certain
$(A_{1},\ldots,A_{l-1})\in(\mathcal{A}_{1},\ldots,\mathcal{A}_{l-1})$, thus

$|K_{l}(f)|\leq\sup_{(A_{1},\ldots,A_{i}),\forall i\leq
l-1,A_{i}\in\mathcal{A}_{i}}\mathcal{N}(\\{\sigma_{l}\circ{A}_{l}\circ
f:f\in\mathcal{F}_{l-1},A_{l}\in\mathcal{A}_{l}\\},\epsilon_{l},\|\cdot\|_{\infty}):=\mathcal{N}_{l}.$

By the definition of $K_{l}=\cup_{f\in K_{l-1}}K_{l}(f)$, we have

$|K_{l}|\leq|K_{l-1}|\sup_{f\in
K_{l-1}}|K_{l}(f)|\leq\mathcal{N}_{l}\Pi_{i=1}^{l-1}\mathcal{N}_{i}=\Pi_{i=1}^{l}\mathcal{N}_{i}.$

Step 3. We need to show such iterative constructed $K_{L}$ is indeed an
$\epsilon$-covering of $\mathcal{F}_{L}=\mathcal{F}_{FNN}$ for some $\epsilon$
depending on $(\epsilon_{1},\ldots,\epsilon_{L})$, $(a_{1},\ldots,a_{L})$,
$(\rho_{1},\ldots,\rho_{L})$ and $(d_{0},\ldots,d_{L})$. For any
$f_{L}\in\mathcal{F}_{L}$, there exists
$(A_{1},\ldots,A_{L})\in(\mathcal{A}_{1},\ldots,\mathcal{A}_{L})$ such that
$f=\sigma_{L}\circ A_{L}\cdots\circ\sigma_{1}\circ A_{1}$, let
$f_{l}=\sigma_{l}\circ A_{l}\cdots\circ\sigma_{1}\circ A_{1}$ for
$l=1,\ldots,L-1$. By the definition of $K_{1}$, there exists $f_{1}^{*}\in
K_{1}$ such that $\|f_{1}^{*}-f_{1}\|_{\infty}\leq\epsilon_{1}$. Define
$\hat{f}^{*}_{2}=\sigma_{2}\circ A_{2}(f^{*}_{1})$, then by the definition of
$K_{2}$, there exists $f_{2}^{*}\in K_{2}$ such that
$\|f_{2}^{*}-\sigma_{2}\circ A_{2}(f^{*}_{1})\|_{\infty}\leq\epsilon_{2}$ and

$\displaystyle\|f_{2}-f^{*}_{2}\|_{\infty}$
$\displaystyle\leq\|f_{2}-\sigma_{2}\circ
A_{2}(f^{*}_{1})\|_{\infty}+\|\sigma_{2}\circ
A_{2}(f^{*}_{1})-f_{2}^{*}\|_{\infty}$ $\displaystyle\leq\|\sigma_{2}\circ
A_{2}(f_{1})-\sigma_{2}\circ A_{2}(f^{*}_{1})\|_{\infty}+\epsilon_{2}$
$\displaystyle\leq\rho_{2}a_{2}\|f_{1}^{*}-f_{1}\|_{\infty}+\epsilon_{2}$
$\displaystyle\leq\rho_{2}a_{2}\epsilon_{1}+\epsilon_{2}.$

By induction, there exists $f_{L}^{*}\in K_{L}$ such that

$\|f^{*}_{L}-f_{L}\|_{\infty}\leq\sum_{l}^{L}\epsilon_{l}\Pi_{i=l+1}^{L}\rho_{i}a_{i}.$

Let $\epsilon=\sum_{l=1}^{L}\epsilon_{l}\Pi_{i=l+1}^{L}\rho_{i}a_{i}$, by the
result in Step 2, we know that $K_{L}$ is a $\epsilon$-covering of
$\mathcal{F}_{L}=\mathcal{F}_{CNN}$ and

$\log\mathcal{N}(\mathcal{F}_{CNN},\epsilon,\|\cdot\|_{\infty})\leq\log|K_{L}|\leq\sum_{i=1}^{L}\log\mathcal{N}_{i}.$

Step 4. We calculate $\log\mathcal{N}_{i}$ for each $i=1,\ldots,L$ and
carefully choose $(\epsilon_{1},\ldots,\epsilon_{L})$ to give a covering
number of $\mathcal{F}_{CNN}$ for any radius $\epsilon>0.$ For
$l\in\mathcal{L}_{C}$, we denote the number operations for each filter by
$m_{l}=d_{l}/r_{l}$, and for $l\in\mathcal{L}_{F}$, we define $m_{l}=1$. Then
for any $f_{1}\in\mathcal{F}_{1}$, we have
$\|f_{1}\|_{\infty}\leq\rho_{1}a_{1}(\sqrt{m_{1}}B+1)$. By induction, it is
easy to find for any $f_{l}\in\mathcal{F}_{l}$ and $l=1,\ldots,L$ we have
$\|f_{l}\|_{\infty}\leq
B\Pi_{i=1}^{l}\sqrt{m_{i}}\rho_{i}a_{i}+\sum_{i=1}^{l}\Pi_{j=i}^{l}\sqrt{m_{j}}\rho_{j}a_{j}:=B_{l}$.
For $l\in\mathcal{L}_{F}$, based on Lemma 16, we have

$\log\mathcal{N}_{l}=\log\mathcal{N}(\\{\sigma_{l}\circ A_{l}\circ
f\in\mathcal{F}_{l-1},A_{l}\in\mathcal{A}_{l}\\},\epsilon_{l},\|\cdot\|_{\infty})\leq(d_{l-1}+1)\times
d_{l}\log(1+\frac{2\rho_{l}a_{l}(\sqrt{m_{l}}B_{l-1}+1)}{\epsilon_{l}}),$

and for $l\in\mathcal{L}_{C}$, based on Lemma 17, we have

$\log\mathcal{N}_{l}=\log\mathcal{N}(\\{\sigma_{l}\circ A_{l}\circ
f\in\mathcal{F}_{l-1},A_{l}\in\mathcal{A}_{l}\\},\epsilon_{l},\|\cdot\|_{\infty})\leq(s_{i}+m_{i})\times
r_{l}\log(1+\frac{2\rho_{l}a_{l}(\sqrt{m_{l}}B_{l-1}+1)}{\epsilon_{l}}).$

Then, we let $\epsilon_{l}=e_{l}\epsilon/\Pi_{i=l+1}^{L}\rho_{i}a_{i}$, and
$e_{l}=(\sqrt{m_{l}}B_{l-1}+1)\Pi_{i=l}^{L}\rho_{i}a_{i}/\sum_{i=1}^{L}(\sqrt{m_{i}}B_{i-1}+1)\Pi_{j=i}^{L}\rho_{j}a_{j}$
which satisfies $\sum_{l=1}^{L}e_{l}=1$ and the requirement
$\epsilon=\sum_{l=1}^{L}\epsilon_{l}\Pi_{i=l+1}^{L}\rho_{i}a_{i}$ in Step 3.
By the result in Step 3,

$\displaystyle\log\mathcal{N}(\mathcal{F}_{CNN},\epsilon,\|\cdot\|_{\infty})\leq\sum_{l\in\mathcal{L}_{F}}\log\mathcal{N}_{l}+\sum_{l\in\mathcal{L}_{C}}\log\mathcal{N}_{l}$
$\displaystyle\leq$ $\displaystyle\sum_{l\in\mathcal{L}_{F}}(d_{l-1}+1)\times
d_{l}\log(1+\frac{2\rho_{l}a_{l}(\sqrt{m_{l}}B_{l-1}+1)}{\epsilon_{l}})+\sum_{l\in\mathcal{L}_{C}}(s_{i}+m_{i})\times
r_{l}\log(1+\frac{2\rho_{l}a_{l}(\sqrt{m_{l}}B_{l-1}+1)}{\epsilon_{l}})$
$\displaystyle=$
$\displaystyle\Big{(}\sum_{l\in\mathcal{L}_{F}}(d_{l-1}+1)\times
d_{l}+\sum_{l\in\mathcal{L}_{C}}(s_{i}+m_{i})\times
r_{l}\Big{)}\log\Big{(}1+\frac{2\sum_{l=1}^{L}(\sqrt{m_{l}}B_{l-1}+1)\Pi_{i=l}^{L}\rho_{i}a_{i})}{\epsilon}\Big{)}$
$\displaystyle\leq$
$\displaystyle\Big{(}\sum_{l\in\mathcal{L}_{F}}(d_{l-1}+1)\times
d_{l}+\sum_{l\in\mathcal{L}_{C}}(s_{i}+m_{i})\times
r_{l}\Big{)}\log\Big{(}1+\frac{4\sum_{l=1}^{L}\sqrt{m_{l}}B_{l-1}\Pi_{i=l}^{L}\rho_{i}a_{i}}{\epsilon}\Big{)}$
$\displaystyle\leq$
$\displaystyle\Big{(}\sum_{l\in\mathcal{L}_{F}}(d_{l-1}+1)\times
d_{l}+\sum_{l\in\mathcal{L}_{C}}(s_{i}+m_{i})\times
r_{l}\Big{)}\log\Big{(}1+\frac{4LB_{L}}{\epsilon}\Big{)}.$

The first inequality follows form Lemma 16 and 17. The second last inequality
follows form $\sqrt{m_{l}}B_{l-1}\geq 1$ and the last inequality follows form
$\sqrt{m_{l}}B_{l-1}\Pi_{i=l}^{L}\rho_{i}a_{i}\leq B_{L}$. If we let
$\mathcal{S}=\sum_{l\in\mathcal{L}_{F}}(d_{l-1}+1)\times
d_{l}+\sum_{l\in\mathcal{L}_{C}}(s_{i}+m_{i})\times r_{l}$ denote the number
of parameters in the CNN, let $\mathcal{B}=B_{L}$ denote the bound of
functions in $\mathcal{F}_{CNN}$, then

$\log\mathcal{N}(\mathcal{F}_{CNN},\epsilon,\|\cdot\|_{\infty})\leq\mathcal{S}\log\Big{(}1+\frac{4\mathcal{B}L}{\epsilon}\Big{)}\leq
2\mathcal{S}\Big{(}\frac{4\mathcal{B}L}{\epsilon}\Big{)}^{1/2},$

where the second inequality follows form $\sqrt{x}\geq\log(1+x)$ for $x\geq
0$.

###  B.2 Proof of Theorem 6

Proof  By Lemma 3, for any loss $\phi$ and random sample
$S=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$, the excess $\phi$-risk of ERM defined in
(5) satisfies

$\displaystyle R^{\phi}(\hat{f}_{n}^{\phi})-R^{\phi}(f^{\phi}_{0})\leq$
$\displaystyle
2\sup_{f\in\mathcal{F}}|R^{\phi}(f)-R^{\phi}_{n}(f)|+\inf_{f\in\mathcal{F}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0}),$

where $R^{\phi}_{n}(f)$ is the empirical risk of $f$ on sample $S$ under loss
$\phi$ which is defined by $R^{\phi}_{n}=\sum_{i=1}^{n}\phi(Y_{i}f(X_{i}))/n$.
Next, we take care the first term
$2\sup_{f\in\mathcal{F_{CNN}}}|R^{\phi}(f)-R^{\phi}_{n}(f)|$ here when the
function class is taken as functions implemented by CNNs $\mathcal{F}_{CNN}$.
Our proof consists of two main Steps.

Step 1. For any given $\delta>0$, with probability at least $1-\delta$, the
following holds,

$\sup_{f\in\mathcal{F_{CNN}}}|R^{\phi}(f)-R^{\phi}_{n}(f)|\leq
2B^{\phi}\mathcal{R}_{n}(\mathcal{F}_{CNN})+B_{\phi}\mathcal{B}\sqrt{\frac{2\log(1/\delta)}{n}},$

where
$\mathcal{R}_{S}(\mathcal{F}_{CNN})=\mathbb{E}_{\sigma}\Big{[}\sup_{f\in\mathcal{F}_{CNN}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(X_{i})\Big{]}$
is the empirical Rademacher complexity of $\mathcal{F}_{CNN}$ with respect to
the sample $S$ and $\sigma=(\sigma_{1},\ldots,\sigma_{n})^{\top}$, with
$\sigma_{i}$ being independent Rademacher random variables, i.e. uniform
random variables taking values in $\\{+1,-1\\}$. We let
$\mathcal{R}_{n}(\cdot)=\mathbb{E}\mathcal{R}_{S}(\cdot)$ denote the
expectation of the empirical Rademacher complexity. Define

$G^{\phi}(S)=\sup_{f\in\mathcal{F}_{CNN}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\\{\phi(Y_{i}f(X_{i}))-\mathbb{E}\phi(Y_{i}f(X_{i}))\\}\Big{]},$

and let $S^{\prime}$ be another sample differing form $S$ by exactly one
point, say $(X_{1},Y_{1})$ in $S$ and $(X^{\prime}_{1},Y^{\prime}_{1})$ in
$S^{\prime}$. Then, by the definition of suprema and Assumption 1, we have

$\displaystyle G^{\phi}(S^{\prime})-G^{\phi}(S)$
$\displaystyle\leq\sup_{f\in\mathcal{F}_{CNN}}\frac{1}{n}\sum_{i=1}^{n}\\{\phi(Y_{i}f(X_{i}))-\phi(Y^{\prime}_{i}f(X^{\prime}_{i}))\\}$
$\displaystyle=\sup_{f\in\mathcal{F}_{CNN}}\frac{1}{n}\\{\phi(Y_{1}f(X_{1}))-\phi(Y^{\prime}_{1}f(X^{\prime}_{1}))\\}$
$\displaystyle\leq B_{\phi}|Y_{1}f(X_{1})-Y^{\prime}_{1}f(X^{\prime}_{1})|/n$
$\displaystyle\leq\frac{2\mathcal{B}B_{\phi}}{n}.$

Then, by McDiarmid’s inequality, for any $\delta>0$, with probability at least
$1-\delta$, it follows

$G^{\phi}(S)\leq\mathbb{E}_{S}\\{G^{\phi}(S)\\}+\mathcal{B}B_{\phi}\sqrt{\frac{2\log(1/\delta)}{n}}.$
(20)

Now let $S^{\prime}$ be another sample independent with $S$ and
$\sigma=(\sigma_{1},\ldots,\sigma_{n})^{\top}$ be independent Rademacher
random variables. We next bound the expectation of $G^{\phi}(S)$ as below,

$\displaystyle\mathbb{E}_{S}\\{G^{\phi}(S)\\}$
$\displaystyle=\mathbb{E}_{S}\Bigg{(}\sup_{f\in\mathcal{F}_{CNN}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\\{\phi(Y_{i}f(X_{i}))-\mathbb{E}\phi(Y_{i}f(X_{i}))\\}\Big{]}\Bigg{)}$
$\displaystyle=\mathbb{E}_{S}\Bigg{(}\sup_{f\in\mathcal{F}_{CNN}}\mathbb{E}_{S^{\prime}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\\{\phi(Y_{i}f(X_{i}))-\phi(Y^{\prime}_{i}f(X^{\prime}_{i}))\\}\Big{]}\Bigg{)}$
$\displaystyle\leq\mathbb{E}_{S,S^{\prime}}\Bigg{(}\sup_{f\in\mathcal{F}_{CNN}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\\{\phi(Y_{i}f(X_{i}))-\phi(Y^{\prime}_{i}f(X^{\prime}_{i}))\\}\Big{]}\Bigg{)}$
$\displaystyle=\mathbb{E}_{S,S^{\prime},\sigma}\Bigg{(}\sup_{f\in\mathcal{F}_{CNN}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\\{\phi(Y_{i}f(X_{i}))-\phi(Y^{\prime}_{i}f(X^{\prime}_{i}))\\}\Big{]}\Bigg{)}$
$\displaystyle\leq\mathbb{E}_{S,\sigma}\Bigg{(}\sup_{f\in\mathcal{F}_{CNN}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\phi(Y_{i}f(X_{i}))\Big{]}\Bigg{)}+\mathbb{E}_{S^{\prime},\sigma}\Bigg{(}\sup_{f\in\mathcal{F}_{CNN}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\phi(Y^{\prime}_{i}f(X^{\prime}_{i}))\Big{]}\Bigg{)}$
$\displaystyle=2\mathcal{R}_{n}(\mathcal{F}^{\phi}_{CNN}),$

where
$\mathcal{F}^{\phi}_{CNN}=\\{(x,y)\mapsto\phi(yf(x)):f\in\mathcal{F}_{CNN}\\}$
is the function class introduced by a fixed function $\phi$ and
$\mathcal{F}_{CNN}$. By Assumption 1, $\phi$ is $B_{\phi}$-Lipschitz, then by
Talagrand’s lemma, see e.g. Lemma 5.7 in Mohri et al. (2018), we have

$\mathcal{R}_{n}(\mathcal{F}^{\phi}_{CNN})\leq
B^{\phi}\mathcal{R}_{n}(\mathcal{F}_{CNN}).$ (21)

Step 2. We bound the Rademacher complexity
$\mathcal{R}_{n}(\mathcal{F}_{CNN})$ in (21) by the covering number through
Dudley’s entropy integral. Let
$\mathcal{N}(\mathcal{F}_{CNN},\epsilon,\|\cdot\|_{\infty})$ denote the
covering number of $\mathcal{F}_{CNN}$ with radius $\epsilon>0$ under
Frobenius norm $\|\cdot\|_{F}$ defined in Appendix A. Here since the output of
each $f\in\mathcal{F}_{CNN}$ is a scalar, thus we can also use metric
$\|\cdot\|_{\infty}$ to define the covering number. By Dudley’s entropy
integral, we have

$\displaystyle\mathcal{R}_{n}(\mathcal{F}_{CNN})$
$\displaystyle\leq\inf_{a>0}\Big{(}{4a}+{12}\int_{a}^{\mathcal{B}}\sqrt{\frac{\log\mathcal{N}(\mathcal{F}_{CNN},\epsilon,\|\cdot\|_{\infty})}{n}}d\epsilon\Big{)}$
$\displaystyle\leq\inf_{a>0}\Big{(}{4a}+{12}\int_{a}^{\mathcal{B}}\frac{(2\mathcal{S})^{1/2}(\mathcal{B}L)^{1/4}}{n^{1/2}\epsilon^{1/4}}d\epsilon\Big{)}$
$\displaystyle=\inf_{a>0}\Big{(}{4a}+\frac{16\sqrt{2}\mathcal{S}^{1/2}(\mathcal{B}L)^{1/4}}{n^{1/2}}(\mathcal{B}^{3/4}-a^{3/4})\Big{)}.$

Taking $a=4\cdot 3^{4}\cdot\mathcal{S}^{2}\mathcal{B}L/n^{2}$, we have,

$\displaystyle\mathcal{R}_{n}(\mathcal{F}_{CNN})$
$\displaystyle\leq\inf_{a>0}\Big{(}{4a}+\frac{16\sqrt{2}\mathcal{S}^{1/2}(\mathcal{B}L)^{1/4}}{n^{1/2}}(\mathcal{B}^{3/4}-a^{3/4})\Big{)}$
$\displaystyle\leq\frac{16\cdot
3^{4}\cdot\mathcal{S}^{2}\mathcal{B}L}{n^{2}}+\frac{16\sqrt{2}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{n^{1/2}}-\frac{64\cdot
3^{3}\cdot\mathcal{S}^{2}\mathcal{B}L}{n^{2}}$
$\displaystyle=\frac{16\sqrt{2}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{n^{1/2}}-\frac{16\cdot
3^{3}\cdot\mathcal{S}^{2}\mathcal{B}L}{n^{2}}$
$\displaystyle\leq\frac{16\sqrt{2}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{n^{1/2}}.$

Combine above inequality, (20) and (21), we have for any $\delta>0$, with
probability at least $1-\delta$,

$R^{\phi}(\hat{f}_{n}^{\phi})-R^{\phi}(f^{\phi}_{0})\leq\frac{16\sqrt{2}B_{\phi}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{\sqrt{n}}+2B_{\phi}\mathcal{B}\sqrt{\frac{2\log(1/\delta)}{n}}+\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0}).$

###  B.3 Proof of Theorem 7

Proof  Firstly, we prove that under Assumption 1 and 2, $f_{0,T}^{\phi}$, the
truncated version of the target function $f^{\phi}_{0}$, is bounded by $T$ and
continuous on $[0,1]^{d}$. Recall that for any $a\in\mathbb{R}$ and
$\eta\in[0,1]$, the conditional risk function
$H^{\phi}(\eta,a)=\eta\phi(a)+(1-\eta)\phi(-a)$. Given $\eta\in[0,1]$, the
function $dH^{\phi}(\eta,a)/da=\eta\phi^{\prime}(a)-(1-\eta)\phi^{\prime}(-a)$
is continuous in both $\eta$ and $a$. Thus the solution
$a(\eta)=\arg\min_{a\in\bar{\mathbb{R}}}H(\eta,\alpha)$ is continuous with
respect to $\eta$, and $|a(\eta)|<\infty$ when $\eta\in(0,1)$. By Assumption 2
(a), $\eta(x)$ is continuous on $\\{x\in[0,1]^{d}:\eta(x)\leq 1-\delta\\}$ for
any $\delta\in(0,1)$, thus $f_{0}^{\phi}(x)=f_{0}^{\phi}(\eta(x))$ is
continuous on $\\{x\in[0,1]^{d}:|f_{0}^{\phi}(\eta(x))|\leq T\\}$ for any
$T>0$. And for any $T>0$, the set $\\{x\in[0,1]^{d}:|f_{0}^{\phi}(x)|\leq
T\\}$ is a compact set. Thus $f_{0,T}^{\phi}$, the truncated version of target
function is continuous on $[0,1]^{d}$.

Recall that for any $f$, the $\phi$-risk is defined by
$R^{\phi}(f)=\mathbb{E}\phi(Yf(X))$, then for $f_{0,T}^{\phi}$, the truncated
version of target function satisfies

$\displaystyle R^{\phi}(f_{0,T}^{\phi})-R^{\phi}(f_{0}^{\phi})$
$\displaystyle=\mathbb{E}\\{\phi(Yf_{0,T}^{\phi}(X))-\phi(Yf_{0}^{\phi}(X))\\}$
$\displaystyle=\mathbb{E}\Big{[}\\{\phi(Yf_{0,T}^{\phi}(X))-\phi(Yf_{0}^{\phi}(X))\\}\\{\mathbbm{1}(|f_{0}^{\phi}(X)|\leq
B)+\mathbbm{1}(|f_{0}^{\phi}(X)|>B)\\}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\mathbbm{1}(|f_{0}^{\phi}(X)|>T)\\{\phi(Yf_{0,T}^{\phi}(X))-\phi(Yf_{0}^{\phi}(X))\\}\Big{]}$
$\displaystyle\leq\inf_{|a|\leq B}\phi(a)-\inf_{a\in\bar{\mathbb{R}}}\phi(a).$

Notice that,

$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f_{0}^{\phi})=\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f_{0,T}^{\phi})+R^{\phi}(f_{0,T}^{\phi})-R^{\phi}(f_{0}^{\phi}),$

then left thing to do is to prove

$\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f_{0,T}^{\phi})\leq
B_{\phi}\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}|f(X)-f^{\phi}_{0,T}(X)|.$

With Assumption 1, $\phi$ is $\mathcal{B}_{\phi}$-Lipschitz, and it is a
straightforward proof that

$\displaystyle\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f_{0,T}^{\phi})$
$\displaystyle=\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}\\{\phi(Yf(X))-\phi(Yf_{0,T}^{\phi}(X))\\}$
$\displaystyle\leq\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}\\{\mathcal{B}_{\phi}|Yf(X)-Yf_{0,T}^{\phi}(X)|\\}$
$\displaystyle=B_{\phi}\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}|f(X)-f_{0,T}^{\phi}(X)|.$

###  B.4 Proof of Theorem 8

Proof  Let $K\in\mathbb{N}^{+}$ and $\tau\in(0,1/K)$, define a region
$\Omega([0,1]^{d},K,\tau)$ of $[0,1]^{d}$ as

$\Omega([0,1]^{d},K,\varepsilon)=\cup_{i=1}^{d}\\{x=[x_{1},x_{2},...,x_{d}]^{T}:x_{i}\in\cup_{k=1}^{K-1}(k/K-\tau,k/K)\\}.$

By Theorem 2.1 of Shen et al. (2020), for any $M,N\in\mathbb{N}^{+}$, there
exists a function $f^{\phi}_{*}\in\mathcal{F}_{MLP}$ with
$f^{\phi}_{0,T}(\textbf{0})+\omega_{f^{\phi}_{0,T}}(\sqrt{d})\leq\mathcal{B}$,
depth $L=12M+14$ and width $\mathcal{W}=\max\\{4d\lfloor
N^{\frac{1}{d}}\rfloor+3d,12N+8\\}$ such that
$\|f^{\phi}_{*}\|_{\infty}\leq|f^{\phi}_{0,T}(\textbf{0})|+\omega_{f^{\phi}_{0,T}}(\sqrt{d})$
and

$|f^{\phi}_{*}(x)-f^{\phi}_{0,T}(x)|\leq
18\sqrt{d}\omega_{f^{\phi}_{0,T}}(N^{-2/d}M^{-2/d}),$

for any $x\in[0,1]^{d}\backslash\Omega([0,1]^{d},K,\tau)$ where $K=\lfloor
N^{1/d}\rfloor^{2}\lfloor M^{1/d}\rfloor^{2}$ and $\tau$ is an arbitrary
number in $(0,\frac{1}{3K}]$. Note that the Lebesgue measure of
$\Omega([0,1]^{d},K,\tau)$ is no more than $dK\tau$ which can be arbitrarily
small if $\tau$ is arbitrarily small. Since $P$ is absolutely continuous with
respect to Lebesgue measure, then we have

$\mathbb{E}\|f^{\phi}_{*}(X)-f^{\phi}_{0,T}(X)\|_{2}\leq
18\sqrt{d}\omega_{f^{\phi}_{0,T}}(N^{-2/d}M^{-2/d}).$

Besides, as the class of functions $\mathcal{F}_{MLP}$ is a subclass of
$\mathcal{F}_{CNN}$ with layer $L$, width $\mathcal{W}$, bound $\mathcal{B}$
and size $\mathcal{S}$. Thus there exists a function $f$ implemented by CNN
with its depth no more than $L=12M+14$ and its width no more than
$\mathcal{W}=\max\\{4d\lfloor N^{\frac{1}{d}}\rfloor+3d,12N+8\\}$ such that

$\mathbb{E}\|f(X)-f^{\phi}_{0,T}(X)\|_{2}\leq
18\sqrt{d}\omega_{f^{\phi}_{0,T}}(N^{-2/d}M^{-2/d}),$

and by Theorem 6 and 7, for any $\delta>0$, with probability at least
$1-\delta$,

$\displaystyle R^{\phi}(\hat{f}_{n})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\frac{16\sqrt{2}B_{\phi}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{\sqrt{n}}+2B_{\phi}\mathcal{B}\sqrt{\frac{2\log(1/\delta)}{n}}$
$\displaystyle+$ $\displaystyle
18\sqrt{d}B_{\phi}\omega_{f^{\phi}_{0,T}}(N^{-2/d}M^{-2/d})+\inf_{|a|\leq
T}\phi(a)-\inf_{a\in\bar{\mathbb{R}}}\phi(a).$

###  B.5 Proof of Lemma 10

Proof  According to Theorem 3.1 in Baraniuk and Wakin (2009), there exists a
linear projector $A\in\mathbb{R}^{d_{\varepsilon}\times d}$ that maps a low-
dimensional manifold in a high-dimensional space to a low-dimensional space
nearly preserving distance. To be exact, there exists a matrix
$A\in\mathbb{R}^{d_{\varepsilon}\times d}$ such that
$AA^{T}=(d/d_{\varepsilon})I_{d_{\varepsilon}}$ where $I_{d_{\varepsilon}}$ is
an identity matrix of size $d_{\varepsilon}\times d_{\varepsilon}$, and

$(1-\varepsilon)|x_{1}-x_{2}|\leq|Ax_{1}-Ax_{2}|\leq(1+\varepsilon)|x_{1}-x_{2}|,$

for any $x_{1},x_{2}\in\mathcal{M}.$ And it is easy to check

$A(\mathcal{M}_{\rho})\subseteq
A([0,1]^{d})\subseteq[-\sqrt{\frac{d}{d_{\varepsilon}}},\sqrt{\frac{d}{d_{\varepsilon}}}]^{d_{\varepsilon}}.$

For any $z\in A(\mathcal{M_{\rho}})$, define
$x_{z}=\mathcal{SL}(\\{x\in\mathcal{M}_{\rho}:Ax=z\\})$ where
$\mathcal{SL}(\cdot)$ is a set function which returns a unique element of a
set. Note if $Ax=z$, then it is not necessary that $x=x_{z}$. For the high-
dimensional function $f^{\phi}_{0,T}:\mathbb{R}^{d}\to\mathbb{R}^{1}$, we
define its low-dimensional representation
$\tilde{f}^{\phi}_{0,T}:\mathbb{R}^{d_{\varepsilon}}\to\mathbb{R}^{1}$ by

$\tilde{f}^{\phi}_{0,T}(z)=f^{\phi}_{0,T}(x_{z}),\quad{\rm for\ any}\ z\in
A(\mathcal{M}_{\rho})\subseteq\mathbb{R}^{d_{\varepsilon}}.$

For any $z_{1},z_{2}\in A(\mathcal{M}_{\rho})$, let
$x_{i}=\mathcal{SL})(\\{x\in\mathcal{M}_{\rho},Ax=z_{i}\\})$. By the
definition of $\mathcal{M}_{\rho}$, there exist
$\tilde{x}_{1},\tilde{x}_{2}\in\mathcal{M}$ such that
$|x_{i}-\tilde{x}_{i}|\leq\rho$ for $i=1,2$. Then

$\displaystyle|\tilde{f}^{\phi}_{0,T}(z_{1})-\tilde{f}^{\phi}_{0,T}(z_{2})|$
$\displaystyle=|{f}^{\phi}_{0,T}(x_{1})-{f}^{\phi}_{0,T}(x_{2})|\leq\omega_{f^{\phi}_{0,T}}(|x_{1}-x_{2}|)\leq\omega_{f^{\phi}_{0,T}}(|\tilde{x}_{1}-\tilde{x}_{2}|+2\rho)$
$\displaystyle\leq\omega_{f^{\phi}_{0,T}}(\frac{1}{1-\varepsilon}|A\tilde{x}_{1}-A\tilde{x}_{2}|+2\rho)$
$\displaystyle\leq\omega_{f^{\phi}_{0,T}}(\frac{1}{1-\varepsilon}|A{x}_{1}-A{x}_{2}|+\frac{2\rho}{1-\varepsilon}\sqrt{\frac{d}{d_{\varepsilon}}}+2\rho)$
$\displaystyle\leq\omega_{f^{\phi}_{0,T}}(\frac{1}{1-\varepsilon}|z_{1}-z_{2}|+\frac{2\rho}{1-\varepsilon}\sqrt{\frac{d}{d_{\varepsilon}}}+2\rho).$

By Lemma 4.1 in Shen et al. (2020), there exists a $\tilde{g}$ defined on
$\mathbb{R}^{d_{\varepsilon}}$, whose modulus of continuity is the same as
$\tilde{f}^{\phi}_{0,T}$ such that

$|\tilde{g}(z)-\tilde{f}_{0,T}(z)|\leq\omega_{f^{\phi}_{0,T}}(\frac{2\rho}{1-\varepsilon}\sqrt{\frac{d}{d_{\varepsilon}}}+2\rho)$

for any $z\in A(\mathcal{M}_{\rho})\subseteq\mathbb{R}^{d_{\varepsilon}}$.
With
$E=[-\sqrt{{d}/{d_{\varepsilon}}},\sqrt{{d}/{d_{\varepsilon}}}]^{d_{\varepsilon}}$,
by Theorem 2.1 and 4.3 of Shen et al. (2020), for any $N,M\in\mathbb{N}_{+}$,
there exists a function
$\tilde{f}_{MLP}:\mathbb{R}^{d_{\varepsilon}}\to\mathbb{R}^{1}$ implemented by
a ReLU MLP with width $\mathcal{W}=\max\\{4d_{\varepsilon}\lfloor
N^{1/d_{\varepsilon}}\rfloor+3d,12N+8\\}$ and depth $L=12M+14$ such that

$|\tilde{f}_{MLP}-\tilde{g}(z)|\leq
18\sqrt{d_{\varepsilon}}\omega_{f^{\phi}_{0,T}}(N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}),$

for any $z\in E\backslash\Omega(E)$ where $\Omega(E)$ is a subset of $E$ with
arbitrarily small Lebesgue measure as well as
$\Omega:=\\{x\in\mathcal{M}_{\rho}:Ax\in\Omega(E)\\}$ does. If we define
$f_{MLP}=\tilde{f}_{MLP}\circ A$ which is $f_{MLP}(x)=\tilde{f}_{MLP}(Ax)$ for
any $x\in[0,1]^{d}$, then $f_{MLP}\in\mathcal{F}_{MLP}$ is also a ReLU MLP
with one more layer than $\tilde{f}_{MLP}$, where this additional layer
computes linear transformation $A$.

Besides, for any $x\in\mathcal{M}_{\rho}$, let $z=Ax$ and
$x_{z}=\mathcal{SL}(\\{x\in\mathcal{M}_{\rho}:Ax=z\\})$. By the definition of
$\mathcal{M}_{\rho}$, there exists $\bar{x},\bar{x}_{z}\in\mathcal{M}$ such
that $|x-\bar{x}|\leq\rho$ and $|x_{z}-\bar{x}_{z}|\leq\rho$. Then we have

$\displaystyle|x-x_{z}|$
$\displaystyle\leq|\bar{x}-\bar{x}_{z}|+2\rho\leq|A\bar{x}-A\bar{x}_{z}|/(1-\varepsilon)+2\rho$
$\displaystyle\leq(|A\bar{x}-A{x}|+|A{x}-A{x}_{z}|+|A{x}_{z}-A\bar{x}_{z}|)/(1-\varepsilon)+2\rho$
$\displaystyle\leq(|A\bar{x}-A{x}|+|A{x}_{z}-A\bar{x}_{z}|)/(1-\varepsilon)+2\rho$
$\displaystyle\leq 2\rho\\{1+\sqrt{d/d_{\varepsilon}}/(1-\varepsilon)\\}.$

Then for any $x\in\mathcal{M}_{\rho}\backslash\Omega$ and $z=Ax$,

$\displaystyle|f_{MLP}(x)-f^{\phi}_{0,T}(x)|$
$\displaystyle\leq|f_{MLP}(x)-f^{\phi}_{0,T}(x_{z})|+|f^{\phi}_{0,T}(x_{z})-f^{\phi}_{0,T}(x)|$
$\displaystyle\leq|\tilde{f}_{MLP}(z)-\tilde{f}^{\phi}_{0,T}(z)|+\omega_{f^{\phi}_{0,T}}(|x-x_{z}|)$
$\displaystyle\leq|\tilde{f}_{MLP}(z)-\tilde{g}(z)|+|\tilde{g}(z)-\tilde{f}^{\phi}_{0,T}(z)|+\omega_{f^{\phi}_{0,T}}(2\rho\\{1+\sqrt{d/d_{\varepsilon}}/(1-\varepsilon)\\})$
$\displaystyle\leq
18\sqrt{d_{\varepsilon}}\omega_{f^{\phi}_{0,T}}(N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}})+2\omega_{f^{\phi}_{0,T}}(N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}})$
$\displaystyle\leq(18\sqrt{d_{\varepsilon}}+2)\omega_{f^{\phi}_{0,T}}(N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}),$

where the third and the fourth inequalities follow from
$\rho\leq(1-\varepsilon)/\\{2(\sqrt{d/d_{\varepsilon}}+1-\varepsilon)\\}N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}$.
Since $P_{X}$ the probability measure of $X$ is absolutely continuous with
respect to Lebesgue measure, then we have

$\mathbb{E}|f_{MLP}(X)-f^{\phi}_{0,T}(X)|\leq(18\sqrt{d_{\varepsilon}}+2)\omega_{f^{\phi}_{0,T}}(N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}}),$

where
$d_{\varepsilon}=O(d_{\mathcal{M}}\frac{\log(d/\varepsilon)}{\varepsilon^{2}})$
is assumed to satisfy $d_{\varepsilon}\ll d$.

###  B.6 Proof of Theorem 11

Proof  The proof is similar to that of Theorem 8, except how we deal with
$\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}\|f(X)-f^{\phi}_{0,T}(X)\|_{2}$.
Combining Theorems 6 and 7 and using Lemma 10, we have

$\displaystyle R^{\phi}(\hat{f}_{n}^{\phi})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\frac{16\sqrt{2}B_{\phi}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{\sqrt{n}}+2B_{\phi}\mathcal{B}\sqrt{\frac{2\log(1/\delta)}{n}}$
$\displaystyle+$
$\displaystyle(18\sqrt{d_{\varepsilon}}+2)B_{\phi}\omega_{f^{\phi}_{0,T}}(N^{-2/d_{\varepsilon}}M^{-2/d_{\varepsilon}})+\inf_{|a|\leq
T}\phi(a)-\inf_{a\in\bar{\mathbb{R}}}\phi(a).$

This completes the proof of Theorem 11.

###  B.7 Proof of the least squares example

Proof  For the least squares loss $\phi(a)=(1-a)^{2}$, we first prove that the
approximation error is of a special form. For any $f\in\mathcal{F}_{CNN}$

$\displaystyle R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$
$\displaystyle=\mathbb{E}\\{\phi(Yf(X))-\phi(Yf^{\phi}_{0}(X))\\}$
$\displaystyle=\mathbb{E}\\{(1-Yf(X))^{2}-(1-Yf^{\phi}_{0}(X))^{2}\\}$