# Deep Convolutional Neural Networks with Zero-Padding: Feature Extraction and
Learning

Zhi Han, Baichen Liu, Shao-Bo Lin, and Ding-Xuan Zhou  Z. Han and B. Liu are
with the State Key Laboratory of Robotics, Shenyang Institute of Automation,
Chinese Academy of Sciences, Shenyang, China and Institutes for Robotics and
Intelligent Manufacturing, Chinese Academy of Sciences, Shenyang, China. S.B.
Lin is with the Center of Intelligent Decision-Making and Machine Learning,
School of Management, Xi’an Jiaotong University, Xi’an, China. D.X. Zhou is
with the School of Mathematics and Statistics, University of Sydney, Sydney
NSW 2006, Australia. Corresponding author: S. B. Lin<EMAIL_ADDRESS>
###### Abstract

This paper studies the performance of deep convolutional neural networks
(DCNNs) with zero-padding in feature extraction and learning. After verifying
the roles of zero-padding in enabling translation-equivalence, and pooling in
its translation-invariance driven nature, we show that with similar number of
free parameters, any deep fully connected networks (DFCNs) can be represented
by DCNNs with zero-padding. This demonstrates that DCNNs with zero-padding is
essentially better than DFCNs in feature extraction. Consequently, we derive
universal consistency of DCNNs with zero-padding and show its translation-
invariance in the learning process. All our theoretical results are verified
by numerical experiments including both toy simulations and real-data running.

###### Index Terms:

Deep learning, deep convolutional neural network, zero-padding, pooling,
learning theory

##  1 Introduction

In the era of big data, machine learning, especially deep learning, has
received unprecedented success in numerous application regions including
computer vision [1], management science [2], finance [3], economics [4], games
[5] and so on. To reveal the mystery behind the success is the recent focus
and will be an eternal task of machine learning, requiring not only to
understand the running mechanism of specific learning schemes, but also to
provide solid theoretical verifications. As shown in Figure 1, a machine
learning scheme can be regarded as a two-step strategy that searches suitable
feature mappings to obtain a sequence of features at first and then finds
appropriate linear combinations of the obtained features for the learning
purpose. In this way, the main difference of learning schemes lies in the
different feature mappings. For example, the kernel approach [6] utilizes the
kernel-based mapping to extract features and deep learning [7] employs deep
neural networks (deep nets for short) for feature representation.

Figure 1: The steps of feature extraction of classical machine learning and
deep learning.

The great success of deep learning [8, 9, 7] implies that deep nets are
excellent feature extractors in representing the translation invariance [10],
rotation invariance [11], calibration invariance [12], spareness [13],
manifold structure[14], among others [15]. Furthermore, avid research
activities in deep learning theory proved that, equipped with suitable
structures, deep nets outperform the classical shallow neural networks
(shallow nets for short) in capturing the smoothness [16], positioning the
input [17], realizing the sparseness in frequency and spatial domains [18,
19], reflecting the rotation-invariance [20], grasping the composite-structure
[21], group-structure [22], manifold-structure [23] and hierarchy-structure
[24]. These encouraging theoretical assertions together with the notable
success in application seem that the running mechanism of deep learning is put
on the order of the day.

The problem is, however, that there are three challenged gaps between the
established theoretical results and desired running mechanisms of deep
learning. At first, the structures of deep nets in theoretical analysis and
applications for the same purpose are totally different. For example, to
embody the rotation invariance, practicioners focus on tailoring the network
to obtain a structured deep nets to automatically extracting the feature [11]
while theoretical analysis devotes to proving the existence of a deep fully
connected neural network (DFCN) via tuning the weights. Then, as the product
of full matrix frequently does not obey to the commutative law, DFCN requires
strict orders of the extracted features, which consequently yields that the
features extracted by DFCNs cannot be combined directly to explain the success
of deep learning in practice. At last, practicioners are willing to encode the
a-priori knowledge into the training process via setting suitable network
structure which is beyond the scope of existing theoretical analysis. The
above three gaps between existing theoretical analysis and application
requirements, highlighted in Figure 2, significantly dampens the spirits of
both practicioner and theoretical analysts, making them drive in totally
different directions in understanding deep learning.

Figure 2: Three challenged gaps between the established theoretical results
and desired running mechanisms of deep learning.

Noting these gaps, some theoretical analysis has been carried out on analyzing
the learning performance of structured deep nets with the intuition that there
exist some features that can be extracted by the structure of deep nets.
Typical examples includes [20] for deep nets with tree structures, [25] for
deep convolutional neural networks (DCNN) with multi-channel, [26] for DCNN
with resnet-type structures, and [27, 28] for deep convolutional neural
networks (DCNN) with zero-padding. However, these results seem not to provide
sufficient advantages of structured deep neural networks since they neither
present solid theoretical explanations on why structured deep nets outperform
others, nor give theoretical guidances on which features can be extracted by
specific network structures. This motivates our study in this paper to show
why and when DCNN performs better than DFCN and how to tailor the structure
(zeor-padding, depth, filter length and pooling scheme) of DCNN for a specific
learning task.

Figure 3: Zero-padding and network structure.

We study the performance of DCNN with one-dimensional and one-channel
convolution in feature extraction and learning. As shown in Figure 3, if there
is not any zero-padding imposed to the convolution structure, DCNN then
behaves a contracting nature (we call such DCNN as cDCNN for short) in the
sense that the width decreases with respect to the depth, prohibiting its
universality in feature extraction [29, 30]. Therefore, without the help of
other structures such as fully-connected layers and zero-padding, there are
numerous features that cannot be extracted by cDCNN. Noticing that additional
fully-connected layer may destroy the convolutional structure of cDCNN, we are
interested in conducting zero-padding as Figure 3 and making the network
possess an expansive nature. We call DCNN with zero-padding like Figure 3 as
eDCNN and study the performance of eDCNN in feature extraction and learning
via considering the following three problems:

$\diamond$ (P1): What is the role of zero-padding in eDCNN?

$\diamond$ (P2): How to specify the pooling scheme to improve the performance
of eDCNNs?

$\diamond$ (P3): Why and when are DCNNs better than widely studied deep fully
connected networks (DFCNs)?

As shown in Figure 3, zero-padding enlarges the size of the extracted features
to guarantee the universality, and therefore plays a crucial role in DCNN.
Problem (P1) indeed refers to how to explore the important role of zero-
padding in enhancing the representation and learning performances of cDCNN. It
is well known that pooling drives the converse direction as zero-padding to
shrink the size via designing suitable sub-sampling mechanism. Problem (P2)
focuses on the role of pooling in eDCNN and studies its theoretical advantages
in improving the generalization performance and enabling the feature
extraction of eDCNN. With the help of a detailed analysis of the roles of
zero-padding and pooling, theoretical guarantees for the pros and cons of
eDCNN, compared with the cDCNN and DFCN, should be illustrated, which is the
main topic of problem (P3). In a nutshell, the above three problems are
crucial to understand the running mechanisms of structured deep nets and
probing into the reason why structured deep nets perform better than DFCN.

Our purpose in this paper is to provide answers to the aforementioned three
problems from the representation theory [15] and statistical learning theory
viewpoints [31, 32]. The main contributions can be concluded as follows:

$\bullet$ Methodology development: We study the role of zero-padding and
pooling in eDCNN and find that with suitable pooling strategy, eDCNN possesses
the translation invariance and is universal in feature extraction. These
findings show that eDCNN is better than DFCN in encoding the translation
invariance in the network structure without sacrificing its peformance in
extracting other features, and is also better than cDCNN in term of
universality in approximation and learning. Therefore, we actually provide an
alternative network structure for deep learning with more clear running
mechanisms and excellent performances in feature extraction and learning.

$\bullet$ Theoretical novelty: We provide solid theoretical verifications on
the excellent performance of eDCNN in feature extraction and learning. From
the feature extraction viewpoint, we prove that zero-padding enables eDCNN to
be translation-equivalent and pooling enables it to be translation-invariant.
Furthermore, we prove that encoding the translation-equivalence (or
translation invariance) into the network, eDCNN performs not worse than DFCN
in extracting other features in the sense that with similar number of free
parameters, eDCNN can approximate DFCN within an arbitrary accuracy but not
vice-verse. From the learning theory perspective, we prove that eDCNN is
capable of yielding universally consistent learner and encoding the
translation-invariance.

$\bullet$ Application guidance: By the aid of theoretical analysis, we conduct
several numerical simulations on both toy data and real-world applications to
show the excellent performance of eDCNN in feature extraction and learning.
Our numerical results show that eDCNN always perform not worse than DFCN and
cDCNN. Furthermore, if the data process some translation-invariance, then
eDCNN is better than other two networks, which provides a guidance on how to
use eDCNN.

In summary, we study the feature extraction and learning performances of eDCNN
and provide theoretical answers to problems (P1-P3). For (P1), we prove that
zero-padding enables DCNN to reflect the translation-equivalence and improve
the performance of DCNNs in feature extraction. For (P2), we show that pooling
plays a crucial role in reducing the number of parameters of eDCNN without
sacrificing its performance in feature extraction. For (P3), we exhibit that
if the learning task includes some translation-equivalence or translation-
invariance, eDCNN is essentially better than other network structures, showing
why and when DCNN outperforms DFCN.

The rest of the paper is organized as follows. In the next section, we
introduce eDCNN. In Section 3, we study the role of zero-padding in eDCNN. In
Section 4, theoretical analysis is carried out to demonstrate the importance
of pooling in eDCNN. In Section 5, we compare eDCNN with DFCN in feature
extraction. In Section 6, we verify the universal consistency of eDCNN and
show its translation-invariance in the learning process. In Section 7,
numerical experiments concerning both toy simulations and real-world
applications are made to illustrate the excellent performance of eDCNN and
verify our theoretical assertions. In the last section, we draw some
conclusions of our results. All proofs of the theoretical assertions are
postponed to Supplementary Material of this paper.

##  2 Deep Convolutional Neural Networks

Let $L\in\mathbb{N}$ be the depth of a deep net, $d_{0}=d$ and
$d_{\ell}\in\mathbb{N}$ be the width of the $\ell$-th hidden layer for
$\ell=1,\dots,L$. For any $\vec{v}\in\mathbb{R}^{d_{\ell-1}}$, define
$\mathcal{J}_{\ell,W^{\ell},\vec{b}^{\ell}}:\mathbb{R}^{d_{\ell-1}}\rightarrow\mathbb{R}^{d_{\ell}}$
as the affine operator by

$\mathcal{J}_{\ell,W^{\ell},\vec{b}^{\ell}}(x):=W^{\ell}x+\vec{b}^{\ell},$ (1)

where $W^{\ell}$ is a $d_{\ell}\times d_{\ell-1}$ weight matrix and
$\vec{b}^{\ell}\in\mathbb{R}^{d_{\ell}}$ is a bias vector. Deep nets with
depth $L$ is then defined by

$\mathcal{N}_{d_{1},\dots,d_{L}}(x)=\vec{a}^{L}\cdot\sigma\circ\mathcal{J}_{L,W^{L},\vec{b}^{L}}\circ\sigma\circ\dots\circ\sigma\circ\mathcal{J}_{1,W^{1},\vec{b}^{1}}(x),$
(2)

where $\vec{a}^{L}\in\mathbb{R}^{d_{L}}$, $\sigma(t):=\max\\{t,0\\}$ is the
ReLU function, $\sigma(x)=(\sigma(x^{(1)}),\dots,\sigma(x^{(d)}))^{T}$ for
$x=(x^{(1)},\dots,x^{(d)})^{T}$ and $f\circ g(x)=f(g(x))$. Denote by
$\mathcal{H}_{d_{1},\dots,d_{L}}$ the set of deep nets with depth $L$ and
width $d_{\ell}$ in the $\ell$-th hidden layer. In this way, deep learning can
be regarded as a learning scheme that utilizes the feature mapping
$\vec{V}_{d_{1},\dots,d_{L}}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d_{L}}$
defined by

$\vec{V}_{d_{1},\dots,d_{L}}(x):=\sigma\circ\mathcal{J}_{L,W^{L},\vec{b}^{L}}\circ\sigma\circ\dots\circ\sigma\circ\mathcal{J}_{1,W^{1},\vec{b}^{1}}(x)$
(3)

to extract data features at first and then uses a simple linear combination of
the extracted features for a learning purpose. The quality of learning is then
determined by the feature mapping $\vec{V}_{d_{1},\dots,d_{L}}$, which depends
on the depth $L$, width $d_{\ell}$, bias vectors $\vec{b}^{\ell}$, and more
importantly, the structure of weight matrices $W^{\ell}$, $\ell=1,\dots,L$.
The structure of the weight matrices actually determines the structure of deep
nets. For example, full weight matrices correspond to DFCNs [16], sparse
weight matrices are related to deep sparsely connected networks (DSCNs) [33],
Toeplitz-type weight matrices refer to eDCNNs. Figure 4 presents four
structures of deep nets and the associated weight matrices.

Figure 4: Four structures of eDCNN, cDCNN, DFCN and DSCN.

The performances of DFCN and DSCN in feature extraction and learning have been
extensively studied in theory[16, 33, 19, 18, 21, 34, 24, 22, 17, 35, 36, 23].
In particular, [23] proved that DFCN succeeds in capturing the manifold
structure of the inputs; [36] verified that DFCN is capable of realizing
numerous features such as the locality and $\ell_{1}$-radial, and [33] showed
that DSCN benefits in extracting the piece-wise smooth features of the data.
Despite these encouraging developments, there is a crucial challenge that the
derived provable properties of DFCNs and DSCNs require totally different
structures for different learning tasks, not only in different width and
depth, but also in the structure of weight matrices. This makes the running
mechanism of deep learning still a mystery, since it is quite difficult to
design a unified DFCN or DSCN structure suitable for all learning tasks to
embody the power of depth.

