111This Thesis has been Submitted to the School of Computer Science, the
University of Sydney in Fulfilment of the requirements for the Degree of
Master of Philosophy of Shan Lin on 26-Dec-2018, but has not been published.
The thesis is available at https://ses.library.usyd.edu.au/handle/2123/20315.

# Generalization Bounds for Convolutional Neural Networks

Shan Lin<EMAIL_ADDRESS>
Department of Computer Science
University of Sydney
Sydney, New South Wales, Australia Jingwei Zhang<EMAIL_ADDRESS>
Department of Computer Science
University of Sydney
Sydney, New South Wales, Australia

###### Abstract

Convolutional neural networks (CNNs) have achieved breakthrough performances
in a wide range of applications including image classification, semantic
segmentation, and object detection. Previous research on characterizing the
generalization ability of neural networks mostly focuses on fully connected
neural networks (FNNs), regarding CNNs as a special case of FNNs without
taking into account the special structure of convolutional layers. In this
work, we propose a tighter generalization bound for CNNs by exploiting the
sparse and permutation structure of its weight matrices. As the generalization
bound relies on the spectral norm of weight matrices, we further study
spectral norms of three commonly used convolution operations including
standard convolution, depthwise convolution, and pointwise convolution.
Theoretical and experimental results both demonstrate that our bounds for CNNs
are tighter than existing bounds.

Keywords: Convolutional Neural Networks, Generalization Bounds, Covering
Number

##  1 Introduction

Convolutional neural networks (CNNs) have led state-of-the-art performances in
various applications including image classification (Krizhevsky et al., 2012),
semantic segmentation (Long et al., 2015), and object detection (Ren et al.,
2015; Redmon et al., 2016). They have significantly outperformed traditional
machine learning approaches on large-scale datasets. However, there exists a
gap between their experimental success and theoretical understanding, as
previous tools in statistical learning theory become powerless for neural
networks. A commonly held view suggests that a heavily overparameterized
neural network can easily overfit (Zhang et al., 2016) and thus will result in
poor predictions for unseen data, which is clearly in contrast to empirical
evidence.

This motivates us to study neural networks from a theoretical perspective so
as to better understand how deep learning algorithm works. We focus on a key
problem in supervised learning, which is the models’ ability to generalize.
For classification, the generalization performance of a model can be measured
by the expected zero-one loss on the underlying input distribution, referred
to as classification error. Indeed, generalizable models are attained through
the combined efforts from various aspects including networks architectures and
optimization algorithms. In this work, we pay close attention to architectures
and parameters, and propose a generalization bound specifically designed for
CNNs.

Previous research on characterizing the generalization capability of neural
networks mostly focuses on fully connected neural networks (FNNs), regarding
CNNs as a special case of FNNs. Although these bounds are also applicable for
CNNs, the sparsity characteristic of weight matrices for convolutional layers
is not fully exploited. Different from FNNs, CNNs have at least one
convolutional layer which uses convolution operation instead of matrix
multiplication. In this operation, a small-sized filter is applied to the
feature map in a sliding-window fashion to obtain properties of sparse
interaction and parameter sharing. We show that convolutional layers can be
transformed to fully connected layers whose weight matrices are sparse and
have shared weights. By exploiting this structure, it is expected to achieve a
tighter bound for CNNs compared with those bounds derived from FNNs.

Our approach to deriving generalization bounds for CNNs is closely related to
(Bartlett et al., 2017; Neyshabur et al., 2017a; Golowich et al., 2018; Li et
al., 2018). In these works, they upper bounded generalization error of a given
neural network in terms of complexity measures depending on the Lipschitz
constants of activation functions and norms of weight matrices. Different from
previous methods, we propose to bound model complexity by the norm of
convolutional weights rather than that of the corresponding fully connected
weight matrices generated from convolutional weights. To achieve this goal, we
make use of the sparsity and permutation structure of the convolutional layer,
yielding a tighter bound in comparison with those bounds directly derived from
FNNs. Our main contributions are summarized as follows.

  * •

We propose a generalization bound for general convolutional neural networks
that contain both fully connected layers and convolutional layers. By
transforming convolution operation into a multiplication of input feature map
and the corresponding fully connected matrix generated by convolutional
weights, we are able to compare the proposed generalization bound with
existing bounds for FNNs. We show that the proposed bound is tighter under
certain conditions, and further provide experimental results on architectures
of MobileNet V1 (Howard et al., 2017) and MobileNet V2 (Sandler et al., 2018)
to validate our theoretical results.

  * •

We analyzes spectral norms of different convolution operations including
standard convolution operation, depthwise operation, and pointwise operation.
We show that the spectral norm of weight matrices generated by convolutional
weights can be upper bounded by certain norms of the convolutional weights.
The proposed generalization bound relies on the spectral norm of weight
matrices of layers in CNNs.

The rest of this paper is organized as follows. We first review related works
in Section 2. In Section 3, we briefly introduce notations, definitions, and
lemmas that will be used later in this paper. Then, we present our main
theorem on bounding generalization error of CNNs in Section 4. Section 5
provides discussions on spectral norm of different convolution operations, and
Section 6 provides theoretical and experimental comparisons of various
existing generalization bounds. Section 7 concludes the paper.

##  2 Related Work

Research on characterizing generalization behaviours of neural networks has
attracted increasing attention over the last few years. Neyshabur et al.
(2017b) investigated multiple measures of model capacity that can be used to
bound the generalization error of deep neural networks (DNNs), including the
number of parameters, VC dimension, flatness and sharpness, and margin and
norm based complexities. Among these complexity measures, the number of
parameters and VC dimension increase as the size of network grows (Anthony and
Bartlett, 2009). Besides, proper definitions of flatness are currently lacked
(Dinh et al., 2017). Thus both of them are not effective in explaining
generalization of deep learning. In terms of margin and norm based
complexities, let $n$ denote the size of a given sample, $L$ denote the depth
of networks, $D$ denote the maximum width of each layer, and $A_{i}$ be the
weight matrix for layer $i\in\\{1,...,L\\}$. For a fully connected neural
network with rectified linear unit (ReLU) activation function, Neyshabur et
al. (2015) introduced a complexity measure based on a broad definition of norm
with an exponential dependence on depth. The bound is
$\widetilde{\mathcal{O}}(2^{L}\prod_{i=1}^{L}\|A_{i}\|_{F}/\sqrt{n})$, where
$\|\cdot\|_{F}$ represents the $F$-norm of a matrix. Later, Bartlett et al.
(2017) and Neyshabur et al. (2017a) proposed similar bounds by the product of
Lipschitz constants of activation functions and norms of weight matrices,
which is
$\widetilde{\mathcal{O}}\left(\prod_{i=1}^{L}\|A_{i}\|_{\sigma}\sqrt{L^{3}D}/\sqrt{n}\right)$,
where $\|\cdot\|_{\sigma}$ denotes the spectral norm of a matrix, which equals
to the largest singular value. Recently, Golowich et al. (2018) proposed a
generalization bound of
$\widetilde{\mathcal{O}}\left(\prod_{i=1}^{L}\|A_{i}\|_{F}\cdot\min\left\\{1/\sqrt[4]{n},\sqrt{L/n}\right\\}\right)$,
which is fully independent of the depth of neural nets at the cost of a slower
convergence rate. Li et al. (2018) achieved a tighter bound of
$\widetilde{\mathcal{O}}\left(\prod_{i=1}^{L}\|A_{i}\|_{\sigma}\sqrt{LD^{2}}/\sqrt{n}\right)$
for ultra-deep neural networks when the layer depth $L$ is much greater than
$D$. More recently, Arora et al. (2018) experimentally showed that the weight
matrices of layers are noise tolerant in the sense that the influences will
decay at higher layers. On account of this property, they proposed to compress
the neural nets first and obtained a tighter generalization bound.

Besides generalization bounds, researchers are also interested in
understanding neural networks theoretically from other aspects including
hardness of training neural networks (Blum and Rivest, 1989; Livni et al.,
2014; Brutzkus and Globerson, 2017; Shamir, 2018), expressiveness of neural
networks (Hornik et al., 1989; Bengio and Delalleau, 2011; Eldan and Shamir,
2016; Sharir and Shashua, 2017), the surfaces of loss functions (Hochreiter
and Schmidhuber, 1995; Choromanska et al., 2015; Keskar et al., 2016;
Kawaguchi, 2016; Dinh et al., 2017; Draxler et al., 2018; Garipov et al.,
2018), stochastic gradient descent (Dauphin et al., 2014; Ge et al., 2015,
2016; Jin et al., 2017), and information theory (Xu and Raginsky, 2017; Zhang
et al., 2018).

Focusing on CNNs, Li et al. (2018) discussed generalization bounds of CNNs
composed of orthogonal filters and Arora et al. (2018) investigated model
compression of CNNs. Du et al. (2018) studied the sample complexity of CNNs
based on one convolutional filter, and showed that the sample complexity of
CNNs is $\mathcal{O}(m/\epsilon^{2})$ for a $m$-dimensional filter, which is
much smaller than that of FNNs $\mathcal{O}(d/\epsilon^{2})$ as $m\ll d$. We
also refer readers to (Sharir and Shashua, 2017; Brutzkus and Globerson, 2017;
Du et al., 2017; Du and Goel, 2018) for more theoretical analysis on CNNs.

##  3 Preliminaries

In this section, we briefly introduce the definitions of generalization error,
Rademacher complexity, and ramp loss for multiclass classification. We also
formulate the notations of neural networks including fully connected neural
networks, fully convolutional neural networks, and general convolutional
neural networks.

###  3.1 Generalization Error

In a classification problem, training examples are assumed to be independently
and identically distributed according to some fixed but unknown probability
distribution $\mathcal{D}$. Given a hypothesis set $\mathcal{F}$, the expected
risk of a hypothesis $f\in\mathcal{F}$ with respect to distribution
$\mathcal{D}$ is defined by

$\mathcal{R}_{\mathcal{D}}(f)=\mathbb{E}_{(x,y)\sim\mathcal{D}}[\mathbf{1}_{f(x)\neq
y}].$ (1)

Our goal is to learn a hypothesis $f\in\mathcal{F}$ which minimizes the
expected risk. However, the expected risk is not directly accessible as the
underlying distribution is unknown given a finite sample. Instead, we use an
unbiased estimator of expected risk named empirical risk. Given a sample
$S=\left((x_{1},y_{1}),...,(x_{n},y_{n})\right)$, the empirical risk of
hypothesis $f\in\mathcal{F}$ is defined by

$\widehat{\mathcal{R}}_{S}(f)=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}_{f(x_{i})\neq
y_{i}}.$ (2)

Minimizing empirical risk will probably lead to overfitting, especially when
the hypothesis set is overly expressive, which results in a large gap between
empirical risk and expected risk. According to statistical learning theory,
such gap can be bounded by the empirical Rademacher complexity of the
hypothesis set, which is defined in the following.

###### Definition 1

(Empirical Rademacher complexity) Given a sample
$Z=\left(z_{1},...,z_{n}\right)\in\mathcal{Z}^{n}$ and a set of real-valued
functions $\mathcal{F}$ defined on $\mathcal{Z}$, the empirical Rademacher
complexity is defined by

$\mathfrak{R}_{Z}(\mathcal{F})=\frac{1}{n}\mathbb{E}_{\tau}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\tau_{i}f(z_{i})\right],$
(3)

where $\tau_{i}$s are Rademacher variables which are uniform random variables
taking values in $\\{-1,+1\\}$.

###  3.2 Loss Function

As the zero-one loss is non-smooth, it is difficult to minimize empirical
risk. In practise, we use surrogate loss functions such as hinge loss and
cross entropy loss. Here, we focus on ramp loss which is defined using the
concept of margin. For a classification problem with $k$ target classes, the
margin of a training example $(x,y)\in\mathcal{X}\times\mathcal{Y}$ with
respect to a hypothesis $f\in\mathcal{F}$ is defined by

$f(x)_{y}-\max_{j\neq y,j\in\\{1,...,k\\}}f(x)_{j}.$ (4)

Then the ramp loss $\ell_{\eta}$ is given by

$\ell_{\eta}\left(f(x),y\right)\triangleq
g_{\eta}\left(-\left(f(x)_{y}-\max_{j\neq y}f(x)_{j}\right)\right),$ (5)

where $g_{\eta}(r):\mathbb{R}\to\mathbb{R}^{+}$ is a function defined by

$g_{\eta}(r)=\begin{cases}0,&{r<-\eta}\\\ 1+r/\eta,&{-\eta\leq r\leq 0}\\\
1,&{r>0}.\end{cases}$

Thus, the empirical risk for a classification problem with respect to ramp
loss $\ell_{\eta}$ and the training sample $S$ can be formulated as

$\widehat{\mathcal{R}}_{S,\ell_{\eta}}(f)=\frac{1}{n}\sum_{i=1}^{n}\ell_{\eta}\left(f(x_{i}),y_{i}\right)=\frac{1}{n}\sum_{i=1}^{n}g_{\eta}\left(-\left(f(x_{i})_{y_{i}}-\max_{j\neq
y_{i}}f(x_{i})_{j}\right)\right).$ (6)

With this in view, the expected risk can be bounded in the following theorem.

###### Theorem 2

(Bartlett et al. (2017), Lemma 3.1) Given a hypothesis set $\mathcal{F}$, a
sample $S=((x_{1},y_{1}),...,(x_{n},y_{n}))$ of size $n$, and any $\eta>0$,
with probability at least $1-\delta$, each hypothesis $f\in\mathcal{F}$
satisfies

$\mathcal{R}_{\mathcal{D}}(f)\leq\widehat{\mathcal{R}}_{S,\ell_{\eta}}(f)+2\mathfrak{R}_{S}(\mathcal{F}_{\eta})+3\sqrt{\frac{\ln(1/\delta)}{2n}},$
(7)

where $\mathcal{F}_{\eta}$ is the $\ell_{\eta}$ loss function class with
respect to hypothesis set $\mathcal{F}$ and is defined as

$\mathcal{F}_{\eta}\triangleq\left\\{(x,y)\to\ell_{\eta}\left(f(x),y\right):f\in\mathcal{F}\right\\}.$
(8)

###  3.3 Neural Networks

