  A major challenge in understanding the generalization of deep learning is to
explain why (stochastic) gradient descent can exploit the network architecture
to find solutions that have good generalization performance when using high
capacity models. We find simple but realistic examples showing that this
phenomenon exists even when learning linear classifiers --- between two linear
networks with the same capacity, the one with a convolutional layer can
generalize better than the other when the data distribution has some underlying
spatial structure. We argue that this difference results from a combination of
the convolution architecture, data distribution and gradient descent, all of
which are necessary to be included in a meaningful analysis. We provide a
general analysis of the generalization performance as a function of data
distribution and convolutional filter size, given gradient descent as the
optimization algorithm, then interpret the results using concrete examples.
Experimental results show that our analysis is able to explain what happens in
our introduced examples.