Noting this, cDCNN comes into researchers’ insights due to its unified
structure and popularity in practice [37]. For $s\in\mathbb{N}$, let
$\vec{w}=(w_{j})_{j=-\infty}^{\infty}$ be a filter of length $s$, i.e.
$w_{j}\neq 0$ only for $0\leq j\leq s$. For any
$\vec{v}\in\mathbb{R}^{d^{\prime}}$ and $d^{\prime}\in\mathbb{N}$, define the
one-dimensional and one-channel convolution without zero padding by

$(\vec{w}\star\vec{v})_{j}=\sum_{k=j-s}^{j}w_{j-k}v_{k+s},\qquad
j=1,\dots,d^{\prime}-s.$ (4)

For $\vec{v}\in\mathbb{R}^{d_{\ell-1}}$ and $d_{\ell}=d_{\ell-1}-s$, define
the contracting convolution operator
$\mathcal{C}^{\star}_{\ell,\vec{w}^{\ell},\vec{b}^{\ell}}:\mathbb{R}^{d_{\ell-1}}\rightarrow\mathbb{R}^{d_{\ell}}$
as

$\mathcal{C}_{\ell,\vec{w}^{\ell},\vec{b}^{\ell}}^{\star}(\vec{v}):=\vec{w}^{\ell}\star\vec{v}+\vec{b}^{\ell}$
(5)

for $\vec{w}^{\ell}$ supported on $\\{0,1,\dots,s\\}$ and bias vector
$\vec{b}^{\ell}\in\mathbb{R}^{d_{\ell}}$. Then cDCNN is defined by

$\mathcal{N}_{L,s}^{\star}(x):=\vec{a}_{L}\cdot\sigma\circ\mathcal{C}_{L,\vec{w}_{L},\vec{b}_{L}}^{\star}\circ\sigma\circ\dots\circ\sigma\circ\mathcal{C}^{\star}_{1,\vec{w}_{1},\vec{b}_{1}}(x).$
(6)

Due to the contracting nature of cDCNN, we get $d_{\ell}\leq d$ for all
$\ell=1,\dots,L$. This makes cDCNN even not be universal in approximation,
since the smallest width of a deep net required to guarantee the universality
is $d+1$ according to the minimal-width theory of deep nets approximation
established in [29]. As a result, though cDCNN is able to extract certain
specific features, it is impossible to use the unified cDCNN structure for all
learning tasks. A feasible remedy for this drawback of cDCNN is to add several
fully connected layers after the convolutional layers to enhance the
versatility. The problem is, however, that how to set the width and depth of
the fully connected layers becomes a complication, making the network
structure also unclear. Furthermore, the added fully connected layers may
destroy several important properties such as the translation-equivalence,
translation-invariance and calibration invariance of cDCNNs [10], making it
difficult to theoretically analyze the role of convolution operator (5) in the
learning process.

Another approach to circumvent the non-universality of cDCNN is to use zero-
padding to widen the network, just as [28, 38, 30] did. For any
$\vec{v}\in\mathbb{R}^{d^{\prime}}$, define

$(\vec{w}*\vec{v})_{j}=\sum_{k=1}^{d^{\prime}}w_{j-k}v_{k},\qquad
j=1,\dots,d^{\prime}+s.$ (7)

Compared with (4), zero-padding is imposed in the convolution operation,
making the convolution defined by (7) have an expansive nature, just as Figure
3 purports to show. For $\vec{v}\in\mathbb{R}^{d_{\ell-1}}$ and
$d_{\ell}=d_{\ell-1}+s$, denote the expansive convolution operator
$\mathcal{C}_{\ell,\vec{w}^{\ell},\vec{b}^{\ell}}:\mathbb{R}^{d_{\ell-1}}\rightarrow\mathbb{R}^{d_{\ell}}$
by

$\mathcal{C}_{\ell,\vec{w}^{\ell},\vec{b}^{\ell}}(\vec{v}):=\vec{w}^{\ell}*\vec{v}+\vec{b}^{\ell}$
(8)

for $\vec{w}^{\ell}$ supported on $\\{0,1,\dots,s\\}$ and bias vector
$\vec{b}^{\ell}\in\mathbb{R}^{d_{\ell}}$. eDCNN is then mathematically defined
by

$\mathcal{N}_{L,s}(x)=\vec{a}_{L}\cdot\vec{V}^{eDCNN}_{d_{1},\dots,d_{L}},$
(9)

where

$\vec{V}^{eDCNN}_{d_{1},\dots,d_{L}}:=\sigma\circ\mathcal{C}_{L,\vec{w}_{L},\vec{b}_{L}}\circ\sigma\circ\dots\circ\sigma\circ\mathcal{C}_{1,\vec{w}_{1},\vec{b}_{1}}(x).$
(10)

Denote by $\mathcal{H}_{L,s}$ the set of all eDCNNs formed as (9).

It is well known that DFCNs do not always obey the commutative law in the
sense that there are infinitely many full matrices $A$ and $B$ such that
$AB\neq BA$. This means that the order of the affine operator defined by (1)
affects the quality of feature extraction significantly and implies that there
must be a strict order for DFCNs to extract different features. Changing the
order of hidden layers thus leads to totally different running mechanisms of
DFCNs. Differently, the convolutional operators defined in (4) and (7) succeed
in breaking through the above bottlenecks of the affine operator by means of
admitting the commutative law.

######  Lemma 1.

Let $s\in\mathbb{N}$. If $\vec{w}^{1},\vec{w}^{2}$ are supported on
$\\{0,\dots,s\\}$, then

$\vec{w}^{1}\otimes\vec{w}^{2}=\vec{w}^{2}\otimes\vec{w}^{1},$ (11)

where $\otimes$ denotes either the contracting convolution $\star$ in (4) or
the expansive convolution $*$ in (7).

The commutative law established in Lemma 1 shows that DCNN is able to extract
different features without considering which feature should be extracted at
first, which is totally different from DFCN and presents the outperformance of
the convolutional structure over the classical inner product structure in DFCN
derived from the affine mapping (1).

We then show the advantage of eDCNN over cDCNN in approximation. Due to the
contracting nature, the depth of cDCNN is always smaller than $d/s$, making
the maximal number of free parameters of cDCNN not larger than $d$, which is
impossible to guarantee the universality [29]. The following lemma provided in
[28, Theorem 1] illustrates the universality of eDCNN.

######  Lemma 2.

Let $2\leq s\leq d$. There holds

$\lim_{L\rightarrow\infty}\inf_{g\in\mathcal{H}_{L,s}}\|f-g\|_{C(\mathbb{I}^{d})}=0,\qquad\forall
f\in C(\mathbb{I}^{d}).$

The universality of eDCNN shows that with sufficiently many hidden layers and
appropriately tuned weights, eDCNN can extract any other features, which shows
its advantage over cDCNN in approximation.

##  3 The Power of Zero-Padding in feature extraction

In this section, we analyze the role of zero-padding to answer problem (P1).
Our study starts with the bottleneck of the contracting convolution structure
(4) in representing the translation-equivalence. We say that a $d$-dimensional
vector $\vec{v}_{p,d,j}$ is supported on $\\{j,j+1,\dots,j+p-1\\}$ with
$j+p\leq d+1$, if

$\vec{v}_{p,d,j}=(\overbrace{0,\dots,0}^{j-1},v_{1},\dots,v_{p},\overbrace{0,\dots,0}^{d-p-j+1})^{T}.$
(12)

Let $A_{j,d}$ be the $d\times d$ matrix whose $(j+i,1+i)$\- components with
$i=0,1,\dots,d-j$ are 1 while the others are 0. Then, it is easy to check that
$A_{j,d}$ is a translation operator (or matrix) satisfying

$A_{j,d}\circ\vec{v}_{p,d,1}=\vec{v}_{p,d,j}.$ (13)

We present definitions of translation-equivalence and translation-invariance
[10] as follows.

######  Definition 1.

Let
$\mathcal{G}_{d^{\prime},d}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d^{\prime}}$
be a linear operator and $A_{j,d}$ be the translation operator satisfying
(13). If

$\mathcal{G}_{d^{\prime},d}\circ
A_{j,d}\circ\vec{v}_{p,d,1}=A_{j,d^{\prime}}\circ\mathcal{G}_{d^{\prime},d}\circ\vec{v}_{p,d,1},\quad\forall
j=1,\dots,d-p,$

then $\mathcal{G}_{d^{\prime},d}$ is said to be translation-equivalent.
Furthermore, if

$\mathcal{G}_{d^{\prime},d}\circ
A_{j,d}\circ\vec{v}_{p,d,1}=\mathcal{G}_{d^{\prime},d}\circ\vec{v}_{p,d,1},\quad\forall
j=1,\dots,d-p,$

then the linear operator $\mathcal{G}_{d^{\prime},d}$ is said to be
translation-invariant.

Figure 5: Translation-invariance of image recognition.

Translation-equivalence and translation-invariance are important features in
numerous application regions [10, 13]. Taking image recognition for example,
as shown in Figure 5, a judgement of the cat is easily to be made independent
of the location of inputs, showing the translation-invariance of the learning
task. Unfortunately, the classical cDCNN is not always capable of encoding the
translation-equivalence into the network structure, just as the the following
lemma exhibits.

######  Lemma 3.

Let $d^{\prime}\in\mathbb{N}$, $1\leq p\leq d^{\prime}$ and $2\leq s\leq
d^{\prime}$. There exist a $\vec{w}^{\ell}$ supported on $\\{0,1,\dots,s\\}$
and some $j\in\\{1,\dots,d^{\prime}-p+1\\}$ such that

$A_{j,d^{\prime}-s}\circ(\vec{w}^{\ell}\star\vec{v}_{p,d^{\prime},1})\neq\vec{w}^{\ell}\star(A_{j,d^{\prime}}\circ\vec{v}_{p,d^{\prime},1}).$

It is easy to check that there is a $\vec{w}^{\ell}$ supported on
$\\{0,1,\dots,s\\}$ such that there are $s$ non-zero items in
$\vec{w}^{\ell}\star\vec{v}_{p,d^{\prime},1}$ and consequently $s$ non-zero
items in
$A_{j,d^{\prime}-s}\circ(\vec{w}^{\ell}\star\vec{v}_{p,d^{\prime},1})$, but
for $s\leq j\leq d^{\prime}-p-s$ there are $2s-1$ non-zero items in
$\vec{w}^{\ell}\star(A_{j,d^{\prime}}\circ\vec{v}_{p,d^{\prime},1})$, which
proves the above lemma directly. Lemma 3 does not show that cDCNN always
cannot encode the translation-invariance, but demonstrates that cDCNN limits
to do this when the support of the target lies on the edges. Our result in
this section is to show that zero-padding defined by (7) is capable of
breaking through the above drawback of cDCNN.

######  Proposition 1.

Let $L\in\mathbb{N}$, $1\leq p\leq d$, $2\leq s\leq d$, $d_{0}=d$,
$d_{\ell}=d+\ell s$ and $\vec{w}^{\ell}$ be supported on $\\{0,1,\dots,s\\}$,
$\ell=1,\dots,L$. For any $1\leq j\leq d-p+1$, there holds

$\displaystyle\vec{w}^{L}*\dots*\vec{w}^{1}*(A_{j,d}\circ\vec{v}_{p,d,1})$
(14) $\displaystyle=$
$\displaystyle\vec{w}^{L}*\dots*(A_{j,d_{1}}\circ(\vec{w}^{1}*\vec{v}_{p,d,1}))$
$\displaystyle=$
$\displaystyle\dots=A_{j,d_{L}}\circ(\vec{w}^{L}*\dots*\vec{w}^{1}*\vec{v}_{p,d,1}).$

The proof of Proposition 1 will be given in Appendix. Proposition 1 shows that
if a vector $v_{p,d,j}$ is translated to $v_{p,d,j^{\prime}}$ for
$j^{\prime}\neq j$, then the output of the convoluted vector
$\vec{w}^{L}*\dots*\vec{w}^{1}*\vec{v}_{p,d,j}$ is also translated with step
$j^{\prime}-j$. This illustrates that without tuning weights, the expansive
convolution structure succeeds in encoding the translation-equivalence feature
of the data, showing its outperformance over the inner product structure in
DFCNs and the contracting convolutional structure in cDCNNs.

##  4 The Importance of Pooling in eDCNN

In this section, we borrow the idea of the location-based pooling (down-
sampling) scheme from [38] to equip eDCNN to reduce the size of extracted
features and enhance its performance of encoding the translation-invariance,
simultaneously. For any $d^{\prime}\in\mathbb{N}$, the location-based pooling
scheme
$\mathcal{S}_{d^{\prime},u,j}:\mathbb{R}^{d^{\prime}}\rightarrow\mathbb{R}^{[d^{\prime}/u]}$
for a vector $\vec{v}\in\mathbb{R}^{d^{\prime}}$ with scaling parameter $u$
and location parameter $0\leq j\leq d^{\prime}$ is defined by

$\mathcal{S}_{d^{\prime},u,j}(\vec{v})=(v_{ku+j})_{k=1}^{[d^{\prime}/u]},$
(15)

where $[a]$ denotes the integer part of the real number $a$ and $v_{ku+j}=0$.
For any $d\in\mathbb{N}$, if we set $v_{ku+j}=0$ for $ku+j>d$, then
$\mathcal{S}_{d^{\prime},u,j}$ can be regarded as a operator from
$\mathbb{R}^{d^{\prime}}$ to $\mathbb{R}^{d}$. As shown in Figure 6 ,
$\mathcal{S}_{d^{\prime},u,j}$ devotes to selecting $[d^{\prime}/u]$ neurons
from $d^{\prime}$ features and the selection rule is only based on the
location of the neurons, which is totally different from the classical max-
pooling that selects neurons with the largest value or the average-pooling
which synthesizes the averaged value of several neurons.