Given a neural network, let $L$ denote the number of layers, and
$(\sigma_{1},..,\sigma_{L})$ denote fixed Lipschitz functions, e.g., rectified
linear unit (ReLU) and max pooling function (Bartlett et al., 2017). We assume
that $\sigma_{i}$ is $\rho_{i}$-Lipschitz satisfying $\sigma_{i}(0)=0$. In
this paper, we discuss three types of neural networks including fully
connected neural networks (FNNs), fully convolutional neural networks (FCNNs),
and general convolutional neural networks (CNNs). They can be formulated in a
unified approach. The key observation is that the convolution operation can be
represented by matrix multiplication, see Section 3.3.1 for details. Let
$X=(x_{1},...,x_{n})^{\top}\in\mathbb{R}^{d\times n}$ denote the given input
data, where $n$ is the number of the training examples. We list the
formulations in the following.

  * •

FNNs: Let $\mathbf{A}=(A_{1},...,A_{L})$ denote the weight matrices of all
layers in FNNs, where $A_{i}\in\mathbb{R}^{d_{i}\times d_{i-1}}$ and
$d_{0}=d$. Then, FNNs can be formulated as

$F_{\mathbf{A}}(X)\triangleq\sigma_{L}(A_{L}\sigma_{L-1}(A_{L-1}\cdots\sigma_{1}(A_{1}X)\cdots)).$
(9)

  * •

FCNNs: Let $\mathbf{W}=(W_{1},...,W_{L})$ be the convolutional weights of all
layers where convolutional weight $W_{i}\in\mathbb{R}^{c_{i}\times r_{i}}$
contains $c_{i}$ convolutional filters, each of which has dimension $r_{i}$.
Let matrix $Z_{i}\in\mathbb{R}^{d_{i}\times n}$ denote the output of the
$i_{th}$ layer, which is also the input of the $(i+1)_{th}$ layer. Thus we
have $Z_{0}=X$ and $d_{0}=d$. Let $\mu_{i}$ be the function representing
convolution operation for the $i_{th}$ layer taking convolutional weight
$W_{i}$ and $Z_{i-1}$ as input. Then, we can formulate $Z_{i}$ in terms of
$Z_{i-1}$ as

$Z_{i}=\sigma_{i}(\mu_{i}(W_{i},Z_{i-1})).$ (10)

Note that the convolutional weight $W_{i}$ can be in any shape as long as its
total dimension is $r_{i}$. Such convolution operation can be rewritten as
matrix multiplication, see Section 3.3.1 for detail. Let
$\gamma_{i}(W_{i})\in\mathbb{R}^{d_{i}\times d_{i-1}}$ denote the fully
connected matrix generated by convolutional weight $W_{i}$, and we have

$\mu_{i}(W_{i},Z_{i-1})=\gamma_{i}(W_{i})Z_{i-1}.$ (11)

Hence, FCNNs can be formulated as

$\displaystyle F_{\mathbf{W}}(X)\triangleq$
$\displaystyle\sigma_{L}(\mu_{L}(W_{L},\sigma_{L-1}(\mu_{L-1}(W_{L-1},\cdots\sigma_{1}(\mu_{1}(W_{1},X))\cdots)))),$
(12)

or,

$\displaystyle F_{\mathbf{W}}(X)\triangleq$
$\displaystyle\sigma_{L}(\gamma_{L}(W_{L})\sigma_{L-1}(\gamma_{L-1}(W_{L-1})\cdots\sigma_{1}(\gamma_{1}(W_{1})X)\cdots)).$
(13)

  * •

CNNs: The formulations of CNNs are obtained by a combination of (9) and (13).
Let $\mathbf{C}=(C_{1},...,C_{L})$ be the unified fully connected matrices,
then CNNs can be written as

$F_{\mathbf{C}}(X)\triangleq\sigma_{L}(C_{L}\sigma_{L-1}(C_{L-1}\cdots\sigma_{1}(C_{1}X)\cdots)),$
(14)

where matrix $C_{i}$ equals $A_{i}$ if the $i_{th}$ layer is fully connected
or $C_{i}$ equals $\gamma_{i}(W_{i})$ if the layer is convolutional and
$\gamma_{i}(W_{i})$ satisfies (11).

####  3.3.1 the fully connected matrix for one convolutional layer

This section illustrates how fully connected matrices are generated by
convolution operations. Let convolutional weight
$W=(w^{1},...,w^{c})\in\mathbb{R}^{c\times r}$ denote the $c$ convolutional
filters for one layer with the same dimension $r$. Let
$Z_{input}=(Z^{1},...,Z^{n})\in\mathbb{R}^{d_{input}\times n}$ denote the $n$
input examples with dimension $d_{input}$. Note that we only need to figure
out how one convolutional filter $w^{i},i\in\\{1,...,c\\}$ operates on one
input example $Z^{j},j\in\\{1,...,n\\}$, and this can be easily extended to
multiple filters and multiple training examples.

Assuming that each filter $w^{i}$ performs $m$ operations on one example
$Z^{j}$, each operation selects $r$ elements out of the
$d_{input}$-dimensional features of $Z^{j}$. For the $k_{th}$ operation, let
vector $S_{k}\in\mathbb{R}^{r}$ represent the indices of the $r$ elements
chosen from the $d_{input}$-dimensional features, and let
$w^{i}_{S_{k}}\in\mathbb{R}^{d_{input}}$ denote the vector derived from
$w^{i}$ whose elements are re-arranged to the places indexed by $S_{k}$ while
filling the other places with zeros. Analogously, let
$Z^{j}_{S_{k}}\in\mathbb{R}^{r}$ denote the vector which selects $r$ elements
of $Z^{j}$ according to $S_{k}$. Then we have

$w^{i}_{S_{k}}Z^{j}=w^{i}Z^{j}_{S_{k}}.$ (15)

For a better understanding, we illustrate this procedure using an example with
a 2-dimensional convolutional filter $w\in\mathbb{R}^{2\times 2}$ and a
2-dimensional input example $Z\in\mathbb{R}^{3\times 4}$ as follows. Let

$w=\begin{bmatrix}w_{1,1}&w_{1,2}\\\
w_{2,1}&w_{2,2}\end{bmatrix},\;\text{and}\;Z=\begin{bmatrix}Z_{1,1}&Z_{1,2}&Z_{1,3}&Z_{1,4}\\\
Z_{2,1}&Z_{2,2}&Z_{2,3}&Z_{2,4}\\\
Z_{3,1}&Z_{3,2}&Z_{3,3}&Z_{3,4}\end{bmatrix},$ (16)

then a standard convolution operation $\mu(w,Z)$ with step size one performs
$m=6$ operations and generates the following result

$\mu(w,Z)=\begin{bmatrix}\sum_{i=1}^{2}\sum_{j=1}^{2}w_{i,j}Z_{i,j}&\sum_{i=1}^{2}\sum_{j=1}^{2}w_{i,j}Z_{i,j+1}&\sum_{i=1}^{2}\sum_{j=1}^{2}w_{i,j}Z_{i,j+2}\\\
\sum_{i=1}^{2}\sum_{j=1}^{2}w_{i,j}Z_{i+1,j}&\sum_{i=1}^{2}\sum_{j=1}^{2}w_{i,j}Z_{i+1,j+1}&\sum_{i=1}^{2}\sum_{j=1}^{2}w_{i,j}Z_{i+1,j+2}\end{bmatrix}.$
(17)

If we reshape $Z$ to one dimension and use $1$ as the starting index, then the
index vectors become

$(S_{1},..,S_{6})^{\top}=\begin{bmatrix}1&2&5&6\\\ 2&3&6&7\\\ 3&4&7&8\\\
5&6&9&10\\\ 6&7&10&11\\\ 7&8&11&12\\\ \end{bmatrix},$ (18)

and we have

$\gamma(w)=\setcounter{MaxMatrixCols}{12}\begin{bmatrix}w_{1,1}&w_{1,2}&0&0&w_{2,1}&w_{2,2}&0&0&0&0&0&0\\\
0&w_{1,1}&w_{1,2}&0&0&w_{2,1}&w_{2,2}&0&0&0&0&0\\\
0&0&w_{1,1}&w_{1,2}&0&0&w_{2,1}&w_{2,2}&0&0&0&0\\\
0&0&0&0&w_{1,1}&w_{1,2}&0&0&w_{2,1}&w_{2,2}&0&0\\\
0&0&0&0&0&w_{1,1}&w_{1,2}&0&0&w_{2,1}&w_{2,2}&0\\\
0&0&0&0&0&0&w_{1,1}&w_{1,2}&0&0&w_{2,1}&w_{2,2}\\\ \end{bmatrix}.$ (19)

After reshaping $\mu(w,Z)$ in (17) to one dimension, we have

$\mu(w,Z)=\gamma(w)Z.$ (20)

Using the above notations, $\gamma(W)$ can be easily formulated by

$\gamma(W)=(w^{1}_{S_{1}},\dots,w^{1}_{S_{m}},w^{2}_{S_{1}},\dots,w^{2}_{S_{m}},\dots,w^{c}_{S_{1}},\dots,w^{c}_{S_{m}})^{\top}\in\mathbb{R}^{d_{output}\times
d_{input}},$ (21)

where the output dimension $d_{output}$ is equal to $mc$.

At last, it is worth mentioning that the output dimension $m$ for one filter
and the index vector $S_{k}$ varies for different convolution operations
represented by $\mu$, depending on the shape of convolutional filters, the
shape of input data, and step size. As a matter of fact, this notation allows
the flexibility of applying different convolution operations in different
layers as long as they can all be transformed to the same kind of formulation
as (19).

##  4 Generalization Bounds for Neural Networks

This section presents our main theorem on generalization bounds for different
neural networks. Our work extends the generalization bound proposed by
(Bartlett et al., 2017) which is derived in terms of Lipschitz constants of
functions and norms of matrices. We first introduce a complexity measure that
will be used in the main theorem.

###### Definition 3

Given a CNN $F_{\mathbf{C}}$ defined in (14). Let
$(\sigma_{1},...,\sigma_{L})$ be some fixed functions where $\sigma_{i}$ is
$\rho_{i}$-Lipschitz satisfying $\sigma_{i}(0)=0$. Let
$\mathbf{C}=(C_{1},...,C_{L})$ be fully connected weight matrices, where
$C_{i}\in\mathbb{R}^{d_{i}\times d_{i-1}}$ and $d_{0}=d$. Let $S_{\mathbf{A}}$
and $S_{\mathbf{W}}$ denote the index sets of fully connected layers and
convolutional layers, respectively. Then if the index $i$ is in
$S_{\mathbf{A}}$, we have $C_{i}=A_{i}$. Otherwise, we have $i\in
S_{\mathbf{W}}$ and $C_{i}=\gamma_{i}(W_{i})\in\mathbb{R}^{d_{i}\times
d_{i-1}}$, where $W_{i}\in\mathbb{R}^{c_{i}\times r_{i}}$ and each filter in
$W_{i}$ is of size $r_{i}$. Let $(a_{1},...,a_{L})$ and $(s_{1},...s_{L})$ be
some real values. Assuming that $\|W_{i}\|_{F}\leq a_{i}$ and
$\|\gamma_{i}(W_{i})\|_{\sigma}\leq s_{i}$ for $i\in S_{\mathbf{W}}$, and
$\|A_{i}\|_{F}\leq a_{i}$ and $\|A_{i}\|_{\sigma}\leq s_{i}$ for $i\in
S_{\mathbf{A}}$, we define the sensitive complexity for $F_{\mathbf{C}}$ with
respect to $\mathbf{C}$ as

$\mathbf{\mathscr{R}}_{\mathbf{C}}=\left(2\prod_{i=1}^{L}\rho_{i}s_{i}\right)\left(\sum_{i\in
S_{\mathbf{A}}}\frac{d_{i}^{2}d_{i-1}^{2}a_{i}}{s_{i}}+\sum_{i\in
S_{\mathbf{W}}}\frac{c_{i}^{2}r_{i}^{2}a_{i}\sqrt{d_{i}/c_{i}}}{s_{i}}\right)L^{2}.$
(22)

###### Remark 4

FNNs and FCNNs can be viewed as special cases of CNNs when $S_{\mathbf{A}}$ is
empty or $S_{\mathbf{W}}$ is empty. Hence their corresponding sensitive
complexity $\mathscr{R}_{\mathbf{A}}$ and $\mathscr{R}_{\mathbf{W}}$ can be
defined as

$\mathscr{R}_{\mathbf{A}}=\left(2\prod_{i=1}^{L}\rho_{i}s_{i}\right)\left(\sum_{i=1}^{L}\frac{d_{i}^{2}d_{i-1}^{2}a_{i}}{s_{i}}\right)L^{2},$
(23)

and

$\mathscr{R}_{\mathbf{W}}=\left(2\prod_{i=1}^{L}\rho_{i}s_{i}\right)\left(\sum_{i=1}^{L}\frac{c_{i}^{2}r_{i}^{2}a_{i}\sqrt{d_{i}/c_{i}}}{s_{i}}\right)L^{2}.$
(24)

Based on the above complexity measures, we obtain the following generalization
bound.

###### Theorem 5

(Generalization Bound for Convolutional Neural Networks) Given a training
sample $S=\\{(x_{1},y_{1}),...,(x_{n},y_{n})\\}$ of size $n$, each
$(x_{i},y_{i})$ is i.i.d. according to some unknown distribution
$\mathcal{D}$. Let $X=(x_{1},...,x_{n})^{\top}\in\mathbb{R}^{d\times n}$ be
the $n$ inputs. For a convolutional neural network $F_{\mathbf{C}}$ defined in
(14), let $(\sigma_{1},...,\sigma_{L})$ be some fixed functions where
$\sigma_{i}$ is $\rho_{i}$-Lipschitz satisfying $\sigma_{i}(0)=0$. Then with
probability at least $1-\delta$, we have

$\displaystyle\mathcal{R}_{\mathcal{D}}(F_{\mathbf{C}})\leq\widehat{\mathcal{R}}_{S,\ell_{\eta}}(F_{\mathbf{C}})+\mathcal{O}\left(\left(\frac{\|X\|_{F}\mathscr{R}_{\mathbf{C}}}{\eta}\right)^{\frac{1}{4}}n^{-\frac{5}{8}}+\sqrt{\frac{\ln(1/\delta)}{n}}\right),$
(25)

