What Can Be Learnt With Wide Convolutional Neural Networks?
This provides theoretical insights into the learnability of CNNs for researchers in machine learning theory, though it is incremental as it builds on existing kernel methods and generalization bounds.
The paper studies infinitely-wide deep convolutional neural networks (CNNs) in the kernel regime, showing that their generalization error decay adapts to the spatial scale of the target function, with error rates controlled by the effective dimensionality of input subsets or the full input dimension. It finds that functions generated by such CNNs are too rich to be efficiently learnable in high dimensions.
Understanding how convolutional neural networks (CNNs) can efficiently learn high-dimensional functions remains a fundamental challenge. A popular belief is that these models harness the local and hierarchical structure of natural data such as images. Yet, we lack a quantitative understanding of how such structure affects performance, e.g., the rate of decay of the generalisation error with the number of training samples. In this paper, we study infinitely-wide deep CNNs in the kernel regime. First, we show that the spectrum of the corresponding kernel inherits the hierarchical structure of the network, and we characterise its asymptotics. Then, we use this result together with generalisation bounds to prove that deep CNNs adapt to the spatial scale of the target function. In particular, we find that if the target function depends on low-dimensional subsets of adjacent input variables, then the decay of the error is controlled by the effective dimensionality of these subsets. Conversely, if the target function depends on the full set of input variables, then the error decay is controlled by the input dimension. We conclude by computing the generalisation error of a deep CNN trained on the output of another deep CNN with randomly-initialised parameters. Interestingly, we find that, despite their hierarchical structure, the functions generated by infinitely-wide deep CNNs are too rich to be efficiently learnable in high dimension.