Figure 6: Location-based pooling.

With the proposed location-based pooling scheme, we show that eDCNN succeeds
in encoding the translation-equivalence (or translation-invariance) without
sacrificing the performance of DCFN in extracting other features. Given
$d^{\prime},\tilde{d},\ell\in\mathbb{N}$ satisfying $\tilde{d}=d^{\prime}+\ell
s$, $\vec{b}\in\mathbb{R}^{d^{\prime}}$ and $\vec{w}^{1},\dots,\vec{w}^{L}$
supported on $\\{0,\dots s\\}$ with
$L=\lceil\frac{\tilde{d}d^{\prime}}{s-1}\rceil$, for any
$x\in\mathbb{R}^{d^{\prime}}$, define a multi-layer convolutional operator
with pooling by

$\mathcal{B}_{L,d^{\prime},k}(x):=\mathcal{S}_{\tilde{d},d^{\prime},k}(\vec{w}^{L}*\dots*\vec{w}^{1}*x+\vec{b}).$
(16)

The following proposition is the main result of this section.

######  Proposition 2.

Let $J,d\in\mathbb{N}$, $2\leq s\leq d$, $d_{0}=d$,
$d_{1},\dots,d_{J}\in\mathbb{N}$,
$L_{j}=\lceil\frac{d_{j-1}d_{j}}{s-1}\rceil$, and $x$ be supported on
$\\{k,k+1,\dots,k+p-1\\}$ for some $p,k\in\mathbb{N}$. If
$\vec{V}_{d_{1},\dots,d_{L}}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d_{L}}$
defined by (3) is an arbitrary feature generated by DFCN, then there exist
$\sum_{j=1}^{J}L_{j}$ filter vectors $\\{\vec{w}^{j,\ell}\\}_{\ell=1}^{L_{j}}$
supported on $\\{0,1,\dots,s\\}$ and $J$ bias vectors
$\vec{b}^{j}\in\mathbb{R}^{d_{j}}$, $j=1,\dots,J$ such that for any $1\leq
i\leq d-p+1-k$ there holds

$\displaystyle\vec{V}_{d_{1},\dots,d_{J}}(x)=\sigma\circ\mathcal{B}_{L_{J},d_{J-1},0}\circ\dots\circ\sigma\circ\mathcal{B}_{L_{1},d_{0},0}(x)$
(17)
$\displaystyle=\sigma\circ\mathcal{B}_{L_{J},d_{J-1},0}\circ\dots\circ\sigma\circ\mathcal{B}_{L_{2},d_{1},0}\circ\sigma\circ\mathcal{B}_{L_{1},d_{1},i}(A_{i,d}x).$

Due to the commutative law established in Lemma 1, it is easy to check that
the representation presented in (17) is not unique. Noting that there are

$L_{j}(s+1)=\lceil\frac{d_{j-1}d_{j}}{s-1}\rceil(s+1)\leq 3d_{j}d_{j-1},$

free parameters involved in the multi-layer convolutional structure
$\vec{w}^{j,L_{j}}*\dots*\vec{w}^{j,1}$, which is comparable with those in the
classical inner product structure, i.e., $d_{j}d_{j-1}$, the location-based
pooling scheme is to enable the same size of the affine-mapping and multi-
layer convolutional mapping without sacrificing its performance in feature
extraction. Therefore, Proposition 2 yields that acting as a feature
extractor, the convolutional structure together with suitable pooling schemes
outperforms the classical inner product structure in DFCN in the sense that
the former succeeds in capturing the translation-invariance structure without
losing the performance of DFCN in extracting other features. A direct
corollary of the above proposition is the following translation-invariance of
eDCNN with pooling.

######  Corollary 1.

Let $L\in\mathbb{N}$, $2\leq s\leq d$, $1\leq p\leq d$ and $\vec{w}^{\ell}$
with $\ell=1,\dots,L$ be supported on $\\{0,1,\dots,s\\}$. Then for any $1\leq
j,j^{\prime}\leq d-p+1$ with $j^{\prime}\neq j$, there holds

$\mathcal{S}_{d_{L},d,j}(\vec{w}^{L}*\dots*\vec{w}^{1}*\vec{v}_{p,d,j})=\mathcal{S}_{d_{L},d,j^{\prime}}(\vec{w}^{L}*\dots*\vec{w}^{1}*\vec{v}_{p,d,j^{\prime}}).$
(18)

It follows from Corollary 1 that a suitable pooling scheme not only reduces
the free parameters in a network but also endows the network with some
important property. Therefore, if the convolutional structure is employed in
the network, designing an appropriate pooling scheme is crucial to improve its
performance in feature extraction and learning. Another direct corollary of
Proposition 2 is the following comparison between eDCNN with pooling and
shallow nets.

######  Corollary 2.

Let $2\leq s\leq d$, $n\in\mathbb{N}$, $x$ be supported on
$\\{j,j+1,\dots,j+p-1\\}$ for some $p,j\in\mathbb{N}$, $\sigma(Wx+\vec{b})$ be
a feature generated by a shallow net with $n\times d$ weight matrix $W$ and
$n$ dimensional bias vector $\vec{b}$. Then, there exist
$L^{*}=\lceil\frac{nd}{s-1}\rceil$ filter vectors
$\\{\vec{w}^{\ell}\\}_{\ell=1}^{L^{*}}$ supported on $\\{0,1,\dots,s\\}$and a
bias vector $\vec{b}^{\prime}\in\mathbb{R}^{n}$ such that for any $1\leq k\leq
d-p+1-j$, there holds

$\displaystyle\sigma(Wx+\vec{b})=\sigma\circ\mathcal{B}_{L^{*},d,0}(x)=\sigma\circ\mathcal{B}_{L^{*},d,k}(A_{k,d}x)),$

where $A_{k,d}$ is the translation matrix satisfying (13).

Corollary 2 shows that convolutional structures and appropriate pooling scheme
can provide the translation-invariance without sacrificing the feature
extraction capability of the classical shallow nets. It implies that no matter
where $x$ is supported, the multi convolutional structure together with
suitable location-based pooling scheme yields the same output of high quality.

##  5 Performance of eDCNNs in Feature Extraction

As discussed in the above two sections, zero-padding and location-based
pooling play important roles in improving the performance of the convolutional
structure in feature extraction. However, the network provided in Proposition
2 uses both bias vectors and ReLU activation functions and is thus different
from the eDCNN defined by (9). In this section, we show that adding suitable
bias vectors enables to produce a unified eDCNN structure formed as (9). We
then present a comparison between eDCNN and DFCN in feature extraction.

Since adopting different bias vectors in different neurons in the same layer
prohibits the translation-equivalence of eDCNN, we study a subset of
$\mathcal{H}_{L,s}$ whose elements of the bias vector in the same layer are
the same. For any $d^{\prime}_{0}=d^{\prime}\in\mathbb{N}$ and
$d_{\ell}^{\prime}=d^{\prime}+\ell s$, define the restricted convolution
operator by

$\mathcal{C}^{R}_{\ell,\vec{w}^{\ell},b^{\ell}}(x):=\vec{w}^{\ell}*x+b^{\ell}{\bf
1}_{d^{\prime}_{\ell}}$ (19)

for $\vec{w}^{\ell}$ supported on $\\{0,1,\dots,s\\}$, $b^{\ell}\in\mathbb{R}$
and
$\mathbf{1}_{d^{\prime}_{\ell}}=(1,\dots,1)^{T}\in\mathbb{R}^{d^{\prime}_{\ell}}$.
Define further the restricted eDCNN feature-extractor from
$\mathbb{R}^{d^{\prime}}$ to $\mathbb{R}^{d^{\prime}_{\ell}}$ by

$\vec{V}_{\ell}^{s,R}(x):=\sigma\circ\mathcal{C}^{R}_{\ell,\vec{w}^{\ell},{b}^{\ell}}\circ\sigma\circ\dots\circ\sigma\circ\mathcal{C}^{R}_{1,\vec{w}^{1},{b}^{1}}(x).$
(20)

Denote by

$\displaystyle\vec{V}_{\ell}^{s,R,d^{\prime},j}(x):=\mathcal{S}_{d^{\prime}_{\ell},d^{\prime}_{0},j}\circ\sigma\circ\mathcal{C}_{\ell,\vec{w}^{\ell},\vec{b}^{\ell}}\circ\sigma\circ\mathcal{C}^{R}_{\ell-1,\vec{w}^{\ell-1},{b}^{\ell-1}}$
$\displaystyle\circ\sigma\circ\mathcal{C}^{R}_{\ell-2,\vec{w}^{\ell-2},{b}^{\ell-2}}\circ\dots\circ\sigma\circ\mathcal{C}^{R}_{1,\vec{w}^{1},{b}^{1}}(x)$
(21)

the restricted eDCNN feature-extractor with depth $\ell$, filter length $s$,
location-based pooling at the $d_{\ell}$ layer with pooling parameter
$d^{\prime}j\in\mathbb{N}$. It should be highlighted that when pooling
happens, that is, in the $\ell$-th layer, we use the convolutional operator
(8) rather than the restricted one (19). In the following theorem, we show
that eDCNN with pooling performs not worse than shallow nets with similar
number of parameters in feature extraction but succeeds in encoding the
translation-invariance.

######  Theorem 1.

Let $2\leq s\leq d$, $n\in\mathbb{N}$, $L^{*}=\lceil\frac{nd}{s-1}\rceil$,
$d_{0}=d$, and $d_{\ell}=d_{\ell-1}+s$. For any $W\in\mathbb{R}^{n\times d}$
and $\vec{\theta}\in\mathbb{R}^{n}$, there exist $b^{\ell}\in\mathbb{R}$ for
$1\leq\ell\leq L^{*}-1$, $\vec{b}^{L^{*}}\in\mathbb{R}^{d_{L^{*}}}$ and
$L^{*}$ filter vectors $\vec{w}^{\ell}$ supported on $\\{0,1,\dots,s\\}$ such
that

$\displaystyle\sigma(Wx+\vec{\theta})=\vec{V}_{L^{*}}^{s,R,d,0}(x)$ (22)

If in addition $x$ is supported on $\\{j,j+1,\dots,j+p-1\\}$ for some
$p,j\in\mathbb{N}$, then for any $1\leq k\leq d-p+1$, there holds

$\displaystyle\vec{V}_{L^{*}}^{s,R,d,0}(x)=\vec{V}_{L^{*}}^{s,R,d,k}(A_{k,d}x).$
(23)

Theorem 1 presents three advantages of eDCNN over shallow nets. At first, as
far as the feature extraction is concerned, eDCNN performs not worse than
shallow nets in the sense that it can exactly represent any features extracted
by shallow nets with comparable free parameters. Then, it follows from (23)
that with suitable pooling mechanism, eDCNN succeeds in encoding the
translation-invariance into the structure without tuning weights, which is
totally different from other network structures. Finally, it can be derived
from (22) and (23) that even with the structure constraints, the approximation
capability of eDCNN is at least not worse than shallow nets. In particular,
denote by

$\mathcal{H}_{\ell}^{s,R,d,j}:=\left\\{h(x)=\vec{a}\cdot\vec{V}_{\ell,\ell-1}^{s,R,d,0}(x):\vec{a},\vec{b}^{\ell}\in\mathbb{R}^{n},b^{k}\in\mathbb{R}\right\\}$
(24)

the set of restricted eDCNN with pooling defined by (5) with
$\\{\vec{w}^{k}\\}_{k=1}^{\ell}$ being supported on $\\{0,1,\dots,s\\}$. We
can derive the following corollary from Theorem 1 directly.

######  Corollary 3.

Let $2\leq s\leq d$, $n\in\mathbb{N}$, $L^{*}=\lceil\frac{nd}{s-1}\rceil$,
$d_{0}=d$ and $d_{\ell}=d_{\ell-1}+s$. Then, for any $f\in C(\mathbb{I}^{d})$,
we have

$\mbox{dist}(f,\mathcal{H}_{\ell}^{s,R,d,j})\leq\mbox{dist}(f,\mathcal{H}_{n}),$
(25)

where
$\mbox{dist}(f,\mathcal{H}):=\inf_{g\in\mathcal{H}}\|f-g\|_{C(\mathbb{I}^{d})}$
denotes the distance between the function $f$ and the set $\mathcal{H}$ in
$C(\mathbb{I}^{d})$ and $\mathcal{H}_{n}$ is the set of shallow nets with $n$
neurons in the hidden layer.

Theorem 1 and Corollary 3 illustrate the outperformance of eDCNN over shallow
nets. In the following, we aim to compare eDCNN with DFCN in feature
extraction. The following theorem is our second main result.

######  Theorem 2.

Let $2\leq s\leq d$, $L\in\mathbb{N}$,
$d_{1}^{*},\dots,d_{L}^{*}\in\mathbb{N}$ and $d_{0}^{*}=d$. If
$L_{\ell}=\lceil\frac{d^{*}_{\ell}d^{*}_{\ell-1}}{s-1}\rceil$ for
$\ell=1,2,\dots,L$, then for any $\vec{V}_{d_{1}^{*},\dots,d_{L}^{*}}(x)$
defined by (3), there exist filter sequences
$\\{\vec{w}_{\ell,j}\\}_{1,1}^{L,d_{L_{\ell}}}$ with
$d_{L_{\ell}}=d+L_{\ell}s$ supported on $\\{0,1,\dots,s\\},$
$b_{\ell,j}\in\mathbb{R}$ and
$\vec{b}^{L_{\ell}}\in\mathbb{R}^{d^{*}_{L_{\ell}}}$ such that

$\vec{V}_{d_{1}^{*},\dots,d_{L}^{*}}(x)=\vec{V}_{L_{L}}^{s,R,d^{*}_{L-1},0}\circ\vec{V}_{L_{L-1}}^{s,R,d^{*}_{L-2},0}\circ\dots\circ\vec{V}_{L_{1}}^{s,R,d^{*}_{0},0}(x).$
(26)