where $\mathscr{R}_{\mathbf{C}}$ represents the corresponding complexity
measure for $F_{\mathbf{C}}$ defined in (22).

###### Remark 6

Generalization bounds for FNNs $F_{\mathbf{A}}$ and FCNNs $F_{\mathbf{W}}$ can
be similarly obtained by substituting the complexity term
$\mathscr{R}_{\mathbf{C}}$ in (25) with $\mathscr{R}_{\mathbf{A}}$ and
$\mathscr{R}_{\mathbf{W}}$, respectively.

Before diving into the proof details of the main theorem, we first draw an
outline as shown in the chart below.

Generalization ErrorRademacher ComplexityCovering Number of CNNsCovering
Number of Single Layer(c)(b)(a)

Here, $(a)$ denotes induction on each layer, $(b)$ represents Dudley’s Entropy
Integral, and $(c)$ represents Theorem 2. The details are demonstrated in
following subsections.

  * •

The first step is to bound the covering number of a single layer, see
subsection 4.1. We consider two situations where the layers are convolutional
or fully connected.

  * •

The next step is to compute the overall covering number of general
convolutional neural networks by a straightforward induction on layers, as
indicated by $(a)$, see subsection 4.2.

  * •

Finally, we relate the covering number of a convolutional neural network to
its Rademacher complexity via Dudley’s entropy integral as indicated by $(b)$.
Substituting the above results into Theorem 2 yields our main Theorem 5 as
indicated by $(c)$, see subsection 4.3.

###  4.1 Covering Number Bound for a Single Neural Network Layer

We study covering number bounds for a single neural network layer, either
fully connected or convolutional. We first introduce the definitions of
$\epsilon$-cover and covering number as well as their closely related concepts
named $\epsilon$-packing and packing number.

###### Definition 7

($\epsilon$-cover and covering number) Let $(V,\|\cdot\|)$ be a normed space
and $U$ be a subset of $V$. Then $U$ is called an $\epsilon$-cover of $V$ if
for any $v\in V$, there exists $u\in U$ such that $\|u-v\|\leq\epsilon.$ The
covering number of the normed space $(V,\|\cdot\|)$ with any $\epsilon>0$ is
the size of the smallest $\epsilon$-cover, which is defined by
$\mathcal{N}(V,\epsilon,\|\cdot\|)\triangleq\min\\{\,|U|:U$ is an
$\epsilon$-cover of $V\\}$.

###### Definition 8

($\epsilon$-packing and packing number) Let $(V,\|\cdot\|)$ be a normed space,
and let $U\subseteq V$. Then $U$ is an $\epsilon$-packing of $V$ if for any
$v,v^{\prime}\in U$, the inequality $\|v-v^{\prime}\|>\epsilon$ holds. The
packing number is thus defined by
$\mathcal{M}(V,\epsilon,\|\cdot\|)\triangleq\max\\{\,|U|:U$ is an
$\epsilon$-packing of $V\\}$.

The following lemma provides a covering number bound with respect to $l_{2}$
norm for a single $a$-bounded vector, which will be used in bounding the
covering number of a single neural network layer. This proof extends from (Wu,
2016).

###### Lemma 9

Let $W\triangleq\\{w:w\in\mathbb{R}^{r},\,\|w\|_{2}\leq a\\}$, then for any
$\epsilon>0$, the covering number of $W$ can be bounded by

$\ln\mathcal{N}\left(W,\epsilon,\|\cdot\|_{2}\right)\leq
r\ln\left(1+\frac{2a}{\epsilon}\right).$ (26)

Proof  Let $M$ be the maximum $\epsilon$-packing of $W$ w.r.t $l_{2}$ norm,
then $|M|=\mathcal{M}(W,\epsilon,\|\cdot\|_{2})$. In the following, we first
show that $\mathcal{N}\left(W,\epsilon,\|\cdot\|_{2}\right)\leq|M|$ and then
show that $|M|\leq\left(1+\frac{2a}{\epsilon}\right)^{d}$.

For the first part, we demonstrate that $M$ is also an $\epsilon$-cover of
$W$. Indeed, for any $w\in W,m\in M$, we must have $\|w-m\|_{2}\leq\epsilon$.
Otherwise, $\\{w\\}\bigcup M$ is a larger $\epsilon$-packing of $W$, which
contradicts the definition of $M$. For the second part, let $B(w,\epsilon)$
denote the $\epsilon$-ball centered at $w$. Because $M$ is an
$\epsilon$-packing of $W$, the set of $\epsilon/2$-balls centered at points in
$M$ are disjoint and the union is covered within the $(a+\epsilon/2)$-ball
centered at the origin. Hence,

$\displaystyle\bigcup_{m\in M}B(m,\epsilon/2)$ $\displaystyle\leq
B(0,a+\epsilon/2)$ (27) $\displaystyle|M|B(0,\epsilon/2)$ $\displaystyle\leq
B(0,a+\epsilon/2)$ $\displaystyle|M|(\epsilon/2)^{d}B(0,1)$
$\displaystyle\leq(a+\epsilon/2)^{d}B(0,1)$ $\displaystyle|M|$
$\displaystyle\leq\left(\frac{2a}{\epsilon}+1\right)^{d}.$

Based on this lemma, we can bound the covering number for a single fully
connected layer or a convolutional layer. In the following, we use $A$ and $W$
to denote the weight matrix for a fully connected layer and a convolutional
layer, respectively.

###### Lemma 10

Let $A\in\mathbb{R}^{d_{output}\times d_{input}}$ be the matrix for a fully
connected layer satisfying $\|A\|_{F}\leq a$, and
$Z\in\mathbb{R}^{d_{input}\times n}$ be a matrix with bounded $F$-norm
representing the given input. We have the following covering number bound for
this fully connected layer

$\ln\mathcal{N}\left(\left\\{AZ:\|A\|_{F}\leq
a\right\\},\epsilon,\|\cdot\|_{F}\right)\leq
d_{input}d_{output}\ln\left(1+\frac{2a\|Z\|_{F}}{\epsilon}\right).$ (28)

Proof  Let $\widehat{A}$ be in the $\epsilon$-cover of $\\{A:\|A\|_{F}\leq
a\\}$ such that $\|A-\widehat{A}\|_{F}\leq\epsilon$. Then,

$\|AZ-\widehat{A}Z\|_{F}\leq\|A-\widehat{A}\|_{F}\|Z\|_{F}\leq\|Z\|_{F}\epsilon.$
(29)

This shows that any $\epsilon$-cover of $\\{A:\|A\|_{F}\leq a\\}$ is also an
$\epsilon\|Z\|_{F}$-cover for $\\{AZ:\|A\|_{F}\leq a\\}$, i.e.,

$\ln\mathcal{N}\left(\left\\{AZ:\|A\|_{F}\leq
a\right\\},\epsilon,\|\cdot\|_{F}\right)\leq\ln\mathcal{N}\left(\left\\{A:\|A\|_{F}\leq
a\right\\},\frac{\epsilon}{\|Z\|_{F}},\|\cdot\|_{F}\right).$ (30)

To get the cover number of $A$, we reshape it into a one dimensional vector
$\bar{A}\in\mathbb{R}^{d_{input}d_{output}}$. Then the $l_{2}$-norm of
$\bar{A}$ is equivalent to the $F$-norm of $A$, i.e.,
$\|\bar{A}\|_{2}=\|A\|_{F}\leq a$. Hence by Lemma 9, we have

$\ln\mathcal{N}\left(\\{A:\|A\|_{F}\leq
a\\},\epsilon,\|\cdot\|_{F}\right)=\ln\mathcal{N}\left(\\{\bar{A}:\|\bar{A}\|_{2}\leq
a\\},\epsilon,\|\cdot\|_{2}\right)\leq
d_{input}d_{output}\ln\left(1+\frac{2a}{\epsilon}\right).$ (31)

Combining (30) and (31) concludes the proof.

###### Lemma 11

Let $W=(w^{1},...,w^{c})\in\mathbb{R}^{c\times r}$ satisfying $\|W\|_{F}\leq
a$ and $Z\in\mathbb{R}^{d\times n}$ with bounded $\|Z\|_{F}$ denote the
convolutional weight and the given input for one convolutional layer,
respectively. Assuming that each filter $w^{i}$ in $W$ performs $m$ operations
on $Z$, then the output is $\mu(W,Z)\in\mathbb{R}^{mc\times n}$. We have the
following covering number bound for this convolutional layer

$\ln\mathcal{N}\left(\\{\mu(W,Z):\|W\|_{F}\leq
a\\},\epsilon,\|\cdot\|_{F}\right)\leq
cr\ln\left(1+\frac{2a\sqrt{m}\|Z\|_{F}}{\epsilon}\right).$ (32)

Proof  Let $\widehat{W}=(\widehat{w}^{1},...,\widehat{w}^{c})$ be in the
$\epsilon$-cover of $\\{W:\|W\|_{F}\leq a\\}$ such that

$\|W-\widehat{W}\|_{F}=\bigg{(}\sum_{i=1}^{c}\|w^{i}-\widehat{w}^{i}\|_{2}^{2}\bigg{)}^{\frac{1}{2}}\leq\epsilon.$
(33)

Let $\gamma(W)\in\mathbb{R}^{mc\times d}$ and
$\gamma(\widehat{W})\in\mathbb{R}^{mc\times d}$ denote the corresponding fully
connected weight matrices generated by convolutional weight $W$ and
$\widehat{W}$. Next, we have

$\displaystyle\|\gamma(W)Z-\gamma(\widehat{W})Z\|_{F}\overset{(a)}{=}$
$\displaystyle\left(\sum_{i=1}^{c}\sum_{j=1}^{m}\|w^{i}_{S_{j}}Z-\widehat{w}^{i}_{S_{j}}Z\|_{2}^{2}\right)^{\frac{1}{2}}$
(34) $\displaystyle\leq$
$\displaystyle\sqrt{m}\left(\sum_{i=1}^{c}\max_{j}\|w^{i}_{S_{j}}Z-\widehat{w}^{i}_{S_{j}}Z\|_{2}^{2}\right)^{\frac{1}{2}}$
$\displaystyle\overset{(b)}{=}$
$\displaystyle\sqrt{m}\left(\sum_{i=1}^{c}\max_{j}\|(w^{i}-\widehat{w}^{i})Z_{S_{j}}\|_{2}^{2}\right)^{\frac{1}{2}}$
$\displaystyle\leq$
$\displaystyle\sqrt{m}\left(\sum_{i=1}^{c}\max_{j}\|w^{i}-\widehat{w}^{i}\|_{2}^{2}\|Z_{S_{j}}\|_{F}^{2}\right)^{\frac{1}{2}}$
$\displaystyle\leq$
$\displaystyle\sqrt{m}\left(\sum_{i=1}^{c}\|w^{i}-\widehat{w}^{i}\|_{2}^{2}\|Z\|_{F}^{2}\right)^{\frac{1}{2}}$
$\displaystyle\overset{(c)}{\leq}$ $\displaystyle\sqrt{m}\epsilon\|Z\|_{F},$

where $(a)$ is due to (21), $(b)$ is from (15), and $(c)$ is due to (33).
Hence,

$\|\mu(W,Z)-\mu(\widehat{W},Z)\|_{F}=\|\gamma(W)Z-\gamma(\widehat{W})Z\|_{F}\leq\sqrt{m}\epsilon\|Z\|_{F}.$
(35)

This shows that any $\epsilon$-cover of $\\{W:\|W\|_{F}\leq a\\}$ is also a
$\sqrt{m}\epsilon\|Z\|_{F}$-cover of $\\{\mu(W,Z):\|W\|_{F}\leq a\\}$, i.e.,

$\ln\mathcal{N}\left(\\{\mu(W,Z):\|W\|_{F}\leq
a\\},\epsilon,\|\cdot\|_{F}\right)\leq\ln\mathcal{N}\left(\\{W:\|W\|_{F}\leq
a\\},\frac{\epsilon}{\sqrt{m}\|Z\|_{F}},\|\cdot\|_{F}\right).$ (36)

Similar to the proof of Lemma 10, we reshape $W$ into a one-dimensional vector
$\bar{W}\in\mathbb{R}^{cr}$. Then the $l_{2}$-norm of $\bar{W}$ is equivalent
to the $F$-norm of $W$, i.e., $\|\bar{W}\|_{2}=\|W\|_{F}\leq a$. Hence by
Lemma 9, we have

$\ln\mathcal{N}(\\{W:\|W\|_{F}\leq
a\\},\epsilon,\|\cdot\|_{F})=\ln\mathcal{N}(\\{\bar{W}:\|\bar{W}\|_{2}\leq
a\\},\epsilon,\|\cdot\|_{2})\leq cr\ln\left(1+\frac{2a}{\epsilon}\right).$
(37)

Combining (36) and (37) concludes the proof.

###### Remark 12

From Lemma 10 and Lemma 11, we can understand the advantage of convolutional
layers over fully connected layers as follows. Assuming that there are $c$
convolutional filters and each one generates $m$ outputs, we have
$d_{output}=cm$. Let convolutional weight $W$ satisfy $\|W\|_{F}\leq a$, then
the corresponding fully connected matrix satisfies
$\|\gamma(W)\|_{F}\leq\sqrt{m}a$. In order to make an appropriate comparison,
we assume that $\|A\|_{F}\leq\sqrt{m}a$. Then, given the same input
$Z\in\mathbb{R}^{d_{input}\times n}$, we have

$\frac{\ln\mathcal{N}(\\{\mu(W,Z):\|W\|_{F}\leq
a\\},\epsilon,\|\cdot\|_{F})}{\ln\mathcal{N}(\\{AZ:\|A\|_{F}\leq\sqrt{m}a\\},\epsilon,\|\cdot\|_{F})}=\mathcal{O}\left(\frac{d_{input}d_{output}}{cr}\right)=\mathcal{O}\left(\frac{md_{input}}{r}\right).$
(38)

Typically we have $r\ll d_{input}$, hence the convolutional layers have much
tighter covering number bounds then the fully connected layers.

