  This work aims to provide understandings on the remarkable success of deep
convolutional neural networks (CNNs) by theoretically analyzing their
generalization performance and establishing optimization guarantees for
gradient descent based training algorithms. Specifically, for a CNN model
consisting of $l$ convolutional layers and one fully connected layer, we prove
that its generalization error is bounded by
$\mathcal{O}(\sqrt{\dt\widetilde{\varrho}/n})$ where $\theta$ denotes freedom
degree of the network parameters and
$\widetilde{\varrho}=\mathcal{O}(\log(\prod_{i=1}^{l}\rwi{i}
(\ki{i}-\si{i}+1)/p)+\log(\rf))$ encapsulates architecture parameters including
the kernel size $\ki{i}$, stride $\si{i}$, pooling size $p$ and parameter
magnitude $\rwi{i}$. To our best knowledge, this is the first generalization
bound that only depends on $\mathcal{O}(\log(\prod_{i=1}^{l+1}\rwi{i}))$,
tighter than existing ones that all involve an exponential term like
$\mathcal{O}(\prod_{i=1}^{l+1}\rwi{i})$. Besides, we prove that for an
arbitrary gradient descent algorithm, the computed approximate stationary point
by minimizing empirical risk is also an approximate stationary point to the
population risk. This well explains why gradient descent training algorithms
usually perform sufficiently well in practice. Furthermore, we prove the
one-to-one correspondence and convergence guarantees for the non-degenerate
stationary points between the empirical and population risks. It implies that
the computed local minimum for the empirical risk is also close to a local
minimum for the population risk, thus ensuring the good generalization
performance of CNNs.