If in addition $x$ is supported on $\\{j,j+1,\dots,j+p-1\\}$ for some
$p,j\in\mathbb{N}$, then for any $1\leq k\leq d-p+1$, there holds

$\displaystyle\vec{V}_{L_{L}}^{s,R,d^{*}_{L-1},0}\circ\vec{V}_{L_{L-1}}^{s,R,d^{*}_{L-2},0}\circ\dots\circ\vec{V}_{L_{1}}^{s,R,d^{*}_{0},0}(x)$
$\displaystyle=$
$\displaystyle\vec{V}_{L_{L}}^{s,R,d^{*}_{L-1},0}\circ\vec{V}_{L_{L-1}}^{s,R,d^{*}_{L-2},0}\circ\dots\circ\vec{V}_{L_{1}}^{s,R,d^{*}_{0},k}(A_{k,d}x).$

It should be mentioned that the only difference between eDCNN for shallow nets
and eDCNN for DFCN is the number of pooling. In fact, to represent an
$L$-layer DFCN, it requires $L$ location-based pooling in eDCNN. Theorem 2
shows that eDCNN with suitable pooling scheme can represent any DFCN with
comparable free parameters, even though eDCNN is capable of encoding the
translation-invariance in the network structure. This demonstrates the
outperformance of eDCNN over DFCN. Denote by
$\mathcal{H}^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}}$ the set
of all eDCNNs formed as

$\vec{a}\cdot\vec{V}_{L_{L}}^{s,R,d^{*}_{L-1},0}\circ\vec{V}_{L_{L-1}}^{s,R,d^{*}_{L-2},0}\circ\dots\circ\vec{V}_{L_{1}}^{s,R,d^{*}_{0},0}(x).$

We obtain from Theorem 2 the following corollary directly.

######  Corollary 4.

Let $2\leq s\leq d$, $L\in\mathbb{N}$,
$d_{1}^{*},\dots,d_{L}^{*}\in\mathbb{N}$ and $d_{0}^{*}=d$. If
$L_{\ell}=\lceil\frac{d^{*}_{\ell}d^{*}_{\ell-1}}{s-1}\rceil$ for
$\ell=1,2,\dots,L^{*}$, then for any $f\in C(\mathbb{I}^{d})$, we have

$\mbox{dist}(f,\mathcal{H}^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}})\leq\mbox{dist}(f,\mathcal{H}_{d^{*}_{1},\dots,d^{*}_{L}}).$
(28)

With the help of the location-based pooling scheme and convolutional
structures, it is easy to check that the number of free parameters involved in
$\mathcal{H}^{s,R,d^{*}_{L_{1}},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}}$ and
$\mathcal{H}_{d^{*}_{1},\dots,d^{*}_{L}}$ are of the same order, which implies
that the approximation capability of the eDCNN is at least not worse than that
of DFCN. The problem is, however, that it is difficult to set the sizes of
pooling since $\\{d_{j}^{*}\\}_{j=1}^{L}$ for a specific learning task is
usually unknown, making them be crucial parameters in eDCNN. The following
corollary devotes to the universal approximation property of eDCNN with
specified $\\{d_{j}^{*}\\}_{j=1}^{L}$.

######  Corollary 5.

Let $2\leq s\leq d$ and $\ell_{1}=\lceil\frac{d(d+1)}{s-1}\rceil$ and
$\ell_{j}=\lceil\frac{(d+1)^{2}}{s-1}\rceil$ for $j\geq 2$. For an arbitrary
$\varepsilon>0$ and any $f\in C(\mathbb{I}^{d})$, there exist an
$L\in\mathbb{N}$ such that

$\mbox{dist}(f,\mathcal{H}^{s,R,d+1,\dots,d+1,0}_{\ell_{L},\dots,\ell_{1}})<\varepsilon.$

Corollary 5 can be derived directly from Corollary 4 and [29] where the
universality of DFCN with fixed width $d+1$ was verified. Corollary 5 shows
that, with the unified structure and specific pooling scheme in the sense that
the pooling is made as soon as the width of the network achieves
$\lceil\frac{(d+1)^{2}}{s-1}\rceil$, just as Figure 7 purports to show, eDCNN
with location-based pooling is universal in approximation.

Figure 7: The unified structure and specific pooling scheme.

##  6  Performance of eDCNN in Learning

In this section, we study the learning performance of eDCNN in terms of
verifying its strongly universal consistency [31, 30]. We conduct our analysis
in the standard least-square regression framework [31, 32] for the sake of
brevity, although our results also hold for other loss functions.

In least-square regression [31, 32], samples in the data set
$D:=\\{z_{i}\\}_{i=1}^{m}:=\\{(x_{i},y_{i})\\}_{i=1}^{m}$ are assumed to be
drawn independently and identically (i.i.d.) from an unknown but definite
probability distribution $\rho$ on $Z:=\mathcal{X}\times\mathcal{Y}$, where
$\mathcal{X}=\mathbb{I}^{d}$, and $\mathcal{Y}\subseteq\mathbb{R}$. The aim is
to learn a function $f_{D}$ based on $D$ to minimize the generalization error
$\mathcal{E}(f):=\int_{\mathcal{Z}}(f(x)-y)^{2}d\rho,$ which is theoretically
minimized by the well known regression function [31]
$f_{\rho}(x):=\int_{\mathcal{Y}}yd\rho(y|x)$. Since $\rho$ is unknown, its
conditional mean $f_{\rho}$ is also unknown. Our aim is then to find an
estimator $f_{D}$ to minimize

$\mathcal{E}(f)-\mathcal{E}(f_{\rho})=\|f-f_{\rho}\|_{L_{\rho_{X}}^{2}}^{2},$
(29)

where $\rho_{X}$ is the marginal distribution of $\rho$ on ${\mathcal{X}}$.

One of the most important properties that a learner should have is that, as
the sample size $m$ grows, the deduced estimator converges to the real
relation between the input and output. This property, featured as the strongly
universal consistency [31], can be defined as follows.

######  Definition 2.

A sequence of regression estimators $\\{f_{m}\\}_{m=1}^{\infty}$ is called
strongly universally consistent, if

$\lim_{m\rightarrow\infty}\mathcal{E}(f_{m})-\mathcal{E}(f_{\rho})=0$

holds with probability one for all Borel probability distributions $\rho$
satisfying $\int_{\mathcal{Y}}y^{2}d\rho(y|x)<\infty$.

In our previous work [30] we show that running empirical risk minimization
(ERM) on eDCNN without pooling yields strongly universally consistent
learners. In this section, we show that imposing pooling scheme on eDCNN can
maintain the strongly universal consistency. For this purpose, we build up the
learner via ERM:

$f^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{D,L_{L},\dots,L_{1}}:={\arg\min}_{f\in\mathcal{H}^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}}}\mathcal{E}_{D}(f),$
(30)

where $\mathcal{E}_{D}(f)=\frac{1}{|D|}\sum_{i=1}^{|D|}(f(x_{i})-y_{i})^{2}$
denotes the empirical risk of $f$. As shown in Definition 2, expect for
$\int_{\mathcal{Y}}y^{2}d\rho(y|x)<\infty$, there is not any other restriction
on $y$, making the analysis be quite difficult. A preferable way is to
consider a truncation operator defined by
$\pi_{M}t=\min\\{M,|t|\\}\cdot\mathrm{sgn}(t)$ on $y$,
$y_{M_{D}}:=\pi_{M_{D}}y$ with $M_{D}\rightarrow\infty$. Therefore, our final
estimator is
$\\{\pi_{M_{D}}f^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{D,L_{L},\dots,L_{1}}\\}_{|D|=1}^{\infty}$.
It should be mentioned that such a truncation operator is widely adopted in
demonstrating the universal consistency for numerous learning schemes [31,
30], including local average regression, linear least squares, shallow neural
networks learning and eDCNN without pooling. The following theorem then
presents sufficient conditions on designing the pooling scheme and selecting
the depth of eDCNN to guarantee the strongly universal consistency.

######  Theorem 3.

Let $\theta\in(0,1/2)$ be an arbitrary real number, $2\leq s\leq d$, and
$L:=L_{D}\in\mathbb{N}$, $d_{1}^{*},\dots,d_{L}^{*}\in\mathbb{N}$ possibly
depending on $|D|$. If $d_{1}^{*},\dots,d_{L}^{*}\geq d+1$,
$\sum_{j=1}^{L}d_{j-1}^{*}d_{j}^{*}\rightarrow\infty$,
$M=M_{D}\rightarrow\infty$, $M^{2}_{D}|D|^{-\theta}\rightarrow 0$ and

$\frac{M_{D}^{4}\left(\sum_{j=1}^{L}d_{j-1}^{*}d_{j}^{*}\right)^{2}\log(L_{D}d^{*}_{\max})\log(M_{D}|D|)}{|D|^{1-2\theta}}\rightarrow
0,$ (31)

then $\pi_{M_{D}}f^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{D,L_{L},\dots,L_{1}}$
is strongly universally consistent. If in addition $x$ is supported on
$\\{j,j+1,\dots,j+p-1\\}$ for some $p,j\in\mathbb{N}$, then for any $1\leq
k\leq d-p+1$, there holds

$\displaystyle\pi_{M_{D}}f^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{D,L_{L},\dots,L_{1}}(x)=\pi_{M_{D}}f^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},k}_{D,L_{L},\dots,L_{1}}(A_{k,d}x).$
(32)

Theorem 3 presents sufficient conditions on the structure and pooling scheme
for verifying the strongly universal consistency of eDCNN. Different from
[30], Theorem 3 admits different pooling schemes to guarantee the universal
consistency. Theorem 3 shows that with arbitrary $L\rightarrow\infty$
location-based pooling operators, eDCNN can reduce the width of network from
infinite to finite. The role of the location-based pooling is not only to trim
the network and consequently reduces the number of parameters, but also to
enhance the translation-invariance of the network structure as shown in (32).
If we set $L=1$, then Theorem 3 is similar as [30, Theorem 1]. If we set
$d_{1}^{*}=\dots=d_{L}^{*}=d+1$, then the condition (31) reduces to

$\frac{M_{D}^{4}L_{D}^{2}\log(L_{D})\log(M_{D}|D|)}{|D|^{1-2\theta}}\rightarrow
0,$ (33)

which shows that eDCNN with the structure in Corollary 5 (or Figure 7) is
universally consistent.

##  7 Numerical Verifications

In this section, we conduct both toy simulations and real data experiments to
verify the excellent performance of eDCNN, compared with cDCNN and DFCN. In
all these simulations, we train the networks with an Adam optimizer for 2000
epochs. The piece-wise learning rates are [0.003, 0.001, 0.0003, 0.0001],
changing at 800, 1200, 1500 epochs. Each experiment is repeated for 10 times
and the outliers that the training loss does not decrease are eliminated and
we report the average loss results. All the following experiments are
conducted on a single GPU of Nvidia GeForce RTX 3090. Codes for our
experiments are available at https://github.com/liubc17/eDCNN_zero_padding.

There are mainly six purposes in our experiments. The first one is to show the
advantage of the expansive convolutional structure in (7) over the inner
structure in DFCN; The second one is to show the outperformance of eDCNN in
extracting the translation-equivalence features, compared with DFCN and cDCNN;
The third one is to evaluate the ability of eDCNN in learning clean data; The
fourth one is to study the performance of eDCNN in learning noisy data; The
fifth one is to show the universal consistency of eDCNN; The final purpose is
to verify the feasibility of eDCNN on two real world data for human activity
recognition and heartbeat classification.

Figure 8: The fitted three functions. “f1” is generated by a 5-layer randomly
initialized cDCNN. “f2” is generated by a 5-layer randomly initialized eDCNN.
“f3” is generated by a 5-layer randomly initialized fully connected network.

###  7.1 Advantages of the expansive convolutional structure

In this simulation, we verify the expansive convolutional structure via
comparing it with the inner structure in DFCN and contracting convolutional
structure in cDCNN. Our basic idea is to show that the expansive convolutional
structure is capable of representing the inner product structure with much
fewer free parameters but not vice-verse. For this purpose, we generate three
implicit functions, denoted as “f1”, “f2” and “f3” respectively, in Figure 8,
where“f1” is generated by a 5-layer randomly initialized cDCNN, “f2” is
generated by a 5-layer randomly initialized eDCNN and “f3” is generated by a
5-layer randomly initialized fully connected network. The only difference
between “f1” and “f2” is that “f2” pads 2 zeros on both side in the
convolution process. For training each function, 900 training samples and 100
test samples are generated. Each sample is a 30-dimension vector with
continuous 5-dimension entries uniformly distributed in [0, 1) and zero for
the others.

TABLE I: The fitting results of 3 functions. Fit function | Network config. | Test Loss | Params.
---|---|---|---
function “f1” | 1-layer fc | 5.96e-3 | 300
1-block multi-conv cDCNN | 5.67e-3 | 16
1-block multi-conv eDCNN | 2.23e-3 | 16
2-layer fc | 7.74e-3 | 400
2-block multi-conv cDCNN | 2.95e-3 | 32
2-block multi-conv eDCNN | 2.40e-3 | 32
function “f2” | 1-layer fc | 1.37e-2 | 300
1-block multi-conv cDCNN | 8.95e-3 | 16
1-block multi-conv eDCNN | 8.66e-3 | 16
2-layer fc | 7.06e-3 | 400
2-block multi-conv cDCNN | 2.89e-3 | 32
2-block multi-conv eDCNN | 2.29e-3 | 32
function “f3” | 1-layer fc | 1.04e-3 | 300
1-block multi-conv cDCNN | 8.30e-3 | 16
1-block multi-conv eDCNN | 1.18e-3 | 16
2-layer fc | 1.16e-3 | 400
2-block multi-conv cDCNN | 7.53e-3 | 32
2-block multi-conv eDCNN | 9.30e-4 | 32