###  4.2 Covering Number Bounds for Neural Networks

In previous section, we have obtained covering number bounds for a single
network layer that is either fully connected or convolutional. Based on these
results, this section studies covering number bounds for multilayer neural
networks including FNNs, FCNNs and CNNs. Our analysis depends on the following
lemma which shows that the covering number of a multilayer neural network can
be bounded by the product of the covering number bounds of its layers.

###### Lemma 13

(Bartlett et al. (2017), Lemma A.7) Let $(\epsilon_{1},...,\epsilon_{L})$ be
given, along with fixed Lipschitz mappings $(\sigma_{1},...,\sigma_{L})$ where
$\sigma_{i}$ is $\rho_{i}$-Lipschitz satisfying $\sigma_{i}(0)=0$. Let
$\mathbf{A}=(A_{1},...,A_{L})$ denote the fully connected weight matrices for
all layers and $X\in\mathbb{R}^{d\times n}$ be the given input data with
bounded $F$-norm. Denote by $\mathcal{H}_{X}$ the family of matrices generated
by evaluating $X$ for all neural networks $F_{\mathbf{A}}(X)$ defined in (9)
with bounded weights, i.e.,
$\mathcal{H}_{X}\triangleq\\{F_{\mathbf{A}}(X):\|A_{i}\|_{\sigma}\leq
s_{i},\forall i=1,...,L\\}$. Then, letting

$\epsilon\triangleq\sum_{j\leq
L}\epsilon_{j}\rho_{j}\prod_{l=j+1}^{L}\rho_{l}s_{l},$ (39)

we have the following $\epsilon$-covering number bound for $\mathcal{H}_{X}$:

$\mathcal{N}(\mathcal{H}_{X},\epsilon,\|\cdot\|_{F})\leq\prod_{i=1}^{L}\sup_{\mathbf{A}_{i-1},\forall
j\leq i-1,\|A_{j}\|_{\sigma}\leq
s_{j}}\mathcal{N}\left(\left\\{A_{i}F_{\mathbf{A}_{i-1}}(X):\|A_{i}\|_{\sigma}\leq
s_{i}\right\\},\epsilon_{i},\|\cdot\|_{F}\right),$ (40)

where $\mathbf{A}_{i}$ denotes $(A_{1},...,A_{i})$ and $F_{\mathbf{A}_{i}}$
denotes the network constructed using the first $i$ layers of
$F_{\mathbf{A}}$.

Based on this lemma, we first prove the covering number bound for CNNs and
then present the bounds for FNNs and FCNNs, both of which can be considered as
special cases of CNNs.

###### Lemma 14

Denote the input data by $X\in\mathbb{R}^{d\times n}$ with bounded $F$-norm.
Let $(\sigma_{1},...,\sigma_{L})$ be fixed functions where $\sigma_{i}$ is
$\rho_{i}$-Lipschitz satisfying $\sigma_{i}(0)=0$. Let
$\mathbf{C}=(C_{1},...,C_{L})$ be fully connected weight matrices of all
layers, where $C_{i}\in\mathbb{R}^{d_{i}\times d_{i-1}}$ and $d_{0}=d$. Let
$S_{\mathbf{A}}$ and $S_{\mathbf{W}}$ denote the index set of fully connected
layers and convolutional layers, respectively. Then if the layer index $i$ is
in $S_{\mathbf{A}}$, we have $C_{i}=A_{i}$. Otherwise $i\in S_{\mathbf{W}}$
and $C_{i}=\gamma_{i}(W_{i})\in\mathbb{R}^{d_{i}\times d_{i-1}}$, where
$W_{i}\in\mathbb{R}^{c_{i}\times r_{i}}$ and each filter in $W_{i}$ is of
size. Denote by $\mathcal{H}_{X}^{\mathcal{C}}$ the family of result matrices
generated by evaluating $X$ for all CNNs $F_{\mathbf{C}}$ defined in (14) with
bounded weights, i.e.,

$\displaystyle\mathcal{H}_{X}^{\mathcal{C}}\triangleq\big{\\{}F_{\mathbf{C}}(X):\|A_{i}\|_{F}\leq
a_{i},\forall i\in S_{\mathbf{A}};\;\|W_{i}\|_{F}\leq a_{i},\forall i\in
S_{\mathbf{W}};\;\|C_{i}\|_{\sigma}\leq s_{i},\forall i=1,...,L\big{\\}}.$
(41)

Let $\mathscr{R}_{\mathbf{C}}$ be defined in (22), then we have the following
covering number bound

$\displaystyle\ln\mathcal{N}\left(\mathcal{H}_{X}^{\mathcal{C}},\epsilon,\|\cdot\|_{F}\right)\leq\left(\frac{\|X\|_{F}\mathscr{R}_{\mathbf{C}}}{\epsilon}\right)^{\frac{1}{2}}.$
(42)

Proof  For any $\epsilon>0$, define $(\epsilon_{1},...,\epsilon_{L})$ by
$\epsilon_{i}=\frac{\alpha_{i}\epsilon}{\rho_{i}\prod_{l=i+1}^{L}\rho_{l}s_{l}}$
for any $\alpha_{i}>0$ satisfying $\sum_{i=1}^{L}\alpha_{i}=1$. Then we have

$\epsilon=\sum_{i\leq L}\epsilon_{i}\rho_{i}\prod_{l=i+1}^{L}\rho_{i}s_{i},$
(43)

which is of the form as (39). By Lemma 13, the covering number of
$\mathcal{H}_{X}^{\mathcal{C}}$ is bounded by

$\mathcal{N}(\mathcal{H}_{X}^{\mathcal{C}},\epsilon,\|\cdot\|_{F})\leq\prod_{i=1}^{L}\sup_{\mathbf{C}_{i-1},\forall
j\leq i-1,\|C_{j}\|_{\sigma}\leq
s_{j}}\mathcal{N}\left(\left\\{C_{i}F_{\mathbf{C}_{i-1}}(X):\|C_{i}\|_{\sigma}\leq
s_{i}\right\\},\epsilon_{i},\|\cdot\|_{F}\right),$ (44)

where $\mathbf{C}_{i}=(C_{1},...,C_{i})$. By Lemma 10 and Lemma 11, if $i\in
S_{\mathbf{A}}$, we have

$\ln\mathcal{N}\left(\left\\{C_{i}F_{\mathbf{C}_{i-1}}(X):\|C_{i}\|_{\sigma}\leq
s_{i}\right\\},\epsilon_{i},\|\cdot\|_{F}\right)\leq
d_{i}d_{i-1}\ln\bigg{(}1+\frac{2a_{i}\|F_{\mathbf{C}_{i-1}}(X)\|_{F}}{\epsilon_{i}}\bigg{)},$
(45)

and if $i\in S_{\mathbf{W}}$,

$\ln\mathcal{N}\left(\left\\{C_{i}F_{\mathbf{C}_{i-1}}(X):\|C_{i}\|_{\sigma}\leq
s_{i}\right\\},\epsilon_{i},\|\cdot\|_{F}\right)\leq
c_{i}r_{i}\ln\bigg{(}1+\frac{2a_{i}\sqrt{d_{i}/c_{i}}\|F_{\mathbf{C}_{i-1}}(X)\|_{F}}{\epsilon_{i}}\bigg{)}.$
(46)

Since $\|C_{j}\|_{\sigma}\leq s_{j}$, we have

$\displaystyle\|F_{\mathbf{C}_{i}}(X)\|_{F}$
$\displaystyle=\|\sigma_{i}(C_{i}F_{\mathbf{C}_{i-1}}(X))-\sigma_{i}(0)\|_{F}$
(47)
$\displaystyle\leq\rho_{i}\|C_{i}\|_{\sigma}\|F_{\mathbf{C}_{i-1}}(X)\|_{F}$
$\displaystyle\leq\rho_{i}s_{i}\|F_{\mathbf{C}_{i-1}}(X)\|_{F}$
$\displaystyle\leq\|X\|_{F}\prod_{j=1}^{i}\rho_{j}s_{j},$

where the last inequality is attained by induction. Substituting (45), (46)
and (47) into (44), we have

$\displaystyle\ln\mathcal{N}\left(\mathcal{H}_{X}^{\mathcal{C}},\epsilon,\|\cdot\|_{F}\right)$
$\displaystyle\leq\sum_{i\in S_{\mathbf{A}}}\sup_{\mathbf{C}_{i-1},\forall
j\leq i-1,\|C_{j}\|_{\sigma}\leq
s_{j}}d_{i}d_{i-1}\ln\bigg{(}1+\frac{2a_{i}\|F_{\mathbf{C}_{i-1}}(X)\|_{F}}{\epsilon_{i}}\bigg{)}$
(48) $\displaystyle\quad+\sum_{i\in
S_{\mathbf{W}}}\sup_{\mathbf{C}_{i-1},\forall j\leq i-1,\|C_{j}\|_{\sigma}\leq
s_{j}}c_{i}r_{i}\ln\bigg{(}1+\frac{2a_{i}\sqrt{d_{i}/c_{i}}\|F_{\mathbf{C}_{i-1}}(X)\|_{F}}{\epsilon_{i}}\bigg{)}$
$\displaystyle\leq\sum_{i\in
S_{\mathbf{A}}}d_{i}d_{i-1}\ln\bigg{(}1+\frac{2a_{i}\|X\|_{F}\prod_{j=1}^{i-1}\rho_{j}s_{j}}{\epsilon_{i}}\bigg{)}$
$\displaystyle\quad+\sum_{i\in
S_{\mathbf{W}}}c_{i}r_{i}\ln\bigg{(}1+\frac{2a_{i}\sqrt{d_{i}/c_{i}}\|X\|_{F}\prod_{j=1}^{i-1}\rho_{j}s_{j}}{\epsilon_{i}}\bigg{)}.$

By the definition of $\epsilon_{i}$, we further have

$\displaystyle\ln\mathcal{N}\left(\mathcal{H}_{X}^{\mathcal{C}},\epsilon,\|\cdot\|_{F}\right)$
(49) $\displaystyle\leq\sum_{i\in
S_{\mathbf{A}}}d_{i}d_{i-1}\ln\bigg{(}1+\frac{2a_{i}\|X\|_{F}\prod_{j=1}^{i-1}\rho_{j}s_{j}}{\frac{\alpha_{i}\epsilon}{\rho_{i}\prod_{l=i+1}^{L}\rho_{l}s_{l}}}\bigg{)}+\sum_{i\in
S_{\mathbf{W}}}c_{i}r_{i}\ln\bigg{(}1+\frac{2a_{i}\sqrt{d_{i}/c_{i}}\|X\|_{F}\prod_{j=1}^{i-1}\rho_{j}s_{j}}{\frac{\alpha_{i}\epsilon}{\rho_{i}\prod_{l=i+1}^{L}\rho_{l}s_{l}}}\bigg{)}$
$\displaystyle=\sum_{i\in
S_{\mathbf{A}}}d_{i}d_{i-1}\ln\bigg{(}1+\frac{2a_{i}\|X\|_{F}\prod_{j=1}^{L}\rho_{j}s_{j}}{s_{i}\alpha_{i}\epsilon}\bigg{)}+\sum_{i\in
S_{\mathbf{W}}}c_{i}r_{i}\ln\bigg{(}1+\frac{2a_{i}\sqrt{d_{i}/c_{i}}\|X\|_{F}\prod_{j=1}^{L}\rho_{j}s_{j}}{s_{i}\alpha_{i}\epsilon}\bigg{)}$
$\displaystyle\leq\sum_{i\in
S_{\mathbf{A}}}d_{i}d_{i-1}\bigg{(}\frac{2a_{i}\|X\|_{F}\prod_{j=1}^{L}\rho_{j}s_{j}}{s_{i}\alpha_{i}\epsilon}\bigg{)}^{\frac{1}{2}}+\sum_{i\in
S_{\mathbf{W}}}c_{i}r_{i}\bigg{(}\frac{2a_{i}\sqrt{d_{i}/c_{i}}\|X\|_{F}\prod_{j=1}^{L}\rho_{j}s_{j}}{s_{i}\alpha_{i}\epsilon}\bigg{)}^{\frac{1}{2}}$
$\displaystyle=\bigg{(}\frac{2\|X\|_{F}\prod_{i=1}^{L}\rho_{i}s_{i}}{\epsilon}\bigg{)}^{\frac{1}{2}}\left(\sum_{i\in
S_{\mathbf{A}}}d_{i}d_{i-1}\left(\frac{a_{i}}{s_{i}\alpha_{i}}\right)^{\frac{1}{2}}+\sum_{i\in
S_{\mathbf{W}}}c_{i}r_{i}\left(\frac{a_{i}\sqrt{d_{i}/c_{i}}}{s_{i}\alpha_{i}}\right)^{\frac{1}{2}}\right).$

where the last inequality is due to the fact that $\ln(1+x)\leq\sqrt{x}$ for
$\forall x\geq 0$. Define

$\Delta\triangleq\sum_{j\in
S_{\mathbf{A}}}\frac{d_{j}^{2}d_{j-1}^{2}a_{j}}{s_{j}}+\sum_{j\in
S_{\mathbf{W}}}\frac{c_{j}^{2}r_{j}^{2}a_{j}\sqrt{d_{j}/c_{j}}}{s_{j}},$ (50)

and let

$\alpha_{i}=\begin{cases}\frac{d_{i}^{2}d_{i-1}^{2}a_{i}}{s_{i}\Delta},&\forall
i\in S_{\mathbf{A}}\\\
\frac{c_{i}^{2}r_{i}^{2}a_{i}\sqrt{d_{i}/c_{i}}}{s_{i}\Delta},&\forall i\in
S_{\mathbf{W}}.\end{cases}$ (51)

It is easy to see that $\sum_{i=1}^{L}\alpha_{i}=1$ by extracting the common
factor $1/\Delta$ from all $\alpha_{i}$s and using the definition of $\Delta$.
Then we have

