  The success of deep convolutional networks on on tasks involving
high-dimensional data such as images or audio suggests that they are able to
efficiently approximate certain classes of functions that are not cursed by
dimensionality. In this paper, we study this theoretically and empirically
through the lens of kernel methods, by considering multi-layer convolutional
kernels, which have achieved good empirical performance on standard vision
datasets, and provide theoretical descriptions of over-parameterized
convolutional networks in certain regimes. We find that while expressive
kernels operating on input patches are important at the first layer, simpler
polynomial kernels can suffice in higher layers for good performance. For such
simplified models, we provide a precise functional description of the RKHS and
its regularization properties, highlighting the role of depth for capturing
interactions between different parts of the input signal, and the role of
pooling for encouraging smooth dependence on the global or relative positions
of such parts.