We use multi-level convolutional structures and fully connected structures to
fit the three functions. As shown in Table I, we use 1-layer and 2-layer fully
connected (denoted as “fc”) networks as baselines. We use 1-block and 2-block
multi-level expansive convolutional (denoted as “multi-conv”) structures to
factorize corresponding 1-layer and 2-layer fully connected networks. Each
layer of the used 1-layer and 2-layer fully connected networks has 10 units
and uses ReLU activation and each block of the used 1-block and 2-block multi-
level cDCNN or eDCNN convolutional structures has 5 convolution layers. Each
layer has 1 filter of filter size 3. The former 4 layers do not use bias and
activation. Only after each block, there is a bias and activation. To match
the feature dimension of multi-level eDCNN, a max pooling with pooling size 4
is used after the first block and a max pooling with pooling size 2 is used
after the second block.

There are four interesting phenomenon can be found in Table I: 1) The multi-
level expansive convolutional structure performs at least not worse than the
inner product structure in approximating all three functions with much fewer
parameters, showing that presenting the expansive convolutional structure to
take place of the inner product structure succeeds in reducing the number of
parameters without sacrificing the performance of feature extraction; 2) In
fitting “f1” and “f2” which possesses some translation-equivalence, multi-
level convolutional structures achieve much lower test loss than their inner
product structure counterparts, exhibiting the outperformance of the
convolutional structure in extracting the translation-equivalence; 3) In
fitting “f3”, although 1-block multi-level convolutional structure has
slightly higher test loss than 1-layer“fc”, 2-block multi-level convolutional
structure achieves the least loss. This is mainly due to the fact that “f3” is
generated by fully connected networks and fitting “f3” is easier for the inner
product structure. This phenomena illustrates that with more hidden layers,
inner product can be represented by the multi-convolutional structure, just as
Proposition 2 says; 4) The expansive convolutional structure performs always
better than the contracting convolutional structure, especially for 1-block
setting. The reason for this is that the contracting nature limits the
representing performance of the corresponding network, although it may encodes
some invariance into the structure. All these demonstrates the power of the
expansive convolutional structure and verifies our theoretical assertions in
Section 3 and Section 4.

###  7.2 eDCNNs for translation-equivalence data

In this simulation, we verify the outperformance of eDCNNs in approximating
translation-equivalence functions over DFCNs and cDCNNs. The used translation-
equivalence functions are adapted from “f1” and “f2” in Figure 8, denoted as
“f1m” and “f2m”. The only difference is that “f1m” and “f2m” use a same weight
bias with value 0.01 after each convolutional layer. We use fully connected
networks, cDCNN and eDCNN to fit “f1m” and “f2m”. The depth of the used fully
connected networks, cDCNN and eDCNN for fitting “f1m” and “f2m” is set as 4.
Each fully connected layer has 10 units and uses ReLU activation. Each
convolutional layer of cDCNN and eDCNN has 1 filter of filter size 3 and eDCNN
pads 2 zeros on both side in the convolution process. 900 training samples and
100 test samples are generated for our purpose. Each sample is a 30-dimension
vector with continuous 5-dimension entries uniformly distributed in [0, 1) and
zero for the others.

The fitting RMSE loss results of the three network configurations are shown in
Figure 9 and Figure 10, where the “Network” axis indicates the network
configuration, the“Pooling-Bias” axis indicates the use of pooling and bias,
“W” denotes using pooling, “W/o” denotes not using pooling, and “T”, “F” and
“S” denote trainable, non-trainable and restricting the trainable bias vector
to be the same, respectively. The only difference between Figure 9 and Figure
10 is that we restrict the continuous 5-dimension entries on the edge of the
30-dimension vector for the 100 test samples to show the translation-
equivalence of eDCNN.

Figure 9: Fitting “f1m” and “f2m” of DFCN, cDCNN and eDCNN

Figure 10: Fitting “f1m” and “f2m” of DFCN, cDCNN and eDCNN on the position
restricted test samples.

There are mainly five observations presented in the above figures: 1) In
approximating translation-equivalence functions, both cDCNN and eDCNN perform
much better than DFCN. The main reason is that cDCNN and eDCNN encode the
translation-equivalence in the network structure111If the support of input is
far away from the edge, then cDCNN also possesses the translation-equivalence.
which is beyond the capability of DFCN; 2) From Figure 9 where testing points
are drawn far from the edge, eDCNN performs at least not worse than cDCNN
while for Figure 10 where testing points are drawn on the edge, eDCNN is much
better than cDCNN, showing the outperformance of eDCNN over cDCNN in encoding
the translation-equivalence and verifying Lemma 3 and Proposition 1; 3) eDCNN
with pooling and restricting trainable bias vectors performs stable for all
four tasks. The main reason is that eDCNN with restricting trainable bias
vectors does not destroy the translation-equivalence of the network and
therefore is more suitable for approximating translation-equivalence functions
and “f1m” and “f2m” are biased with 0.01 after each convolutional layer, which
verifies Theorem 2; 4) Though the effect of pooling is a little bit unstable
for different learning tasks and different bias vector selections, it is
efficient for the proposed eDCNN with restricting trainable bias vectors,
which also verifies Theorem 2; 5) As far as the bias vector selection is
concerned, it can be found in the above figures that restricting the bias
vectors to be constants in the same hidden layers generally outperform other
two methods, exhibiting a “less is more” phenomena in the sense that less
tunable parameters may lead to better approximation performance. This is due
to the fact that parameterizing all elements of the bias vector destroys the
translation-equivalence of eDCNN. All these show the advantages of the
proposed eDCNN and verify our theoretical assertions in Section 5.

###  7.3 Learning ability of eDCNN for clean data

In this section, we show the learning performance of eDCNN in learning clean
data $y_{i}=f(x_{i})$ for $f$ being either
$f_{1}(x)=x_{1}+x_{2}+x_{3}x_{4}+x_{5}^{2}$ with the entries of $x$ are
uniformly distributed in $(-1,1)$ or
$f_{2}(x)=x_{1}x_{2}x_{3}x_{4}x_{5}+x_{2}x_{3}x_{4}x_{5}x_{6}+\cdots+x_{26}x_{27}x_{28}x_{29}x_{30}$
with continuous 5-dimension entries uniformly distributed in $[0,1)$ and zero
for the others. It is easy to check that $f_{2}$ is translation-invariant
while $f_{1}$ does not have any transformation-invariance property. For each
problem, 1000 training samples and 100 test samples are generated randomly.

To show the power of eDCNN, we consider the following 5 network
configurations:

1) fully connected networks (denoted as DFCN). Each fully connected layer has
10 units and uses ReLU activation.

2) contracted DCNN (denoted as cDCNN). Each convolutional layer has 1 filter
with filter size 3. Each layer has a trainable bias restricted to share the
same value, expect for the last layer has a trainable bias without any
restriction. Each layer does not use padding and is followed by a ReLU
activation.

3) contracted DCNN followed by one fully connected layer (denoted as
“cDCNN+fc”). The setting is the same as cDCNN configuration, except that there
is a fully connected layer after the convolution module. The number of units
of the fully connected layer is the same as the output dimension of the
convolution module after flatten operation.

4) expansive DCNN (denoted as eDCNN). Each convolutional layer has 1 filter
with filter size 3. Each layer has a trainable bias restricted to share the
same value, expect for the last layer has a trainable bias without any
restriction. Each layer pads 2 zeros on both side in the convolution process
and is followed by a ReLU activation.

5) expansive DCNN followed by one pooling layer (denoted as “eDCNN+pl”). The
setting is the same as eDCNN configuration, except that there is a max pooling
with pooling size 2 after the convolution module.

Figure 11: Learning performance of mentioned approaches on clean data

The numerical results can be found in Figure 11. There are three interesting
observation showed in the figure: 1) eDCNN as well as “eDCNN+pl” always
performs better than other two structures in both translation-invariance data
and non-translation-invariance data. Due to the universality in approximation
and learning, eDCNN is capable of learning arbitrary regression functions
neglecting whether it possesses some transformation-invariance, which is far
beyond the capability of cDCNN; 2) cDCNN performs worse than DFCN in learning
$f_{1}$ while better than DFCN in learning $f_{2}$, although cDCNN does not
possesses the universality in approximation and learning. This is due to the
fact that $f_{2}$ possesses translation-invariance and the convolutional
structure is easy to capture this invariance while the classical inner product
structure fails; 3) eDCNN performs a little bit than the popular “cDCNN+fc” in
both learning tasks, showing that eDCNN would be a preferable alternative of
the classical setting of convolutional neural networks. All these verify our
theoretical setting in Section 6 for clean data.

TABLE II: The learning results of 5 network architectures.

Test Position | beginning
---|---
Network | DFCN | cDCNN | cDCNN+fc | eDCNN | eDCNN+pl
Loss | 0.0578 | 0.0496 | 0.0447 | 0.0401 | 0.0406
Test Position | middle
Network | DFCN | cDCNN | cDCNN+fc | eDCNN | eDCNN+pl
Loss | 0.0597 | 0.0430 | 0.0467 | 0.0401 | 0.0406
Test Position | end
Network | DFCN | cDCNN | cDCNN+fc | eDCNN | eDCNN+pl
Loss | 0.0698 | 0.0556 | 0.0426 | 0.0385 | 0.0415

Figure 12: Relation between RMSE of test position “beginning” and network
depth. The number of training samples is 20000.

###  7.4 Learning ability of eDCNN for noisy data

In this simulation, we show the outperformance of eDCNN in learning noisy
data. The data are generated by $y_{i}=f(x_{i})+\sigma_{i}$ with
$f_{3}(x)=\sin{(x_{1}^{2}+\cdots+x_{30}^{2})}+\frac{1}{2}\cos{(x_{1}^{2}+\cdots+x_{30}^{2})}$
with only continuous 5-dimension entries uniformly distributed in [0, 1) and
zero for the other and $\sigma_{i}$ is drawn i.i.d. according to the Gaussian
distribution $\mathcal{N}(0,0.01)$. To show the differece between cDCNN and
eDCNN in reflecting the translation-invariance, we evaluate on different
positions of the continuous 5-dimension entries. Our numerical results can be
found in Table II, where test position “beginning” denotes that the continuous
5-dimension entries are at positions 1 to 5, test position “middle” denotes
that the continuous 5-dimension entries are at positions 13 to 17, and test
position “end” denotes that the continuous 5-dimension entries are at
positions 26 to 30. We also figure out the role of depth for the mentioned
five structures in Figure 12.

From Table II and Figure 12, it is safe to draw the following two conclusions:
1) eDCNN as well as “eDCNN+pl” performs better than DFCN and cDCNN in three
test positions. Especially, for “beginning” and “end” positions, eDCNN
performs much better. This is due to the fact that cDCNN does not encode the
translation-equivalence when the support of function is at the edge, showing
the necessity of zero-padding; 2) eDCNN as well as “eDCNN+pl” performs at
least not worse than “cDCNN+fc”. Furthermore, it follows from Figure 12 that
eDCNN and “eDCNN+pl” behave stable with respect to the depth, which is similar
as “cDCNN+fc”. Both observations illustrate that zero-padding is a feasible
and efficient alternative of fully connected layer in learning noisy data.

(a) Relation for $f_{2}$ (b) Relation for $f_{3}$

Figure 13: Relation between RMSE and data size for $f_{2}$ and $f_{3}(x)$ with
test position “beginning”.

###  7.5 Universal consistency of eDCNN

In this simulation, we show the universal consistency of eDCNN via showing the
relation between the generalization error and size of the data. In particular,
we report this relation on both clean and noisy data for the mentioned 5
network configurations. To be detailed, we report the smallest loss among
different network depths for learning $f_{2}$ and set depth to be 6 for
learning $f_{3}$. The reason of different setting for different simulations is
due to the stability of depth shown in the previous subsection. The numerical
results can be found in Figure 13.

There are also three interesting observations exhibited in Figure 13: 1) For
$f_{2}$, the test loss curve of eDCNN is much lower than others while
“eDCNN+pl” achieves the suboptimal results, which validates that eDCNN has
better learning capability than DFCNs and cDCNNs in learning clean
translation-invariant data; 2) For $f_{3}$, eDCNN, “eDCNN+pl” and “cDCNN+fc”
are better than DFCN and cDCNN, mainly due to the non-translation-invariance
of DFCN and cDCNN when $f_{3}$ is supported at the edge; 3) RMSE roughly
decreases with respect to the number of training samples, demonstrating the
consistency of the deep nets estimates. All these verify our theoretical
assertions in Section 6.

Figure 14: Classification accuracy results of the 5 network configurations on
WISDM dataset.

Figure 15: Classification accuracy results of the 5 network configurations on
MIT-BTH dataset.

Figure 16: Classification accuracy results of the 5 network configurations on
PTB dataset.

###  7.6 Real date everifications

In this part, we aim at showing the usability and efficiency of eDCNN on two
real world data.

####  7.6.1 WISDM dataset

For human activity recognition task, we evaluate on WISDM dataset which
includes 1098207 samples with 6 categories of movement (walking, running,
jogging, etc.).

The network structures are as follows. There are 60 units in each fully
connected layer and 20 filters with filter length 9 in the the convolutional
layer of cDCNN, “cDCNN+fc”, eDCNN and “eDCNN+pl”. The number of units of the
fully connected layer of “cDCNN+fc” is set as 100. The pooling size of the max
pooling layer of “eDCNN+pl” is set as 2 and the max pooling layer lies after
the convolutional module. We train the network with an Adam optimizer for 150
epochs. The batch size is set as 512.