$\displaystyle\ln\mathcal{N}\left(\mathcal{H}_{X}^{\mathcal{C}},\epsilon,\|\cdot\|_{F}\right)$
$\displaystyle\leq\bigg{(}\frac{2\|X\|_{F}\prod_{i=1}^{L}\rho_{i}s_{i}}{\epsilon}\bigg{)}^{\frac{1}{2}}\left(\sum_{i\in
S_{\mathbf{A}}}\frac{d_{i}^{2}d_{i-1}^{2}a_{i}}{s_{i}}+\sum_{i\in
S_{\mathbf{W}}}\frac{c_{i}^{2}r_{i}^{2}a_{i}\sqrt{d_{i}/c_{i}}}{s_{i}}\right)^{\frac{1}{2}}L$
(52)
$\displaystyle=\left(\frac{\|X\|_{F}\mathscr{R}_{\mathbf{C}}}{\epsilon}\right)^{\frac{1}{2}}.$

By substituting all layers in CNNs to fully connected layers, i.e.,
$S_{\mathbf{W}}$ is empty, we have the following covering number bound for
FNNs.

###### Proposition 15

Denote the input data by $X\in\mathbb{R}^{d\times n}$ with bounded $F$-norm.
Let $(\sigma_{1},...,\sigma_{L})$ be fixed functions where $\sigma_{i}$ is
$\rho_{i}$-Lipschitz satisfying $\sigma_{i}(0)=0$. Let
$\mathbf{A}=(A_{1},...,A_{L})$ be fully connected weight matrices of all
layers, where $A_{i}\in\mathbb{R}^{d_{i}\times d_{i-1}}$ and $d_{0}=d$. Denote
by $\mathcal{H}_{X}^{\mathcal{A}}$ the family of result matrices generated by
evaluating $X$ for all FNNs $F_{\mathbf{A}}$ defined in (9) with bounded
weights, i.e.,

$\displaystyle\mathcal{H}_{X}^{\mathcal{A}}\triangleq\big{\\{}F_{\mathbf{A}}(X):\|A_{i}\|_{F}\leq
a_{i},\|A\|_{\sigma}\leq s_{i},\forall i=1,...,L\big{\\}}.$ (53)

Letting $\mathscr{R}_{\mathbf{A}}$ be defined in (23), we have the following
covering number bound

$\displaystyle\ln\mathcal{N}\left(\mathcal{H}_{X}^{\mathcal{A}},\epsilon,\|\cdot\|_{F}\right)\leq\left(\frac{\|X\|_{F}\mathscr{R}_{\mathbf{A}}}{\epsilon}\right)^{\frac{1}{2}}.$
(54)

Similarly, by substituting all layers in CNNs to convolutional layers, i.e.,
$S_{\mathbf{A}}$ is empty, we have the following covering number bound for
FCNNs.

###### Proposition 16

Denote the input data by $X\in\mathbb{R}^{d\times n}$ with bounded $F$-norm.
Let $(\sigma_{1},...,\sigma_{L})$ be fixed functions where $\sigma_{i}$ is
$\rho_{i}$-Lipschitz satisfying $\sigma_{i}(0)=0$. Let
$\mathbf{W}=(w_{1},...,w_{L})$ and $(\gamma_{1}(W_{1}),...,\gamma_{L}(W_{L}))$
be convolutional weights and their corresponding fully connected weight
matrices, where $W_{i}\in\mathbb{R}^{c_{i}\times r_{i}}$ containing $c_{i}$
convolutional filters of size $r_{i}$. Let the output of each convolutional
layer be $d_{i}$ dimension, then $\gamma_{i}(W_{i})\in\mathbb{R}^{d_{i}\times
d_{i-1}}$ and $d_{0}=d$. Denote by $\mathcal{H}_{X}^{\mathcal{W}}$ the family
of result matrices generated by evaluating $X$ for all FCNNs $F_{\mathbf{W}}$
defined in (13) with bounded weights, i.e.,

$\displaystyle\mathcal{H}_{X}^{\mathcal{W}}\triangleq\big{\\{}F_{\mathbf{W}}(X):\|W_{i}\|_{F}\leq
a_{i},\|\gamma_{i}(W_{i})\|_{\sigma}\leq s_{i},\forall i=1,...,L\big{\\}}.$
(55)

Letting $\mathscr{R}_{\mathbf{W}}$ be defined in (24), we have the following
covering number bound

$\displaystyle\ln\mathcal{N}\left(\mathcal{H}_{X}^{\mathcal{W}},\epsilon,\|\cdot\|_{F}\right)\leq\left(\frac{\|X\|_{F}\mathscr{R}_{\mathbf{W}}}{\epsilon}\right)^{\frac{1}{2}}.$
(56)

###  4.3 Generalization Bounds for Neural Networks

By far, we have obtained the covering number bounds for multilayer neural
networks. The next step is to relate the covering number to Rademacher
complexity, and then we can obtain the generalization bound by Theorem 2. We
take advantage of a standard tool in statistical learning theory named
Dudley’s entropy integral.

###### Lemma 17

(Dudley’s entropy integral) Let $\mathcal{F}$ be a real-valued function class
taking values in $[0,1]$ and we assume that $\mathbf{0}\in\mathcal{F}$. Let
$X=(x_{1},...,x_{n})^{\top}$ be the given input containing $n$ examples and
$\mathcal{F}_{|X}=\left\\{\left(f(x_{1}),...,f(x_{n})\right)\in[0,1]^{n}:f\in\mathcal{F}\right\\}$,
then

$\mathfrak{R}_{X}(\mathcal{F})\leq\inf_{\alpha>0}\left(\frac{4\alpha}{\sqrt{n}}+\frac{12}{n}\int_{\alpha}^{\sqrt{n}}\sqrt{\ln\mathcal{N}(\mathcal{F}_{|X},\epsilon,\|\cdot\|_{2})}\,d\epsilon\right).$
(57)

###### Lemma 18

Given a training sample $S=((x_{1},y_{1}),...,(x_{n},y_{n}))$ of $n$ examples,
where $x_{i}\in\mathbb{R}^{d}$ and $y_{i}$ taking integer values from $[1,k]$.
Let $X=(x_{1},...,x_{n})^{\top}\in\mathbb{R}^{d\times n}$ be the input data.
Consider the hypothesis set $\mathcal{H}$ of neural networks mapping values
from $\mathbb{R}^{d}$ to $\mathbb{R}^{k}$, let $\ell_{\eta}$ be the ramp loss
defined in (5), and define the $\ell_{\eta}$ loss function class with respect
to $\mathcal{H}$ as

$\mathcal{H}_{\eta}\triangleq\left\\{(x,y)\to\ell_{\eta}\left(h(x),y\right):h\in\mathcal{H}\right\\}.$
(58)

Then empirical Rademacher complexity of $\mathcal{H}_{\eta}$ can be bounded by

$\mathfrak{R}_{S}(\mathcal{H}_{\eta})\leq
16n^{-5/8}\left(\frac{2\|X\|_{F}\mathscr{R}}{\eta}\right)^{\frac{1}{4}},$ (59)

where $\mathscr{R}$ denotes the corresponding sensitive complexity defined in
(22), (23) and (24) for CNNs, FNNs and FCNNs, respectively.

Proof  Since $\ell_{\eta}$ is $\frac{2}{\eta}$-Lipschitz, we have

$\ln\mathcal{N}\left(\mathcal{H}_{\eta|S},\epsilon,\|\cdot\|_{F}\right)\leq\ln\mathcal{N}\left(\mathcal{H}_{|X},\frac{\eta\epsilon}{2},\|\cdot\|_{F}\right)\leq\left(\frac{2\|X\|_{F}\mathscr{R}}{\eta\epsilon}\right)^{\frac{1}{2}},$
(60)

where the last inequality follows from Lemma 14, Proposition 15 and
Proposition 16. Moreover, because $\ell_{\eta}$ takes value from $[0,1]$, we
can apply Dudley’s entropy integral, which yields

$\displaystyle\mathfrak{R}_{S}(\mathcal{H}_{\eta})$
$\displaystyle\leq\inf_{\alpha>0}\left(\frac{4\alpha}{\sqrt{n}}+\frac{12}{n}\int_{\alpha}^{\sqrt{n}}\sqrt{\ln\mathcal{N}(\mathcal{H}_{\eta|S},\epsilon,\|\cdot\|_{F})}\,\text{d}\epsilon\right)$
(61)
$\displaystyle\leq\inf_{\alpha>0}\left(\frac{4\alpha}{\sqrt{n}}+\frac{12}{n}\int_{\alpha}^{\sqrt{n}}\left(\frac{2\|X\|_{F}\mathscr{R}}{\eta\,\epsilon}\right)^{\frac{1}{4}}\,\text{d}\epsilon\right)$
$\displaystyle=\inf_{\alpha>0}\left(\frac{4\alpha}{\sqrt{n}}+\frac{16}{n}\left(\frac{2\|X\|_{F}\mathscr{R}}{\eta}\right)^{\frac{1}{4}}\left({n}^{3/8}-\alpha^{3/4}\right)\right).$

When the first derivative equals zero, the right hand side function achieves
the minimum at $\alpha=\frac{81\|X\|_{F}\mathscr{R}}{128\eta n^{2}}$. Then, we
have

$\displaystyle\mathfrak{R}_{S}(\mathcal{H}_{\eta})$
$\displaystyle\leq\left(\frac{4}{\sqrt{n}}\frac{81\|X\|_{F}\mathscr{R}}{128\eta
n^{2}}+\frac{16}{n}\left(\frac{2\|X\|_{F}\mathscr{R}}{\eta}\right)^{\frac{1}{4}}\left({n}^{3/8}-\left(\frac{81\|X\|_{F}\mathscr{R}}{128\eta
n^{2}}\right)^{\frac{3}{4}}\right)\right)$ (62)
$\displaystyle=16n^{-5/8}\left(\frac{2\|X\|_{F}\mathscr{R}}{\eta}\right)^{\frac{1}{4}}-\frac{351}{32}\frac{\|X\|_{F}\mathscr{R}}{\eta
n^{2}\sqrt{n}}$ $\displaystyle\leq
16n^{-5/8}\left(\frac{2\|X\|_{F}\mathscr{R}}{\eta}\right)^{\frac{1}{4}}.$

Combining the above with Theorem 2 yields the main Theorem 5. And it implies
that for any neural network $h\in\mathcal{H}$,

$\displaystyle\mathcal{R}_{\mathcal{D}}(h)$
$\displaystyle\leq\widehat{\mathcal{R}}_{S,\ell_{\eta}}(h)+2\mathfrak{R}_{S}(\mathcal{H}_{\eta})+3\sqrt{\frac{\ln(1/\delta)}{2n}}$
(63)
$\displaystyle\leq\widehat{\mathcal{R}}_{S,\ell_{\eta}}(h)+32\left(\frac{2\|X\|_{F}\mathscr{R}}{\eta}\right)^{\frac{1}{4}}n^{-5/8}+3\sqrt{\frac{\ln(1/\delta)}{2n}}.$

###### Remark 19

Here we emphasize the dependence of our bound on two parameters, including the
number of samples $n$ and the depth of networks $L$. For fully convolutional
neural networks with ReLU activation, our bound is of
$\mathcal{O}(L^{3/4}/\sqrt{n})$, because $\|X\|_{F}$ is of $\sqrt{n}$ and
$\mathscr{R}$ is of $L^{3}$. In this way, our bound is better than
$\mathcal{O}(L^{3/2}/\sqrt{n})$ in (Bartlett et al., 2017; Neyshabur et al.,
2017a), but it seems to be worse than $\mathcal{O}(L^{1/2}/\sqrt{n})$ in
(Golowich et al., 2018; Li et al., 2018). However, when combined with other
parameters, our bound is advantageous under mild conditions, see Section 6.

##  5 Extensions to Different Convolution Operations

The proposed generalization bound depends on the $F$-norm of convolutional
weight $W$ as well as the spectral norm of the corresponding fully connected
matrix $\gamma(W)$. Although introducing the notion of $\gamma(W)$ offers much
convenience when deriving covering number bounds for CNNs and making
comparisons with existing generalization bounds as shown in Section 4.2 and
Section 6, it is cumbersome to transform $W$ to $\gamma(W)$. Moreover,
$\gamma(W)$ will change according to the input dimension even if $W$ remains
the same. This motivates us to relate the spectral norm of $\gamma(W)$ to the
norm of $W$ so as to remove the dependence on $\gamma(W)$ from the proposed
generalization bounds for CNNs. In this section, we will consider different
types of convolution operations including standard convolution, depthwise
convolution, and pointwise convolution. Note that depthwise and pointwise
convolutions are often chained together to form depthwise separable
convolutions, which are commonly used in CNN architectures like (Howard et
al., 2017; Sandler et al., 2018; Chollet, 2017).

###  5.1 Standard Convolution

Previously, Li et al. (2018) demonstrated that the spectral norm of
$\gamma(W)$ equals $r/l$ for orthogonal filters, where $r$ is the length of
each filter and $l$ represents the stride size. We discuss the general case of
standard convolution without the orthogonality condition.

###### Proposition 20

Let $W=(w^{1},...,w^{c})\in\mathbb{R}^{c\times r}$ be a convolutional weight
matrix containing $c$ convolutional filters. Assume that each filter $w^{i}$
performs $m$ operations on input data $Z\in\mathbb{R}^{d\times n}$. For the
corresponding fully connected matrix $\gamma(W)\in\mathbb{R}^{cm\times d}$, we
have

$\|\gamma(W)\|_{\sigma}\leq\sqrt{m}\|W\|_{F}.$ (64)

Proof  We have

$\displaystyle\|\gamma(W)\|_{\sigma}$
$\displaystyle\leq\|\gamma(W)\|_{F}=\left(\sum_{i=1}^{cm}\sum_{j=1}^{d}\gamma(W)_{ij}^{2}\right)^{\frac{1}{2}}$
(65)
$\displaystyle=\left(m\sum_{i=1}^{c}\sum_{j=1}^{r}W_{ij}^{2}\right)^{\frac{1}{2}}=\sqrt{m}\|W\|_{F}.$

This completes the proof.

###### Remark 21

Substituting $s_{i}=\sqrt{m_{i}}a_{i}=\sqrt{d_{i}/c_{i}}a_{i}$ into (24)
yields

$\displaystyle\mathscr{R}_{\mathbf{W}}$
$\displaystyle=\left(2\prod_{i=1}^{L}\rho_{i}\sqrt{d_{i}/c_{i}}a_{i}\right)\left(\sum_{i=1}^{L}c_{i}^{2}r_{i}^{2}\right)L^{2}.$
(66)