Figure 14 shows the classification accuracy results of the 5 network
configurations on WISDM dataset varying with depth. It can be found that
“eDCNN+pl” achieves the highest test accuracy and holds high test accuracy
with different depths, which shows the good learning capacity of eDCNN with
appropriate pooling scheme. DFCN is not good at dealing with such data that
contains temporal information. Even when dealing with such data, cDCNN
outperforms “cDCNN+fc” overall, which further validates the disadvantage of
the fully connected layer in dealing with such data.

####  7.6.2 ECG heartbeat dataset

For ECG heartbeat classification task, we evaluate on the MIT-BIH Arrhythmia
Database and the PTB Diagnostic ECG Database. An ECG is a 1D signal that is
the result of recording the electrical activity of the heart using an
electrode. It is a very useful tool that cardiologists use to diagnose heart
anomalies and diseases. The MIT-BIH Arrhythmia data set includes 109446
samples with 5 categories, and the PTB Diagnostic ECG Database includes 14552
samples with 2 categories. Similarly, the network depth of DFCN, cDCNN,
“cDCNN+fc”, eDCNN and “eDCNN+pl” varies from 1 to 10. For fully connected
layers, each layer has 80 units. For the convolutional layer, each layer has
16 filters with length 6. The number of units of the fully connected layer is
64. The pool size of the max pooling layer of “eDCNN+pl” is 2 and the max
pooling layer lies after the first convolutional layer. We train the network
with an Adam optimizer for 100 epochs.

Figure 15 shows the classification accuracy results of the 5 network
configurations on MIT-BTH dataset varying with depth. “eDCNN+pl” achieves the
highest test accuracy and holds high test accuracy with large network depths,
which shows the good learning capacity of eDCNN with appropriate pooling
scheme. DFCN achieves good and stable results among different network depths.
The relatively poor results of cDCNN and “cDCNN+fc” may due to the information
loss while convolving at the edge of feature without bias.

Figure 16 shows the classification accuracy results of the 5 network
configurations on PTB dataset varying with depth. DFCN is not good at dealing
with this dataset. The other four configurations achieve good and vary close
results. It may because this dataset is relatively easy to classify.

##  8 Conclusion

In this paper, we studied the representation and learning performance of deep
convolutional neural networks with zero-padding (eDCNN). After detailed
analysis of the roles of zero-padding, pooling and bias vectors, we found that
eDCNN succeeds in encoding the translation-equivalence (or translation-
invariance for eDCNN with pooling) without sacrificing the universality in
approximation and learning of DFCNs. This demonstrated that eDCNN is
essentially better than DFCN in translation-equivalence related applications,
since the network structure itself can reflect this data feature without any
training. Noting that deep neural networks without zero-padding (cDCNN) do not
possess the universality, we found that eDCNN is essentially better than cDCNN
in the sense that eDCNN can extract any data features if it is sufficiently
deep, which is beyond the capability of cDCNN. This assertion was also made in
extracting the translation-equivalence (or translation-invariance) by terms
that cDCNN fails to encode it if the support of data is on the edge. All these
findings together with solid theoretical analysis and numerous numerical
experiments illustrated the outperformance of eDCNN over cDCNN and DFCN and
provided a unified network structure with theoretical verifications for
feature extraction and learning purposes.

## Acknowledgement

Z. Han was partially supported by the National Key Research and Development
Program of China under Grant 2020YFB1313400, the CAS Project for Young
Scientists in Basic Research under Grant YSBR-041, the National Natural
Science Foundation of China under Grant 61903358, 61773367, 61821005, and the
Youth Innovation Promotion Association of the Chinese Academy of Sciences
under Grant 2022196, Y202051. S. B. Lin was partially supported by the
National Natural Science Foundation of China [Grant Nos. 62276209]. D. X. Zhou
was partially supported in part by the Research Grants Council of Hong Kong
[Project Nos. CityU 11308020, N_CityU 102/20, C1013-21GF], Hong Kong Institute
for Data Science, Germany/Hong Kong Joint Research Scheme [Project No.
G-CityU101/20], Laboratory for AI-Powered Financial Technologies, and National
Science Foundation of China [Project No. 12061160462].

## References

  * [1] R. Cipolla, S. Battiato, and G. M. Farinella, _Machine Learning for Computer Vision_. Springer, 2013, vol. 5.
  * [2] H. Pallathadka, M. Mustafa, D. T. Sanchez, G. S. Sajja, S. Gour, and M. Naved, “Impact of machine learning on management, healthcare and agriculture,” _Materials Today: Proceedings_ , 2021.
  * [3] M. F. Dixon, I. Halperin, and P. Bilokon, _Machine Learning in Finance_. Springer, 2020, vol. 1406.
  * [4] S. Athey, “The impact of machine learning on economics,” in _The economics of artificial intelligence: An agenda_. University of Chicago Press, 2018, pp. 507–547.
  * [5] M. Bowling, J. Fürnkranz, T. Graepel, and R. Musick, “Machine learning and games,” _Machine learning_ , vol. 63, no. 3, pp. 211–215, 2006.
  * [6] J. Shawe-Taylor, N. Cristianini _et al._ , _Kernel methods for pattern analysis_. Cambridge University Press, 2004\.
  * [7] I. Goodfellow, Y. Bengio, and A. Courville, _Deep Learning_. MIT Press, 2016.
  * [8] L. Deng, D. Yu _et al._ , “Deep learning: methods and applications,” _Foundations and trends® in signal processing_ , vol. 7, no. 3–4, pp. 197–387, 2014.
  * [9] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _nature_ , vol. 521, no. 7553, pp. 436–444, 2015.
  * [10] O. S. Kayhan and J. C. v. Gemert, “On translation invariance in cnns: Convolutional layers can exploit absolute spatial location,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 14 274–14 285.
  * [11] Z. Zhang, B.-S. Hua, D. W. Rosen, and S.-K. Yeung, “Rotation invariant convolutions for 3d point clouds deep learning,” in _2019 International conference on 3d vision (3DV)_. IEEE, 2019, pp. 204–213.
  * [12] M. Chatzidakis and G. Botton, “Towards calibration-invariant spectroscopy using deep learning,” _Scientific reports_ , vol. 9, no. 1, pp. 1–10, 2019\.
  * [13] Y. Bengio, “Learning deep architectures for ai,” _Foundations and Trends® in Machine Learning_ , vol. 2, no. 1, pp. 1–127, 2009\.
  * [14] P. P. Brahma, D. Wu, and Y. She, “Why deep learning works: A manifold disentanglement perspective,” _IEEE transactions on neural networks and learning systems_ , vol. 27, no. 10, pp. 1997–2008, 2015.
  * [15] Y. Bengio, A. Courville, and P. Vincent, “Representation learning: A review and new perspectives,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 35, no. 8, pp. 1798–1828, 2013.
  * [16] D. Yarotsky, “Error bounds for approximations with deep relu networks,” _Neural Networks_ , vol. 94, pp. 103–114, 2017.
  * [17] C. K. Chui, S.-B. Lin, B. Zhang, and D.-X. Zhou, “Realization of spatial sparseness by deep relu nets with massive data,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2020.
  * [18] C. Schwab and J. Zech, “Deep learning in high dimension: Neural network expression rates for generalized polynomial chaos expansions in uq,” _Analysis and Applications_ , vol. 17, no. 01, pp. 19–55, 2019.
  * [19] S.-B. Lin, “Generalization and expressivity for deep nets,” _IEEE transactions on neural networks and learning systems_ , vol. 30, no. 5, pp. 1392–1406, 2018.
  * [20] C. K. Chui, S.-B. Lin, and D.-X. Zhou, “Deep neural networks for rotation-invariance approximation and learning,” _Analysis and Applications_ , vol. 17, no. 05, pp. 737–772, 2019.
  * [21] H. N. Mhaskar and T. Poggio, “Deep vs. shallow networks: An approximation theory perspective,” _Analysis and Applications_ , vol. 14, no. 06, pp. 829–848, 2016.
  * [22] Z. Han, S. Yu, S.-B. Lin, and D.-X. Zhou, “Depth selection for deep relu nets in feature extraction and generalization,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2020.
  * [23] U. Shaham, A. Cloninger, and R. R. Coifman, “Provable approximation properties for deep neural networks,” _Applied and Computational Harmonic Analysis_ , vol. 44, no. 3, pp. 537–557, 2018.
  * [24] M. Kohler and A. Krzyżak, “Nonparametric regression based on hierarchical interaction models,” _IEEE Transactions on Information Theory_ , vol. 63, no. 3, pp. 1620–1630, 2016.
  * [25] P. Petersen and F. Voigtlaender, “Equivalence of approximation by convolutional neural networks and fully-connected networks,” _Proceedings of the American Mathematical Society_ , vol. 148, no. 4, pp. 1567–1581, 2020.
  * [26] K. Oono and T. Suzuki, “Approximation and non-parametric estimation of resnet-type convolutional neural networks,” in _International conference on machine learning_. PMLR, 2019, pp. 4922–4931.
  * [27] D.-X. Zhou, “Deep distributed convolutional neural networks: Universality,” _Analysis and Applications_ , vol. 16, no. 06, pp. 895–919, 2018.
  * [28] ——, “Universality of deep convolutional neural networks,” _Applied and Computational Harmonic Analysis_ , vol. 48, no. 2, pp. 787–794, 2020.
  * [29] B. Hanin and M. Sellke, “Approximating continuous functions by relu nets of minimal width,” _arXiv preprint arXiv:1710.11278_ , 2017.
  * [30] S.-B. Lin, K. Wang, Y. Wang, and D.-X. Zhou, “Universal consistency of deep convolutional neural networks,” _IEEE Transactions on Information Theory_ , 2022.
  * [31] L. Györfi, M. Kohler, A. Krzyżak, and H. Walk, _A Distribution-free Theory of Nonparametric Regression_. Springer, 2002, vol. 1.
  * [32] F. Cucker and D. X. Zhou, _Learning Theory: an Approximation Theory Viewpoint_. Cambridge University Press, 2007, vol. 24.
  * [33] P. Petersen and F. Voigtlaender, “Optimal approximation of piecewise smooth functions using deep relu neural networks,” _Neural Networks_ , vol. 108, pp. 296–330, 2018.
  * [34] J. Schmidt-Hieber, “Nonparametric regression using deep neural networks with relu activation function,” _The Annals of Statistics_ , vol. 48, no. 4, pp. 1875–1897, 2020.
  * [35] H. W. Lin, M. Tegmark, and D. Rolnick, “Why does deep and cheap learning work so well?” _Journal of Statistical Physics_ , vol. 168, no. 6, pp. 1223–1247, 2017.
  * [36] I. Safran and O. Shamir, “Depth-width tradeoffs in approximating natural functions with neural networks,” in _International conference on machine learning_. PMLR, 2017, pp. 2979–2987.
  * [37] J. Gu, Z. Wang, J. Kuen, L. Ma, A. Shahroudy, B. Shuai, T. Liu, X. Wang, G. Wang, J. Cai _et al._ , “Recent advances in convolutional neural networks,” _Pattern recognition_ , vol. 77, pp. 354–377, 2018.
  * [38] D.-X. Zhou, “Theory of deep convolutional neural networks: Downsampling,” _Neural Networks_ , vol. 124, pp. 319–327, 2020.
  * [39] I. Daubechies, _Ten Lectures on Wavelets_. SIAM, 1992.

## Appendix: Proofs

We prove our theoretical results in Appendix. The proof idea of Lemma 1 is
standard by either using the definition of the convolution or using the the
symbol of sequences in [39, 28].

###### Proof of Lemma 1.

Due to (4) and the fact that $\vec{w}^{1}=(w_{j}^{1})_{j=-\infty}^{\infty}$
and $\vec{w}^{2}=(w_{j}^{2})_{j=-\infty}^{\infty}$ are supported on
$\\{0,1,\dots,s\\}$, for any $-s\leq k\leq 0,k\leq j\leq s+k$, the $j$-th
component of $\vec{w}^{1}\star\vec{w}^{2}$ is

$\displaystyle(\vec{w}^{1}\star\vec{w}^{2})_{j}=\sum_{k=j-s}^{j}w^{1}_{j-k}w^{2}_{k+s}$
$\displaystyle=$ $\displaystyle
w_{0}^{1}w_{j+s}^{2}+w_{1}^{1}w_{j+s-1}^{2}+\dots+w_{j+s-1}^{1}w_{1}^{2}+w^{1}_{j+s}w_{0}^{2}.$

Noting again that $\vec{w}^{1}$ and $\vec{w}^{2}$ have the same support, we
thus have

$(\vec{w}^{1}\star\vec{w}^{2})_{j}=(\vec{w}^{2}\star\vec{w}^{1})_{j},$

which implies (11) for $\otimes=\star$. To prove (11) for $\otimes=*$, we use
the symbol of sequences as follows. The symbol $\tilde{\vec{w}}$ of a sequence
$\vec{w}$ supported on the set of nonnegative integers is defined as a
polynomial on $\mathbb{C}$ by $\tilde{\vec{w}}=\sum_{k=0}^{\infty}w_{k}z^{k}$.
Then, direct computation yields

$\widetilde{\vec{w}^{1}*\vec{w}^{2}}=\tilde{\vec{w}}^{1}\tilde{\vec{w}}^{2}.$

Noting

$\tilde{\vec{w}}^{1}\tilde{\vec{w}}^{2}=\tilde{\vec{w}}^{2}\tilde{\vec{w}}^{1}=\widetilde{\vec{w}^{2}*\vec{w}^{1}},$

we then have

$\widetilde{\vec{w}^{1}*\vec{w}^{2}}=\widetilde{\vec{w}^{2}*\vec{w}^{1}}$

and consequently

$\vec{w}^{1}*\vec{w}^{2}=\vec{w}^{2}*\vec{w}^{1}.$

This completes the proof of Lemma 1. ∎

Define $T_{\tilde{d},d^{\prime}}^{\vec{w}}$ be a $\tilde{d}\times d^{\prime}$
Toeplitz matrix by

$\left[\begin{array}[]{ccccccc}w_{0}&0&0&\cdots&0\\\ w_{1}&w_{0}&0&\cdots&0\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\
w_{d^{\prime}-1}&w_{d^{\prime}-2}&\cdots&\cdots&w_{0}\\\
w_{d^{\prime}}&w_{d^{\prime}-1}&\cdots&0\cdots&w_{1}\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\
w_{\tilde{d}-d^{\prime}}&\cdots&\cdots&\cdots&w_{\tilde{d}-2d^{\prime}+1}\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\
w_{\tilde{d}-2}&w_{\tilde{d}-3}&\cdots&w_{\tilde{d}-d^{\prime}}&w_{\tilde{d}-d^{\prime}-1}\\\
w_{\tilde{d}-1}&w_{\tilde{d}-2}&\cdots&w_{\tilde{d}-d^{\prime}+1}&w_{\tilde{d}-d^{\prime}}\end{array}\right].$
(34)

Observe that if $W$ is supported in $\\{0,\dots,S\\}$ for some
$S\in\mathbb{N}$, the entry $(T_{D,d^{\prime}}^{\vec{w}})_{i,k}=w_{i-k}$
vanishes when $i-k>S$. To prove Proposition 1, it is sufficient to prove the
following lemma.

######  Lemma 4.

Let $1\leq p\leq d$, $2\leq s\leq d$, $d_{0}=d$ and $d_{\ell}=d+\ell s$. If
$\vec{w}$ is supported on $\\{0,1,\dots,s\\}$ and
$T_{d_{\ell},d_{\ell-1}}^{\vec{w}}$ is the Toeplitz matrix in (34). Then for
any $j\leq d_{\ell-1}-p+1$, there holds

$T_{d_{\ell},d_{\ell-1}}^{\vec{w}}A_{j,d_{\ell-1}}\vec{v}_{p,d_{\ell-1},1}=A_{j,d_{\ell}}T_{d_{\ell},d_{\ell-1}}^{\vec{w}}\vec{v}_{p,d_{\ell-1},1}.$

###### Proof.

Direct computation yields

$\vec{w}^{\ell}*\vec{v}=T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\vec{v}.$ (35)

Due to (13), we have

$A_{j,d_{\ell-1}}\vec{v}_{p,d_{\ell-1},1}=\vec{v}_{p,d_{\ell-1},j}.$

Then, for any $k=1,\dots,d_{\ell}$, we have from (35) and (7) that

$\displaystyle\left(T_{d_{\ell},d_{\ell-1}}^{\vec{w}}A_{j,d_{\ell-1}}\vec{v}_{p,d_{\ell-1},1}\right)_{k}=(\vec{w}*\vec{v}_{p,d_{\ell-1},j})_{k}$
$\displaystyle=$ $\displaystyle\sum_{i=j}^{j+p-1}w_{k-i}v_{i-j+1}$

and

$\left(T_{d_{\ell},d_{\ell-1}}^{\vec{w}}\vec{v}_{p,d_{\ell-1},1}\right)_{k}=(\vec{w}*\vec{v}_{p,d_{\ell-1},1})_{k}=\sum_{i=1}^{p}w_{k-i}v_{i}.$

According to (13) again, we have for any $k=j,\dots,j+p-1$,

$\displaystyle\left(A_{j,d_{\ell}}T_{d_{\ell},d_{\ell-1}}^{\vec{w}}\vec{v}_{p,d_{\ell-1},1}\right)_{k}=\left(T_{d_{\ell},d_{\ell-1}}^{\vec{w}}\vec{v}_{p,d_{\ell-1},1}\right)_{k-j+1}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{p}w_{k-j+1-i}v_{i}=\sum_{i=j}^{j+p-1}w_{k-i}v_{i-j+1}.$

Noting further that except for the $j,\dots,j+p-1$ components, other
components are zero. We then have

$T_{d_{\ell},d_{\ell-1}}^{\vec{w}}A_{j,d_{\ell-1}}\vec{v}_{p,d_{\ell-1},1}=A_{j,d_{\ell}}T_{d_{\ell},d_{\ell-1}}^{\vec{w}}\vec{v}_{p,d_{\ell-1},1}.$

This completes the proof of Lemma 4. ∎

Based on Lemma 4, we can prove Proposition 1 directly.

###### Proof of Proposition 1.

Due to Lemma 4, we have

$\displaystyle T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\cdots
T_{d_{1},d}^{\vec{w}^{1}}A_{j,d}\vec{v}_{p,d,1}=T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\cdots
A_{j,d_{1}}T_{d_{1},d_{0}}^{\vec{w}^{1}}\vec{v}_{p,d,1}$ $\displaystyle=$
$\displaystyle\dots=A_{j,d_{\ell}}T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\cdots
T_{d_{1},d_{0}}^{\vec{w}^{1}}\vec{v}_{p,d,1}$

Then it follows from (35) that (14) holds. This completes the proof of
Proposition 1. ∎

To prove Proposition 2, we need several auxiliary lemmas. The first one is the
convolution factorization lemma provided in [28, Theorem 3].

######  Lemma 5.

Let $S\geq 0,2\leq s\leq d$ and $\vec{u}=(u_{k})_{-\infty}^{\infty}$ be
supported on $\\{0,\dots,S\\}$. Then there exists $L<\frac{S}{s-1}+1$ filter
vectors $\\{\vec{w}^{\ell}\\}_{\ell=1}^{L}$ supported on $\\{0,\dots,s\\}$
such that $\vec{u}=\vec{w}^{L}*\cdots*\vec{w}^{1}$.

The second one is the following lemma that was given in [27].

######  Lemma 6.

Let $2\leq s\leq d^{\prime}$, $d^{\prime}_{\ell}=d^{\prime}+\ell s$ and
$d^{\prime}_{0}=d^{\prime}$. If $\\{\vec{w}^{\ell}\\}_{\ell=1}^{L^{*}}$ is
supported on $\\{0,\dots,s\\}$, then

$T_{d_{\ell}^{\prime},d^{\prime}}^{\vec{w}^{\ell}*\cdots\vec{w}^{2}*\vec{w}^{1}}=T_{d^{\prime}_{\ell},d^{\prime}_{\ell-1}}^{\vec{w}^{\ell}}\cdots
T_{d_{2}^{\prime},d^{\prime}_{1}}^{\vec{w}^{2}}T_{d^{\prime}_{1},d^{\prime}}^{\vec{w}^{1}}$
(36)

holds for any $\ell\in\\{1,2,\dots,L^{*}\\}$.

The third one focuses on representing the inner product by multi-layer
convolution.

######  Lemma 7.

Let $\tilde{d},d^{\prime}\in\mathbb{N}$, $2\leq s\leq d^{\prime}$,
$d^{\prime}=0$ and $d^{\prime}_{\ell}=d^{\prime}+\ell s$. Then for any
$\tilde{d}\times d^{\prime}$ matrix $W$, there exist
$L^{*}=\lceil\frac{d^{\prime}\tilde{d}}{s-1}\rceil$ filter vectors
$\\{\vec{w}^{\ell}\\}_{\ell=1}^{L^{*}}$ supported on $\\{0,1,\dots,s\\}$ such
that

$Wx=\mathcal{S}_{d^{\prime}_{L^{*}},d^{\prime},0}\left(\vec{w}^{L^{*}}*\dots*\vec{w}^{1}*x\right),\qquad\forall
x\in\mathbb{R}^{d^{\prime}}.$ (37)

###### Proof.

Define a sequence $\vec{u}$ supported on $\\{0,\dots,d^{\prime}\tilde{d}-1\\}$
by stacking the rows of $W$, i.e.

$\displaystyle\vec{u}^{T}$ $\displaystyle=$
$\displaystyle(W_{1,1},W_{2,1},\dots,W_{d\tilde{d},1},W_{1,2},\dots,W_{\tilde{d},d})$
$\displaystyle=:$ $\displaystyle(W_{0},\dots,W_{d^{\prime}\tilde{d}-1}).$

We apply Lemma 5 with $S=d^{\prime}\tilde{d}-1$ and $s\geq 2$ to obtain
$\hat{L}<\frac{d^{\prime}\tilde{d}-1}{s-1}+1$ filter vectors
$\\{\vec{w}^{\ell}\\}_{\ell=1}^{\hat{L}}$ such that

$\vec{u}=\vec{w}^{\hat{L}}*\dots*\vec{w}^{1}.$

Let $T^{\vec{u}}$ be the $d^{\prime}_{\hat{L}}\times d^{\prime}$ matrix
$(W_{k-j})_{k=1,\dots,d_{\hat{L}}^{\prime},j=1,\dots,d^{\prime}}$. Observe
from the definition of the sequence $\vec{u}$ that for $j=1,\dots,\tilde{d}$,
the $jd^{\prime}$-th row of $T^{\vec{u}}$ is exactly the $j$-th raw of $W$.
Setting $L^{*}=\lceil\frac{d^{\prime}\tilde{d}}{s-1}\rceil$, it is obvious
that $\hat{L}\leq L^{*}$. Taking $\vec{w}^{\hat{L}+1}=\dots=\vec{w}^{L^{*}}$
to be the delta sequence, we have $\vec{u}=\vec{w}^{L^{*}}*\dots*\vec{w}^{1}$.
Then it follows from Lemma 6 that $T^{\vec{u}}=T^{\vec{w}^{L^{*}}}\cdots
T^{\vec{w}^{1}}.$ According to the definition of
$\mathcal{S}_{d_{L^{*}}^{\prime},d^{\prime},0}$ in (15) and the definition of
$T^{\vec{u}}$, we have

$\mathcal{S}_{d_{L^{*}}^{\prime},d^{\prime},0}\left(T^{\vec{u}}x\right)=Wx.$

Therefore,

$\displaystyle\mathcal{S}_{d_{L^{*}}^{\prime},d^{\prime},0}(T^{\vec{w}^{L^{*}}}\dots
T^{\vec{w}^{1}}x)$ $\displaystyle=$
$\displaystyle\mathcal{S}_{d_{L^{*}}^{\prime},d^{\prime},0}(\vec{w}^{L^{*}}*\dots*\vec{w}^{1}*x)=Wx.$

This completes the proof of Lemma 7. ∎

Our fourth lemma is a representation of matrices multiplication, which can be
derived from Lemma 7.

######  Lemma 8.

Let $J,d\in\mathbb{N}$, $2\leq s\leq d$, $d_{1},\dots,d_{J}\in\mathbb{N}$
satisfying $d_{0}=d$ and $L_{j}=\lceil\frac{d_{j-1}d_{j}}{s-1}\rceil$. If
$W^{j}$ is a $d_{j}\times d_{j-1}$ matrix, then for any $x\in\mathbb{R}^{d}$,
there exist $\sum_{j=1}^{J}L_{j}$ filter vectors
$\\{\vec{w}^{j,\ell}\\}_{\ell=1}^{L_{j}}$ supported on $\\{0,1,\dots,s\\}$
such that

$\displaystyle W^{J}W^{J-1}\cdots W^{1}x$ (38) $\displaystyle=$
$\displaystyle\mathcal{S}_{d_{J-1}+L_{J}s,d_{J-1},0}\left(\vec{w}^{J,L_{J}}*\cdots*\vec{w}^{J,1}\right)$
$\displaystyle*\dots*\mathcal{S}_{d_{0}+L_{1}s,d_{0},0}\left(\vec{w}^{1,L_{1}}*\dots*\vec{w}^{1,1}*x\right).$

With these helps, we are in a position to prove Proposition 2

###### Proof of Proposition 2.

According to Proposition 1, for any $1\leq j,j^{\prime}$, the $j$-th component
of $\vec{w}^{L}*\dots*\vec{w}^{1}*\vec{v}_{p,d,j}$ is exactly the
$j^{\prime}$-th component of
$\vec{w}^{L}*\dots*\vec{w}^{1}*\vec{v}_{p,d,j^{\prime}}$. We then have from
(15) that (18) holds. Then Proposition 2 is a direct result by combining Lemma
8 and (18). This completes the proof of Proposition 2. ∎

To prove Theorem 1, we need some preliminaries. For a sequence $\vec{w}$
supported on $\\{0,1,\dots,s\\}$, write
$\|\vec{w}\|_{1}=\sum_{k=-\infty}^{\infty}|w_{k}|$ and
$\|\vec{w}\|_{\infty}=\max_{-\infty\leq k\leq\infty}|w_{k}|$. Define
$B^{0}:=\max_{x\in\mathbb{I}^{d}}\max_{k=1,\dots,d}|x^{(k)}|$ and

$B^{\ell}:=\|\vec{w}^{\ell}\|_{1}B^{\ell-1}\cdots B^{1}B^{0},\qquad\ell\geq
1.$

Let $T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}$ be the convolution matrix given
in (34). Then for any $j=1,\dots,d_{\ell}$, direct computation yields

$\max_{x\in\mathbb{I}^{d}}\left|\left(T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\dots
T_{d_{1},d_{0}}^{\vec{w}^{1}}x\right)_{j}\right|\leq B^{\ell}$ (39)

and for $1\leq k\leq\ell-1$

$\left|\left(T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\dots
T_{d_{k+1},d_{k}}^{\vec{w}^{k+1}}B^{k}\mathbf{1}_{d_{k}}\right)_{j}\right|\leq
B^{\ell}.$ (40)

######  Lemma 9.

Let $\ell\in\mathbb{N}$, $2\leq s\leq d$ and
$\mathcal{C}^{R}_{\ell,\vec{w}^{\ell},b^{\ell}}$ be defined by (19) with
$\vec{w}^{\ell}$ supported on $\\{0,1,\dots,s\\}$ and
$b^{\ell}=2^{\ell-1}B^{\ell}$, then