Thus we can remove the dependence on $\gamma(W)$ from the generalization bound
of FCNNs. The complexity $\mathscr{R}_{\mathbf{C}}$ of CNNs can also be
updated analogously. However, we have made an aggressive step in the first
inequality of (65) that simply bounds the spectral norm by $F$-norm, which is
generally not tight and will result in loose bounds.

In the following, we will derive tighter relations between
$\|\gamma(W)\|_{\sigma}$ and the norm of $W$ for special cases of depthwise
and pointwise convolutions.

###  5.2 Depthwise Convolution

Depthwise convolution is widely used because of its efficiency in the sense
that each convolutional filter operates independently on different input
channels rather than across channels. In previous discussions, we do not
consider the specific shape of input features and convolutional filters by
using them as one-dimension vectors of size $d$ and $r$. We refine our
notations by assuming that $d$ and $r$ both have two dimensions, i.e., the
spatial dimension and the channel dimension. For the $i_{th}$ layer, let
$d_{i}=m_{i}\times c_{i}$ and $r_{i}=k_{i}\times c_{i-1}$, where $m_{i}$
denotes the spatial size of the output, $c_{i}$ denotes the number of channels
for the output, and $k_{i}$ denotes the spatial size of each convolutional
filter. Hence, we have the output $Z_{i}\in\mathbb{R}^{m_{i}\times c_{i}\times
n}$ and the convolutional weight $W_{i}\in\mathbb{R}^{c_{i}\times k_{i}\times
c_{i-1}}$.

We consider one depthwise convolutional layer with input data
$Z\in\mathbb{R}^{m\times c\times n}$. Let
$W=(w^{1},...,w^{c})\in\mathbb{R}^{c\times k}$ be the depthwise convolutional
weight matrix containing $c$ depthwise convolutional filters, and each filter
$w^{i}$ only has a spatial dimension $k$. Here we use the fact that in
depthwise convolution, the number of filters is always equal to the number of
input channels and each filter operates on one channel, i.e., no channel
dimension is needed for each filter. Assuming that each $w^{i}$ performs
$m^{\prime}$ operations on one channel of $Z$, then the output is
$Z^{\prime}\in\mathbb{R}^{m^{\prime}\times c\times n}$. The corresponding
fully connected weight matrix $\gamma(W)\in\mathbb{R}^{m^{\prime}c\times mc}$
can be written as

$\gamma(W)=\begin{pmatrix}\Omega(w^{1})&0&0&\cdots&0\\\
0&\Omega(w^{2})&0&\cdots&0\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&\Omega(w^{c})\end{pmatrix}\text{, where
}\Omega(w^{i})\triangleq\begin{pmatrix}w^{i}_{S_{1}}\\\ w^{i}_{S_{2}}\\\
\vdots\\\ w^{i}_{S_{m^{\prime}}}\end{pmatrix}\in\mathbb{R}^{m^{\prime}\times
m},$ (67)

and the index set $S_{i}$s are defined in Section 3.3.1.

We aim to calculate the spectral norm of $\gamma(W)$, which is equal to the
square root of the largest eigenvalue of square matrix
$\gamma(W)\gamma(W)^{\top}$. Given (67), we have

$\gamma(W)\gamma(W)^{\top}=\begin{pmatrix}\Omega(w^{1})\Omega(w^{1})^{\top}&0&0&\cdots&0\\\
0&\Omega(w^{2})\Omega(w^{2})^{\top}&0&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&\Omega(w^{c})\Omega(w^{c})^{\top}\end{pmatrix},$ (68)

where

$\Omega(w^{i})\Omega(w^{i})^{\top}=\begin{pmatrix}w^{i}_{S_{1}}w^{i\top}_{S_{1}}&w^{i}_{S_{1}}w^{i\top}_{S_{2}}&\cdots&w^{i}_{S_{1}}w^{i\top}_{S_{m^{\prime}}}\\\
w^{i}_{S_{2}}w^{i\top}_{S_{1}}&w^{i}_{S_{2}}w^{i\top}_{S_{2}}&\cdots&w^{i}_{S_{2}}w^{i\top}_{S_{m^{\prime}}}\\\
\vdots&\vdots&\vdots&\vdots\\\
w^{i}_{S_{m^{\prime}}}w^{i\top}_{S_{1}}&w^{i}_{S_{m^{\prime}}}w^{i\top}_{S_{2}}&\cdots&w^{i}_{S_{m^{\prime}}}w^{i\top}_{S_{m^{\prime}}}\end{pmatrix}.$
(69)

Then it only remains to find the largest eigenvalue of
$\Omega(w^{i})\Omega(w^{i})^{\top}$. Without loss of generality, we can assume
that indices in $S_{j}$ are in ascending order. Let $l$ be the stride size and
$k$ be the filter size, then we have

$S_{j}=\left(l(j-1)+1,l(j-1)+2,\cdots,l(j-1)+k\right),\forall j\in
1,...,m^{\prime}.$ (70)

With this notation, we further divide depthwise convolution into two scenarios
when $S_{1},...,S_{m^{\prime}}$ are overlapping or non-overlapping, or
equivalently, when the stride size is smaller than or equal to the filter
size. Both cases have been shown to play important roles in modern CNNs. We
start with the easier non-overlapping scenario.

####  5.2.1 Non-overlapping Convolutional Filters

Non-overlapping convolution has attracted increasing attention recently. From
theoretical perspective, non-overlapping filters lead to neat formulations and
deliver concrete analysis. Brutzkus and Globerson (2017) showed that a non-
overlapping convolutional neural network with Gaussian inputs can converge to
global optimum in polynomial time. Although limited, non-overlapping
convolutions do play an important role in recent works. The following lemma
demonstrates the relation between $\|\gamma(W)\|_{\sigma}$ and $\|W\|_{F}$ for
non-overlapping convolutions.

###### Proposition 22

Let $W=(w^{1},...,w^{c})\in\mathbb{R}^{c\times k}$ be a depthwise
convolutional weight matrix, and let
$\gamma(W)\in\mathbb{R}^{m^{\prime}c\times mc}$,
$\Omega(w^{i})\in\mathbb{R}^{m^{\prime}\times m}$, and
$S_{1},...,S_{m^{\prime}}$ be defined in (67). If $S_{1},...,S_{m^{\prime}}$
are non-overlapping, then we have

$\|\gamma(W)\|_{\sigma}\leq\|W\|_{F}.$ (71)

Proof  When $S_{1},...,S_{m^{\prime}}$ are non-overlapping, we have

$w^{i}_{S_{p}}w^{i\top}_{S_{q}}=\begin{cases}\left\|w^{i}\right\|_{2}^{2},&\text{if
}\,p=q\\\ 0,&\text{otherwise.}\end{cases}$ (72)

By (69), we have

$\Omega(w^{i})\Omega(w^{i})^{\top}=\text{diag}\left(\left\|w^{i}_{S_{1}}\right\|_{2}^{2},...,\big{\|}w^{i}_{S_{m^{\prime}}}\big{\|}_{2}^{2}\right)=\text{diag}\left(\big{\|}w^{i}\big{\|}_{2}^{2},...,\left\|w^{i}\right\|_{2}^{2}\right)=\|w^{i}\|_{2}^{2}\;I_{m^{\prime}},$
(73)

where $I_{m^{\prime}}$ is the identity matrix with size $m^{\prime}$.
Combining with (68), we have

$\displaystyle\|\gamma(W)\|_{\sigma}$
$\displaystyle=\sqrt{\lambda_{\max}\left(\gamma(W)\gamma(W)^{\top}\right)}=\sqrt{\max_{i=1,...,c}\lambda_{\max}\left(\Omega(w^{i})\Omega(w^{i})^{\top}\right)}$
(74)
$\displaystyle=\sqrt{\max_{i=1,...,c}\left\|w^{i}\right\|_{2}^{2}}\leq\sqrt{\sum_{i=1}^{c}\left\|w^{i}\right\|_{2}^{2}}=\|W\|_{F}.$

This completes the proof.

####  5.2.2 Overlapping Convolutional Filters

Overlapping convolution operation significantly increases the expressive power
of neural networks compared with non-overlapping operation (Sharir and
Shashua, 2017). In this scenario, we show that
$\Omega(w^{i})\Omega(w^{i})^{\top}$ is a symmetric banded Toeplitz matrix
(Gray et al., 2006). We first introduce its definition.

######  Definition 23 (Banded Toeplitz Matrix)

Given an infinite sequence $\\{t_{q}\\}$ and a positive number $b$ for which
$t_{q}=0$ if $|q|>b$, the banded Toeplitz matrix with respect to this sequence
is defined by

$T_{n}\triangleq\setcounter{MaxMatrixCols}{11}\begin{pmatrix}t_{0}&t_{-1}&\cdots&t_{-b}&&&&&&&\\\
t_{1}&t_{0}&&&&&&&&&\\\ \vdots&&&&&&&&0&&\\\ &&\ddots&&&&\ddots&&&&\\\
t_{b}&&&&&&&&&&\\\ &\ddots&&&&&&&&&\\\
&&t_{b}&\cdots&t_{1}&t_{0}&t_{-1}&\cdots&t_{-b}&&\\\ &&&&&&&&&\ddots&\\\
&&&&\ddots&&&\ddots&&&t_{-b}\\\ &&0&&&&&&&&\vdots\\\ &&&&&&&&&t_{0}&t_{-1}\\\
&&&&&&&t_{b}&\cdots&t_{1}&t_{0}\end{pmatrix}\in\mathbb{R}^{n\times n}.$ (75)

If we further have $t_{q}=t_{-q}$ for all $|q|\leq b$, then $T_{n}$ is a
symmetric banded Toeplitz matrix.

For such a matrix, we have the following lemma for its eigenvalues.

###### Lemma 24

(Gray et al. (2006), Lemma 4.1) Given a real symmetric banded Toeplitz matrix
$T_{n}$ generated by $\\{t_{q}\\}$ with band $b$, let
$\lambda_{k},k\in\\{1,...,n\\}$ be its eigenvalues. Then if
$\sum_{i=1}^{b}|t_{i}|<\infty$, for any $k$, we have

$\lambda_{k}\leq\sum_{i=-b}^{b}\left|t_{|i|}\right|.$ (76)

Based on this, we obtain the following bound for $\|\gamma(W)\|_{\sigma}$ in
terms of $\|W\|_{\infty}$.

###### Proposition 25

Let $W=(w^{1},...,w^{c})\in\mathbb{R}^{c\times k}$ be a depthwise
convolutional weight matrix, and let
$\gamma(W)\in\mathbb{R}^{m^{\prime}c\times mc}$,
$\Omega(w^{i})\in\mathbb{R}^{m^{\prime}\times m}$, and
$S_{1},...,S_{m^{\prime}}$ be defined as (67). If $S_{1},...,S_{m^{\prime}}$
are overlapping, then we have

$\|\gamma(W)\|_{\sigma}\leq\|W\|_{\infty}.$ (77)

Proof  First, we show that $\Omega(w^{i})\Omega(w^{i})^{\top}$ is a symmetric
banded Toeplitz matrix for all $i=1,...,c$, and then we can apply Lemma 24.
Denote the stride size by $l$. In the overlapping scenario, the stride size
$l$ is smaller than the filter size $k$. Using the definition of $S_{j}$ in
(70), if $p<q$, we have

$\left[\Omega(w^{i})\Omega(w^{i})^{\top}\right]_{p,q}=w^{\,i}_{S_{p}}w_{S_{q}}^{\,i\top}=\sum_{j=1}^{k-(q-p)l}w^{\,i}_{(q-p)l+j}w^{\,i}_{j}.$
(78)

By defining

$t^{\,i}_{s}\triangleq\sum_{j=1}^{k-s\,l}w^{\,i}_{s\,l+j}\,w^{\,i}_{j},$ (79)

we have $\left[\Omega(w^{i})\Omega(w^{i})^{\top}\right]_{p,q}=t^{\,i}_{q-p}$.
Since $\Omega(w^{i})\Omega(w^{i})^{\top}$ is symmetric, we have that

$\left[\Omega(w^{i})\Omega(w^{i})^{\top}\right]_{p,q}=t^{\,i}_{|p-q|}.$ (80)

By definition, it is a symmetric banded Toeplitz matrix with band $b=\lceil
k/l\rceil$. Applying Lemma 24, we have

$\lambda_{\max}\left(\Omega(w^{i})\Omega(w^{i})^{\top}\right)\leq\sum_{q=-b}^{b}\sum_{j=1}^{k-|q|l}\left|w^{i}_{|q|l+j}w^{i}_{j}\right|\overset{(a)}{\leq}\sum_{p=1}^{k}\sum_{q=1}^{k}\left|w^{i}_{p}w^{i}_{q}\right|=\left\|w^{i}\right\|_{1}^{2},$
(81)

where equality of $(a)$ holds if the stride size $l$ is equal to one. Hence by
(68), we have

$\displaystyle\|\gamma(W)\|_{\sigma}$
$\displaystyle=\sqrt{\lambda_{\max}\left(\gamma(W)\gamma(W)^{\top}\right)}=\sqrt{\max_{i=1,...,c}\lambda_{\max}\left(\Omega(w^{i})\Omega(w^{i})^{\top}\right)}$
(82)
$\displaystyle\leq\sqrt{\max_{i=1,...,c}\left\|w^{i}\right\|_{1}^{2}}=\max_{i=1,...,c}\left\|w^{i}\right\|_{1}=\left\|W\right\|_{\infty}.$

This concludes the proof.

###  5.3 Pointwise Convolution

Different from depthwise convolutions, pointwise convolutions have channel
dimensions, whereas their spatial dimensions are always equal to one. They are
often used to combine the outputs of depthwise convolutions so as to form
depthwise separable convolutions. In addition, they can be applied
individually as bottleneck layers by setting the number of output channels to
be smaller than the number of input channels, or as logit layers by setting
the number of output channels to be equal to the number of output classes.