$\displaystyle\sigma\circ\mathcal{C}^{R}_{\ell,\vec{w}^{\ell},{b}^{\ell}}\circ\sigma\circ\dots\circ\sigma\circ\mathcal{C}^{R}_{1,\vec{w}^{1},{b}^{1}}(x)$
(41) $\displaystyle=$ $\displaystyle
T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\cdots
T_{d_{2},d_{1}}^{\vec{w}^{2}}T_{d_{1},d}^{\vec{w}^{1}}x+b^{\ell}{\bf
1}_{d_{\ell}}$ $\displaystyle+$
$\displaystyle\sum_{k=1}^{\ell-1}T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\cdots
T_{d_{k+1},d_{k}}^{\vec{w}^{k+1}}b^{k}{\mathbf{1}}_{d_{k}}.$

###### Proof.

For any $1\leq\ell\leq L^{*}$, it follows from (35) that

$\vec{w}^{\ell}*\dots*\vec{w}^{1}*x=T_{d_{\ell*},d_{\ell-1}}^{\vec{w}^{\ell}}\dots
T_{d_{1},d_{0}}^{\vec{w}^{1}}x.$ (42)

We then prove (41) by induction. We obtain from the definition of $\sigma$
directly that

$\sigma(\vec{w}^{1}*x+b^{1}{\bf
1}_{d_{1}})=T_{d_{1},d_{0}}^{\vec{w}^{1}}x+b^{1}{\bf 1}_{d_{1}},$

which verifies (41) for $\ell=1$. Assume that (41) holds for $\ell-1$, that
is,

$\displaystyle\vec{V}_{\ell-1}^{s,R}=\sigma\circ\mathcal{C}^{R}_{\ell-1,\vec{w}^{\ell-1},{b}^{\ell-1}}\circ\sigma\circ\dots\circ\sigma\circ\mathcal{C}^{R}_{1,\vec{w}^{1},{b}^{1}}(x)$
$\displaystyle=$ $\displaystyle
T_{d_{\ell-1},d_{\ell-2}}^{\vec{w}^{\ell-1}}\cdots
T_{d_{2},d_{1}}^{\vec{w}^{2}}T_{d_{1},d}^{\vec{w}^{1}}x+b^{\ell-1}{\bf
1}_{d_{\ell-1}}$ $\displaystyle+$
$\displaystyle\sum_{k=1}^{\ell-2}T_{d_{\ell-1},d_{\ell-2}}^{\vec{w}^{\ell-1}}\cdots
T_{d_{k+1},d_{k}}^{\vec{w}^{k+1}}b^{k}{\mathbf{1}}_{d_{k}}.$

Then,

$\displaystyle\vec{w}^{\ell}*\vec{V}^{s,R}_{\ell-1}=T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\cdots
T_{d_{1},d}^{\vec{w}^{1}}x$ $\displaystyle+$
$\displaystyle\sum_{k=1}^{\ell-1}T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}T_{d_{\ell-1},d_{\ell-2}}^{\vec{w}^{\ell-1}}\cdots
T_{d_{k+1},d_{k}}^{\vec{w}^{k+1}}b^{k}{\mathbf{1}}_{d_{k}}.$

This together with (39), (40) and $b^{\ell}=2^{\ell-1}B^{\ell}$ yields that
for any $j=1,\dots,d_{\ell}$, there holds

$\max_{x\in\mathbb{I}^{d}}\left|\left(\vec{w}^{\ell}*\vec{V}^{s,R}_{\ell-1}\right)_{j}\right|\leq
B^{\ell}+B^{\ell}\sum_{k=1}^{\ell-1}2^{k-1}=2^{\ell-1}B^{\ell}=b^{\ell},$

implying

$\displaystyle\sigma\left(\vec{w}^{\ell}*\vec{V}^{s,R}_{\ell-1}+b^{\ell}{\bf
1}_{d_{\ell}}\right)=\vec{w}^{\ell}*\vec{V}^{s,R}_{\ell-1}+b^{\ell}{\bf
1}_{d_{\ell}}$ $\displaystyle=$ $\displaystyle
T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}\cdots T_{d_{1},d}^{\vec{w}^{1}}x$
$\displaystyle+$
$\displaystyle\sum_{k=1}^{\ell-1}T_{d_{\ell},d_{\ell-1}}^{\vec{w}^{\ell}}T_{d_{\ell-1},d_{\ell-2}}^{\vec{w}^{\ell-1}}\cdots
T_{d_{k+1},d_{k}}^{\vec{w}^{k}}b^{k}{\mathbf{1}}_{d_{k}}+b^{\ell}{\bf
1}_{d_{\ell}}.$

Therefore, (41) holds for any $\ell=1,2,\dots$. This completes the proof of
Lemma 9. ∎

By the help of the above lemma, we are in a position to prove Theorem 1 as
follows.

###### Proof of Theorem 1.

Define

$b^{\ell}=2^{\ell-1}B^{\ell},\qquad\ell=1,2,\dots,L^{*}.$ (43)

It follows from Lemma 9 with $\ell=L^{*}-$ and (35) that

$\displaystyle\vec{V}_{L^{*}-1}^{s,R}=\vec{w}^{L^{*}-1}*\cdots*\vec{w}^{1}*x+b^{L^{*}-1}{\bf
1}_{d_{L^{*}-1}}$ $\displaystyle+$
$\displaystyle\sum_{k=1}^{L^{*}-2}T_{d_{L^{*}-1},d_{L^{*}-2}}^{\vec{w}^{L^{*}-1}}\cdots
T_{d_{k+1},d_{k}}^{\vec{w}^{k+1}}b^{k}{\mathbf{1}}_{d_{k}}.$

Write

$\displaystyle\vec{B}^{d_{L^{*}}}:=\sum_{k=1}^{L^{*}}T_{d_{L^{*}},d_{L^{*}-1}}^{\vec{w}^{L^{*}}}\cdots
T_{d_{k+1},d_{k}}^{\vec{w}^{k+1}}b^{k}{\mathbf{1}}_{d_{k}}$ $\displaystyle=$
$\displaystyle w^{L^{*}}*b^{L^{*}-1}{\bf 1}_{d_{L^{*}-1}}$ $\displaystyle+$
$\displaystyle
w^{L^{*}}*\sum_{k=1}^{L^{*}-2}T_{d_{L^{*}-1},d_{L^{*}-2}}^{\vec{w}^{L^{*}-1}}\cdots
T_{d_{k+1},d_{k}}^{\vec{w}^{k+1}}b^{k}{\mathbf{1}}_{d_{k}}.$

For $\vec{\theta}:=(\theta_{1},\dots,\theta_{n})^{T}$, define
$\vec{\theta}_{d_{L^{*}}}\in\mathbb{R}^{d_{L^{*}}}$ be the vector satisfying
$\mathcal{S}_{d_{L^{*}},d,0}(\theta_{d_{L^{*}}})=\theta$ and other components
being zero. Then, we can define

$\vec{b}^{L^{*}}:=\theta_{d_{L^{*}}}-\vec{B}^{d_{L^{*}}}.$

Therefore, it follows from the definition of $\mathcal{S}_{d_{L^{*}},d,0}$ and
Lemma 7 that

$\displaystyle\mathcal{S}_{d_{L^{*}},d,0}\circ\sigma(\vec{w}^{L^{*}}*\vec{V}_{L^{*}-1}^{s,R}+\vec{b}^{L^{*}})$
$\displaystyle=$
$\displaystyle\sigma\circ\mathcal{S}_{d_{L^{*}},d,0}(\vec{w}^{L^{*}}*\vec{V}_{L^{*}-1}^{s,R}+\vec{b}^{L^{*}})$
$\displaystyle=$
$\displaystyle\sigma\circ\mathcal{S}_{d_{L^{*}},d,0}(\vec{w}^{L^{*}}*\vec{V}_{L^{*}-1}^{s,R}+\theta_{d_{L^{*}}}-\vec{B}^{d_{L^{*}}})$
$\displaystyle=$
$\displaystyle\sigma\circ\mathcal{S}_{d_{L^{*}},d,0}(\vec{w}^{L^{*}}*\cdots*\vec{w}^{1}*x+\theta_{d_{L^{*}}})$
$\displaystyle=$
$\displaystyle\sigma(\mathcal{S}_{d_{L^{*}},d,0}\circ\vec{w}^{L^{*}}*\cdots*\vec{w}^{1}*x+\theta)$
$\displaystyle=$ $\displaystyle\sigma(Wx+\theta).$

This proves (22). Furthermore (23) can be derived by Corollary 1 by noting
that the bias vectors in the same layer are the same before pooling. This
completes the proof of Theorem 1. ∎

###### Proof of Theorem 2.

Since $\mathcal{S}_{d_{L_{\ell}}+1,d_{L_{\ell}},0}$ maps
$\mathbb{R}^{d_{L_{\ell}}+1}$ to $\mathbb{R}^{d^{*}_{\ell}}$, the we can ues
(22) $L$ times and obtain (26) directly. The translation invariance (2) can
also be derived from (23) directly. This completes the proof of Theorem 2. ∎

The proof of Theorem 3 is almost the same as that in [30]. The only difference
is that the pooling scheme reduces the covering number of eDCNN. It should be
highlighted that this proof is semi-trivial and we sketch it for the sake of
completeness.

At first, we introduce the definition of the $\ell^{1}$ empirical covering
number. For a set of functions $\mathcal{V}$, denote by
$\mathcal{N}_{1}(\epsilon,\mathcal{V})$ the $\ell^{1}$ empirical $\varepsilon$
covering number [31, Def. 9.3] of $\mathcal{V}$ which is the number of
elements in a least $\varepsilon$-net of $\mathcal{V}$ with respect to the
metric $\|f\|_{D,1}:=\frac{1}{|D|}\sum_{i=1}^{|D|}|f(x_{i})|$. Define

$\pi_{M}\mathcal{H}^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}}:=\left\\{\pi_{M}f:f\in\mathcal{H}^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}}\right\\}.$

It is easy to check that deep nets in
$H^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}}$ is of depth at
most

$L_{pooling}:=\frac{\sum_{j=1}^{L}d_{j-1}^{*}d_{j}^{*}}{s-1}+2L$

and with free parameter at most

$\displaystyle n_{pooling}$ $\displaystyle:=$ $\displaystyle
L_{pooling}s+\sum_{j=1}^{L}d^{*}_{L}$ $\displaystyle=$
$\displaystyle\left(\frac{\sum_{j=1}^{L}d_{j-1}^{*}d_{j}^{*}}{s-1}+2L\right)s+\sum_{j=1}^{L}d^{*}_{L}.$

The following lemma that can be derived by using the same approach as that in
[30, Lemma 4] describes the covering number of
$\pi_{M}\mathcal{H}^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}}$.

######  Lemma 10.

Let $2\leq s\leq d$ and $L\in\mathbb{N}$. For any $0<\varepsilon\leq M$, if
$d_{1}^{*},\dots,d_{L}^{*}\geq d+1$, then there holds

$\displaystyle\log_{2}\sup_{D\in\mathcal{Z}^{m}}\mathcal{N}_{1}(\epsilon,\pi_{M}\mathcal{H}^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}})$
$\displaystyle\leq$ $\displaystyle
c^{*}\left(\frac{\sum_{j=1}^{L}d_{j-1}^{*}d_{j}^{*}}{s-1}+2L\right)\log(Ld_{\max}^{*})$
$\displaystyle\left(\left(\frac{\sum_{j=1}^{L}d_{j-1}^{*}d_{j}^{*}}{s-1}+2L\right)s+\sum_{j=1}^{L}d^{*}_{L}\right)\log\frac{M}{\epsilon},$

where $c^{*}$ is an absolute constant and $d^{*}_{\max}=\max_{1\leq j\leq
L}d^{*}_{j}.$

We then use the above covering number estimate to bound generalization error
for bounded samples. Write $y_{M}=\pi_{M}y$ and $y_{i,M}=\pi_{M}y_{i}$. Define

$\mathcal{E}_{\pi_{M}}(f)=\int_{\mathcal{Z}}(f(x)-y_{M})^{2}d\rho,$

and

$\mathcal{E}_{\pi_{M},D}(f)=\frac{1}{m}\sum_{i=1}^{m}(f(x_{i})-y_{i,M})^{2}.$

The following lemma that can be derived directly from [31, Theorem 11.4] and
Lemma 10 shows the performance of eDCNN with pooling for learning bounded
samples.

######  Lemma 11.

If $M^{2}_{D}|D|^{-\theta}\rightarrow 0$ and (31) holds for some
$\theta\in(0,1/2)$, then

$\mathcal{E}_{\pi_{M}}(\pi_{M}f^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{D,L_{L},\dots,L_{1}})-\mathcal{E}_{\pi_{M},D}(\pi_{M}f^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{D,L_{L},\dots,L_{1}})\rightarrow
0$

holds almost surely.

We then sketch the proof of Theorem 3 as follows.

###### Proof of Theorem 3.

Based on the above lemmas, Theorem 3 can be derived as the standard approach
in the proof of [30, Theorem 1] by dividing the generalization error into
eight items. The only thing difference is that to guarantee the universal
approximation property of
$f^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{D,L_{L},\dots,L_{1}}$, it follows from
Theorem 2 that if $d_{1}^{*},\dots,d_{\ell}^{*}\geq d+1$, then for any
$\varepsilon>0$, there exists some
$g_{\varepsilon}\in\mathcal{H}^{s,R,d^{*}_{L-1},\dots,d^{*}_{0},0}_{L_{L},\dots,L_{1}}$
with sufficiently large $\sum_{j=1}^{L}d_{j-1}^{*}d_{j}^{*}$ such that

$\|f_{\rho}-g_{\varepsilon}\|_{L^{2}({\rho_{X}})}^{2}\leq\varepsilon.$

The strongly universal consistency then can be derived by using the same
method as that in proving [30, Theorem 1] directly. Furthermore, the
translation-invariance (32) can be derived from (2). This completes the proof
of Theorem 3. ∎