Given input data $Z\in\mathbb{R}^{m\times c\times n}$, let
$W=(w^{1},...,w^{c^{\prime}})\in\mathbb{R}^{c^{\prime}\times c}$ be a
pointwise convolutional weight matrix containing $c^{\prime}$ convolutional
filters and the output data $Z^{\prime}\in\mathbb{R}^{m\times c^{\prime}\times
n}$. Then the corresponding fully connected matrix $\gamma(W)$ can be
formulated as

$\gamma(W)=\begin{pmatrix}\Phi(w^{1})\\\ \Phi(w^{2})\\\ \vdots\\\
\Phi(w^{c^{\prime}})\end{pmatrix}\in\mathbb{R}^{mc^{\prime}\times mc}\text{,
where }\Phi(w^{i})=\begin{pmatrix}w^{i}&\cdots&\cdots&\cdots\\\
\cdots&w^{i}&\cdots&\cdots\\\ \vdots&\vdots&\vdots&\vdots\\\
\cdots&\cdots&\cdots&w^{i}\end{pmatrix}\in\mathbb{R}^{m\times mc}.$ (83)

Similarly, our goal is to compute the square root of the largest eigenvalue of
$\gamma(W)\gamma(W)^{\top}$. Given (83), we have

$\Phi(w^{i})\Phi(w^{j})^{\top}=w^{i}w^{j\top}I_{m}.$ (84)

Hence, we have

$\displaystyle\gamma(W)\gamma(W)^{\top}$
$\displaystyle=\begin{pmatrix}\Phi(w^{1})\Phi(w^{1})^{\top}&\Phi(w^{1})\Phi(w^{2})^{\top}&\cdots&\Phi(w^{1})\Phi(w^{c^{\prime}})^{\top}\\\
\Phi(w^{2})\Phi(w^{1})^{\top}&\Phi(w^{2})\Phi(w^{2})^{\top}&\cdots&\Phi(w^{2})\Phi(w^{c^{\prime}})^{\top}\\\
\vdots&\vdots&\vdots&\vdots\\\
\Phi(w^{c^{\prime}})\Phi(w^{1})^{\top}&\Phi(w^{c^{\prime}})\Phi(w^{2})^{\top}&\cdots&\Phi(w^{c^{\prime}})\Phi(w^{c^{\prime}})^{\top}\end{pmatrix}$
(85)
$\displaystyle=\begin{pmatrix}w^{1}w^{1\top}I_{m}&w^{1}w^{2\top}I_{m}&\cdots&w^{1}w^{c^{\prime}\top}I_{m}\\\
w^{2}w^{1\top}I_{m}&w^{2}w^{2\top}I_{m}&\cdots&w^{2}w^{c^{\prime}\top}I_{m}\\\
\vdots&\vdots&\vdots&\vdots\\\
w^{c^{\prime}}w^{1\top}I_{m}&w^{c^{\prime}}w^{2\top}I_{m}&\cdots&w^{c^{\prime}}w^{c^{\prime}\top}I_{m}\end{pmatrix}$
$\displaystyle\triangleq\Theta(WW^{\top},I_{m}),$

where we define a new matrix operator $\Theta(\cdot,I_{m})$ in the last step.
The following lemma presents a nice property for this operator.

###### Lemma 26

Given any positive semidefinite matrix $V\in\mathbb{R}^{n\times n}$, let
$\lambda=\text{diag}(\lambda_{1},...,\lambda_{n})$ denote its eigenvalues. For
any $m>0$, $\Theta(V,I_{m})$ is similar to $\Theta(\lambda,I_{m})$.

Proof  Since $V$ is positive semidefinite, there exists matrix
$P\in\mathbb{R}^{n\times n}$ such that $V$ can be factorized as $P\lambda
P^{-1}$, hence $\Theta(V,I_{m})=\Theta(P\lambda P^{-1},I_{m})$. We first show
that $\Theta$ has distributive property of multiplication, i.e,
$\Theta(AB,I_{m})=\Theta(A,I_{m})\Theta(B,I_{m})$ for any
$A,B\in\mathbb{R}^{n\times n}$. Indeed, we have

$\displaystyle\Theta(AB,I_{m})$
$\displaystyle=\begin{pmatrix}(AB)_{1,1}I_{m}&(AB)_{1,2}I_{m}&\cdots&(AB)_{1,n}I_{m}\\\
(AB)_{2,1}I_{m}&(AB)_{2,2}I_{m}&\cdots&(AB)_{2,n}I_{m}\\\
\vdots&\vdots&\vdots&\vdots\\\
(AB)_{n,1}I_{m}&(AB)_{n,2}I_{m}&\cdots&(AB)_{n,n}I_{m}\\\ \end{pmatrix}$ (86)
$\displaystyle=\begin{pmatrix}A_{1,1}I_{m}&A_{1,2}I_{m}&\cdots&A_{1,n}I_{m}\\\
A_{2,1}I_{m}&A_{2,2}I_{m}&\cdots&A_{2,n}I_{m}\\\
\vdots&\vdots&\vdots&\vdots\\\
A_{n,1}I_{m}&A_{n,2}I_{m}&\cdots&A_{n,n}I_{m}\\\
\end{pmatrix}\times\begin{pmatrix}B_{1,1}I_{m}&B_{1,2}I_{m}&\cdots&B_{1,n}I_{m}\\\
B_{2,1}I_{m}&B_{2,2}I_{m}&\cdots&B_{2,n}I_{m}\\\
\vdots&\vdots&\vdots&\vdots\\\
B_{n,1}I_{m}&B_{n,2}I_{m}&\cdots&B_{n,n}I_{m}\\\ \end{pmatrix}$
$\displaystyle=\Theta(A,I_{m})\Theta(B,I_{m}).$

Given this, we obtain

$\Theta(V,I_{m})=\Theta(P\lambda
P^{-1},I_{m})=\Theta(P,I_{m})\Theta(\lambda,I_{m})\Theta(P^{-1},I_{m}).$ (87)

We also have

$\Theta(P,I_{m})\Theta(P^{-1},I_{m})=\Theta(PP^{-1},I_{m})=I_{mn}.$ (88)

Combining (87) and (88) concludes the proof.
Based on the above lemma, it is straightforward to get
$\|\gamma(W)\|_{\sigma}$ as shown in the following.

###### Proposition 27

Let $W=(w^{1},...,w^{c^{\prime}})\in\mathbb{R}^{c^{\prime}\times c}$ be a
pointwise convolutional weight matrix, then the corresponding fully connected
matrix $\gamma(W)$ generated by $W$ satisfies

$\|\gamma(W)\|_{\sigma}=\|W\|_{\sigma}.$ (89)

Proof  Let $\lambda=\text{diag}(\lambda_{1},...,\lambda_{c^{\prime}})$, where
$\lambda_{i}$s are the eigenvalues of $WW^{\top}$. Then by Lemma 26 and
equation (85), we have

$\displaystyle\|\gamma(W)\|_{\sigma}$
$\displaystyle=\sqrt{\lambda_{\max}\left(\gamma(W)\gamma(W)^{\top}\right)}=\sqrt{\lambda_{\max}\left(\Theta(WW^{\top},I_{m})\right)}$
(90)
$\displaystyle=\sqrt{\lambda_{\max}\left(\Theta(\lambda,I_{m})\right)}=\sqrt{\max_{i=1,...,c}\lambda_{i}}=\sqrt{\lambda_{\max}\left(WW^{\top}\right)}$
$\displaystyle=\|W\|_{\sigma}.$

This completes the proof.

##  6 Comparison with Existing Generalization Bounds

In this section, we compare our proposed generalization bounds with existing
bounds, e.g., (Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et
al., 2017a; Golowich et al., 2018; Li et al., 2018) both theoretically and
empirically. For theoretical comparisons, we discuss generalization bounds for
FNNs and FCNNs. For empirical comparisons, we conduct experiments for FCNNs
based on MobileNet v1 and MobileNet v2. Note that previous bounds are mainly
derived for FNNs without taking into account convolution structures. Thus, for
those works which do not explicitly present generalization bounds for FCNNs,
we use the transformed fully connected weight matrices generated by
convolution weights in place of the fully connected weight matrix in their
bounds for FNNs when comparing.

###  6.1 Theoretical Comparisons

Existing bounds depend on different norms of the fully connected matrices of
layers or different norms of the convolutional weights. For instance, the
generalization bound of FNNs proposed by (Bartlett et al., 2017) depends on
the $2,1$-norm and the spectral norm of the fully connected matrix, whereas
our bounds depend on its $F$-norm. Besides, with $W$ being the convolutional
weight, previous bounds of FCNNs are based on different norms of $\gamma(W)$,
whereas ours depend on the $F$-norm of $W$. To make them comparable, we first
derive the relation between the relation between $\|A\|_{2,1}$ and $\|A\|_{F}$
as well as $\|\gamma(W)\|_{2,1}$ and $\|W\|_{F}$.

###### Proposition 28

Given a fully connected weight matrix $A\in\mathbb{R}^{d_{output}\times
d_{input}}$ satisfying $\|A\|_{F}\leq a$, we have

$\|A\|_{2,1}\leq a\sqrt{d_{output}}.$ (91)

Proof  With Jensen’s inequality, we have

$\left(\frac{1}{d_{output}}\sum_{i=1}^{d_{output}}\left(\sum_{j=1}^{d_{input}}A_{ij}^{2}\right)^{1/2}\right)^{2}\leq\frac{1}{d_{output}}\sum_{i=1}^{d_{output}}\left(\sum_{j=1}^{d_{input}}A_{ij}^{2}\right).$
(92)

Hence,

$\|A\|_{2,1}=\sum_{i=1}^{d_{output}}\left(\sum_{j=1}^{d_{input}}A_{ij}^{2}\right)^{1/2}\leq\sqrt{d_{output}}\|A\|_{F}\leq
a\sqrt{d_{output}}.$ (93)

###### Proposition 29

Given a convolutional weight matrix $W=(w^{1},...,w^{c})\in\mathbb{R}^{c\times
r}$ satisfying $\|W\|_{F}\leq a$. Assuming that each convolutional filter
$w^{i}\in W$ generates $m$ outputs, then its transformed fully connected
weight matrix $\gamma(W)\in\mathbb{R}^{d_{output}\times d_{input}}$ where
$d_{output}=cm$ satisfying

$\|\gamma(W)\|_{2,1}\leq am\sqrt{c}.$ (94)

Proof

$\|\gamma(W)\|_{2,1}=\sum_{i=1}^{cm}\left(\sum_{j=1}^{d_{input}}\gamma(W)_{ij}^{2}\right)^{1/2}=m\sum_{i=1}^{c}\left(\sum_{j=1}^{r}W_{ij}^{2}\right)^{1/2}.$
(95)

With Jensen’s inequality, we have

$\left(\frac{1}{c}\sum_{i=1}^{c}\left(\sum_{j=1}^{r}W_{ij}^{2}\right)^{1/2}\right)^{2}\leq\frac{1}{c}\sum_{i=1}^{c}\left(\sum_{j=1}^{r}W_{ij}^{2}\right)=\frac{1}{c}\|W\|_{F}^{2}.$
(96)

Combining this with (95), we get

$\|\gamma(W)\|_{2,1}\leq m\sqrt{c}\|W\|_{F}\leq am\sqrt{c}.$ (97)

This concludes the proof.

Based on the summary of existing generalization bounds presented in (Li et
al., 2018), we list the original and simplified bounds for FNNs in Table 1.
The simplification is achieved by assuming that, for any layer
$i\in\\{1,...,L\\}$, the Lipschitz constant of activation function
$\sigma_{i}$ is equal to one, the output dimension $d_{i}$ is equal to $d$,
and $\|A_{i}\|_{\sigma}\leq s,\|A_{i}\|_{F}\leq a$. Then by Proposition 28, we
have $\|A_{i}\|_{2,1}\leq a\sqrt{d}$. Table 2 of generalization bounds for
FCNNs is obtained in a similar approach. The simplification column is achieved
by further assuming that, for any layer $i\in\\{1,...,L\\}$, the number of
channels denoted by $c_{i}$ is $c$, the size of each convolutional filter
$r_{i}$ is $r$, and each convolutional filter generates $m$ outputs. We also
assume that $\|\gamma_{i}(W_{i})\|_{\sigma}\leq s$ and $\|W_{i}\|_{F}\leq a$.
Then by Proposition 29, we have $\|\gamma_{i}(W_{i})\|_{2,1}\leq am\sqrt{c}$.

Ignoring constant factors independent of $L$, our result consistently
surpasses the results from (Bartlett et al., 2017; Neyshabur et al., 2017a) in
terms of the number of layers $L$ for both cases of FNNs and FCNNs. When
$L<\min\\{2^{L},s^{3L+1}\\}$, which is often the case in FNNs and FCNNs, our
result is also tighter than those from (Neyshabur et al., 2015; Golowich et
al., 2018; Li et al., 2018).

| Original Bound | Simplification
---|---|---
Neyshabur et al. (2015) | $\mathcal{O}\left(\frac{2^{L}\prod_{i=1}^{L}\|A_{i}\|_{F}}{\sqrt{n}}\right)$ | $\mathcal{O}\left(\frac{2^{L}a^{L}}{\sqrt{n}}\right)$
Bartlett et al. (2017) | $\widetilde{\mathcal{O}}\left(\frac{\prod_{i=1}^{L}\|A_{i}\|_{\sigma}}{\sqrt{n}}\left(\sum_{i=1}^{L}\frac{\|A_{i}\|_{2,1}^{\frac{2}{3}}}{\|A_{i}\|_{\sigma}^{\frac{2}{3}}}\right)^{\frac{3}{2}}\right)$ | $\widetilde{\mathcal{O}}\left(\frac{s^{L-1}L^{\frac{3}{2}}ad^{\frac{1}{2}}}{\sqrt{n}}\right)$
Neyshabur et al. (2017a) | $\widetilde{\mathcal{O}}\left(\frac{\prod_{i=1}^{L}\|A_{i}\|_{\sigma}}{\sqrt{n}}\sqrt{L^{2}d\sum_{i=1}^{L}\frac{\|A_{i}\|_{F}^{2}}{\|A_{i}\|_{\sigma}^{2}}}\right)$ | $\widetilde{\mathcal{O}}\left(\frac{s^{L-1}L^{\frac{3}{2}}ad^{\frac{1}{2}}}{\sqrt{n}}\right)$
Golowich et al. (2018) | $\widetilde{\mathcal{O}}\left(\prod_{i=1}^{L}\|A_{i}\|_{F}\cdot\min\left\\{\frac{1}{\sqrt[4]{n}},\sqrt{\frac{L}{n}}\right\\}\right)$ | $\widetilde{\mathcal{O}}\left(a^{L}\cdot\min\left\\{\frac{1}{\sqrt[4]{n}},\sqrt{\frac{L}{n}}\right\\}\right)$
Li et al. (2018) | $\widetilde{\mathcal{O}}\left(\frac{\prod_{i=1}^{L}\|A_{i}\|_{\sigma}\sqrt{Ld^{2}}}{\sqrt{n}}\right)$ | $\widetilde{\mathcal{O}}\left(\frac{s^{L}L^{\frac{1}{2}}d}{\sqrt{n}}\right)$
Our result | $\widetilde{\mathcal{O}}\left(\frac{\prod_{i=1}^{L}\|A_{i}\|_{\sigma}^{\frac{1}{4}}}{\sqrt{n}}\left(L^{2}d^{4}\sum_{i=1}^{L}\frac{\|A_{i}\|_{F}}{\|A_{i}\|_{\sigma}}\right)^{\frac{1}{4}}\right)$ | $\widetilde{\mathcal{O}}\left(\frac{s^{\frac{L-1}{4}}L^{\frac{3}{4}}a^{\frac{1}{4}}d}{\sqrt{n}}\right)$

Table 1: Comparison of generalization bounds for fully connected neural
networks.

| Original Bound | Simplification
---|---|---
Neyshabur et al. (2015) | $\mathcal{O}\left(\frac{2^{L}\prod_{i=1}^{L}\|\gamma_{i}(W_{i})\|_{F}}{\sqrt{n}}\right)$ | $\mathcal{O}\left(\frac{2^{L}a^{L}m^{\frac{L}{2}}}{\sqrt{n}}\right)$
Bartlett et al. (2017) | $\widetilde{\mathcal{O}}\left(\frac{\prod_{i=1}^{L}\|\gamma_{i}(W_{i})\|_{\sigma}}{\sqrt{n}}\left(\sum_{i=1}^{L}\frac{\|\gamma_{i}(W_{i})\|_{2,1}^{\frac{2}{3}}}{\|\gamma_{i}(W_{i})\|_{\sigma}^{\frac{2}{3}}}\right)^{\frac{3}{2}}\right)$ | $\widetilde{\mathcal{O}}\left(\frac{s^{L-1}L^{\frac{3}{2}}ac^{\frac{1}{2}}m}{\sqrt{n}}\right)$
Neyshabur et al. (2017a) | $\widetilde{\mathcal{O}}\left(\frac{\prod_{i=1}^{L}\|\gamma_{i}(W_{i})\|_{\sigma}}{\sqrt{n}}\sqrt{L^{2}cm\sum_{i=1}^{L}\frac{\|\gamma_{i}(W_{i})\|_{F}^{2}}{\|\gamma_{i}(W_{i})\|_{\sigma}^{2}}}\right)$ | $\widetilde{\mathcal{O}}\left(\frac{s^{L-1}L^{\frac{3}{2}}ac^{\frac{1}{2}}m}{\sqrt{n}}\right)$
Golowich et al. (2018) | $\widetilde{\mathcal{O}}\left(\prod_{i=1}^{L}\|\gamma_{i}(W_{i})\|_{F}\cdot\min\left\\{\frac{1}{\sqrt[4]{n}},\sqrt{\frac{L}{n}}\right\\}\right)$ | $\widetilde{\mathcal{O}}\left(a^{L}m^{\frac{L}{2}}\cdot\min\left\\{\frac{1}{\sqrt[4]{n}},\sqrt{\frac{L}{n}}\right\\}\right)$
Li et al. (2018) | $\widetilde{\mathcal{O}}\left(\frac{\prod_{i=1}^{L}\|\gamma_{i}(W_{i})\|_{\sigma}\sqrt{Lc^{2}m^{2}}}{\sqrt{n}}\right)$ | $\widetilde{\mathcal{O}}\left(\frac{s^{L}L^{\frac{1}{2}}cm}{\sqrt{n}}\right)$
Our result | $\widetilde{\mathcal{O}}\left(\frac{\prod_{i=1}^{L}\|\gamma_{i}(W_{i})\|_{\sigma}^{\frac{1}{4}}}{\sqrt{n}}\left(L^{2}c^{2}r^{2}\sqrt{m}\sum_{i=1}^{L}\frac{\|W_{i}\|_{F}}{\|\gamma_{i}(W_{i})\|_{\sigma}}\right)^{\frac{1}{4}}\right)$ | $\widetilde{\mathcal{O}}\left(\frac{s^{\frac{L-1}{4}}L^{\frac{3}{4}}a^{\frac{1}{4}}c^{\frac{1}{2}}m^{\frac{1}{8}}r^{\frac{1}{2}}}{\sqrt{n}}\right)$

Table 2: Comparison of generalization bounds for fully convolutional neural
networks.

###  6.2 Empirical Comparisons

In this section, we conduct experiments to empirically demonstrate the
advantage of our generalization bounds. We use MobileNet V1 (Howard et al.,
2017) and V2 (Sandler et al., 2018) to compare our FCNN bounds with others.
MobileNets extensively utilize depthwise separable convolutions to achieve
balance between efficiency and accuracy such that they are suitable to deploy
to mobile devices with limited computation power. In this experiment, we use
official trained weights of MobileNets
222https://github.com/tensorflow/models/tree/master/research/slim to
instantiate the network. For simplicity, we bound $\|\gamma(W)\|_{\sigma}$,
$\|\gamma(W)\|_{F}$, and $\|\gamma(W)\|_{2,1}$ in terms of $\|W\|_{F}$
according to Proposition 20, 22, 25, 27 and 29. Additionally, we ignore the
factors of the number of training sample $n$, as they are the same for all
generalization bounds discussed here. Based on the results shown in Figure 1,
we can see that our bound is much tighter than others empirically.

123456$10^{3}$$10^{24}$$10^{45}$$10^{66}$$10^{87}$1.93e834.32e308e303.81e753.41e301.6e10
(a) MobileNet v1

123456$10^{0}$$10^{39}$$10^{78}$$10^{117}$$10^{156}$2.41e1447.52e401.88e411.94e1296.85e405.1e12
(b) MobileNet v2

Figure 1: Comparison of generalization bounds for MobileNets. From left to
right, the bounds represent Neyshabur et al. (2015), Bartlett et al. (2017),
Neyshabur et al. (2017a), Golowich et al. (2018), Li et al. (2018) and our
result, respectively.

##  7 Conclusion

In this paper, we propose a margin-based generalization bound for general
convolutional neural networks that can have both fully connected layers and
convolutional layers. We study spectral norm for fully connected matrices
generated by three types of convolution operations including standard
convolution, depthwise convolution, and pointwise convolution. We show that
the proposed generalization bounds for MobileNets are indeed tighter compared
with existing bounds from both theoretical and experimental views. Such
advantage is achieved by exploring the sparsity and shared weights of
convolutional layers.

In the end, it is worth mentioning that generalization bounds derived for
convolutional neural networks cannot fully explain generalization phenomenon.
More effort is needed to improve our theoretical understanding on
generalization. We believe that generalization is achieved via combined
efforts from optimization algorithms, loss functions, the structure of
networks, and other factors. It is of interest to study how these factors
contribute to generalization individually and jointly.

## References

  * Anthony and Bartlett (2009) Martin Anthony and Peter L Bartlett.  _Neural network learning: Theoretical foundations_.  cambridge university press, 2009.
  * Arora et al. (2018) Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  _arXiv preprint arXiv:1802.05296_ , 2018.
  * Bartlett et al. (2017) Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky.  Spectrally-normalized margin bounds for neural networks.  In _Advances in Neural Information Processing Systems_ , pages 6240–6249, 2017.
  * Bengio and Delalleau (2011) Yoshua Bengio and Olivier Delalleau.  On the expressive power of deep architectures.  In _International Conference on Algorithmic Learning Theory_ , pages 18–36. Springer, 2011.
  * Blum and Rivest (1989) Avrim Blum and Ronald L Rivest.  Training a 3-node neural network is np-complete.  In _Advances in neural information processing systems_ , pages 494–501, 1989.
  * Brutzkus and Globerson (2017) Alon Brutzkus and Amir Globerson.  Globally optimal gradient descent for a convnet with gaussian inputs.  _arXiv preprint arXiv:1702.07966_ , 2017.
  * Chollet (2017) François Chollet.  Xception: Deep learning with depthwise separable convolutions.  _arXiv preprint_ , pages 1610–02357, 2017.
  * Choromanska et al. (2015) Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun.  The loss surfaces of multilayer networks.  In _Artificial Intelligence and Statistics_ , pages 192–204, 2015\.
  * Dauphin et al. (2014) Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio.  Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.  In _Advances in neural information processing systems_ , pages 2933–2941, 2014.
  * Dinh et al. (2017) Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio.  Sharp minima can generalize for deep nets.  _arXiv preprint arXiv:1703.04933_ , 2017.
  * Draxler et al. (2018) Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht.  Essentially no barriers in neural network energy landscape.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1309–1318, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.  URL http://proceedings.mlr.press/v80/draxler18a.html.
  * Du and Goel (2018) Simon S Du and Surbhi Goel.  Improved learning of one-hidden-layer convolutional neural networks with overlaps.  _arXiv preprint arXiv:1805.07798_ , 2018.
  * Du et al. (2017) Simon S Du, Jason D Lee, and Yuandong Tian.  When is a convolutional filter easy to learn?  _arXiv preprint arXiv:1709.06129_ , 2017.
  * Du et al. (2018) Simon S Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Ruslan Salakhutdinov, and Aarti Singh.  How many samples are needed to learn a convolutional neural network?  _stat_ , 1050:21, 2018.
  * Eldan and Shamir (2016) Ronen Eldan and Ohad Shamir.  The power of depth for feedforward neural networks.  In _Conference on Learning Theory_ , pages 907–940, 2016.
  * Garipov et al. (2018) Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew Gordon Wilson.  Loss surfaces, mode connectivity, and fast ensembling of dnns.  _arXiv preprint arXiv:1802.10026_ , 2018.
  * Ge et al. (2015) Rong Ge, Furong Huang, Chi Jin, and Yang Yuan.  Escaping from saddle points—online stochastic gradient for tensor decomposition.  In _Conference on Learning Theory_ , pages 797–842, 2015.
  * Ge et al. (2016) Rong Ge, Jason D Lee, and Tengyu Ma.  Matrix completion has no spurious local minimum.  In _Advances in Neural Information Processing Systems_ , pages 2973–2981, 2016.
  * Golowich et al. (2018) Noah Golowich, Alexander Rakhlin, and Ohad Shamir.  Size-independent sample complexity of neural networks.  In _Conference On Learning Theory_ , pages 297–299, 2018.
  * Gray et al. (2006) Robert M Gray et al.  Toeplitz and circulant matrices: A review.  _Foundations and Trends® in Communications and Information Theory_ , 2(3):155–239, 2006.
  * Hochreiter and Schmidhuber (1995) Sepp Hochreiter and Jürgen Schmidhuber.  Simplifying neural nets by discovering flat minima.  In _Advances in neural information processing systems_ , pages 529–536, 1995.
  * Hornik et al. (1989) Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Howard et al. (2017) Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _arXiv preprint arXiv:1704.04861_ , 2017.
  * Jin et al. (2017) Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan.  How to escape saddle points efficiently.  In _International Conference on Machine Learning_ , pages 1724–1732, 2017.
  * Kawaguchi (2016) Kenji Kawaguchi.  Deep learning without poor local minima.  In _Advances in Neural Information Processing Systems_ , pages 586–594, 2016.
  * Keskar et al. (2016) Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang.  On large-batch training for deep learning: Generalization gap and sharp minima.  _arXiv preprint arXiv:1609.04836_ , 2016.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In _Advances in neural information processing systems_ , pages 1097–1105, 2012.
  * Li et al. (2018) Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao.  On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond.  _arXiv preprint arXiv:1806.05159_ , 2018.
  * Livni et al. (2014) Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir.  On the computational efficiency of training neural networks.  In _Advances in Neural Information Processing Systems_ , pages 855–863, 2014.
  * Long et al. (2015) Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3431–3440, 2015.
  * Neyshabur et al. (2015) Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro.  Norm-based capacity control in neural networks.  In _Conference on Learning Theory_ , pages 1376–1401, 2015.
  * Neyshabur et al. (2017a) Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro.  A pac-bayesian approach to spectrally-normalized margin bounds for neural networks.  _arXiv preprint arXiv:1707.09564_ , 2017a.
  * Neyshabur et al. (2017b) Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro.  Exploring generalization in deep learning.  In _Advances in Neural Information Processing Systems_ , pages 5947–5956, 2017b.
  * Redmon et al. (2016) Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 779–788, 2016.
  * Ren et al. (2015) Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In _Advances in neural information processing systems_ , pages 91–99, 2015.
  * Sandler et al. (2018) Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4510–4520, 2018.
  * Shamir (2018) Ohad Shamir.  Distribution-specific hardness of learning neural networks.  _Journal of Machine Learning Research_ , 19(32), 2018.
  * Sharir and Shashua (2017) Or Sharir and Amnon Shashua.  On the expressive power of overlapping architectures of deep learning.  _arXiv preprint arXiv:1703.02065_ , 2017.
  * Wu (2016) Yihong Wu, 2016.  URL http://www.stat.yale.edu/~yw562/teaching/598/lec14.pdf.
  * Xu and Raginsky (2017) Aolin Xu and Maxim Raginsky.  Information-theoretic analysis of generalization capability of learning algorithms.  In _Advances in Neural Information Processing Systems_ , pages 2524–2533, 2017.
  * Zhang et al. (2016) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  _arXiv preprint arXiv:1611.03530_ , 2016.
  * Zhang et al. (2018) Jingwei Zhang, Tongliang Liu, and Dacheng Tao.  An information-theoretic view for deep learning.  _arXiv preprint arXiv:1804.09060_ , 2018.