Approximation Analysis of Convolutional Neural Networks

In its simplest form, convolution neural networks (CNNs) consist of a fully connected two-layer network g composed with a sequence of convolution layers T. Al-though g is known to have the universal approximation property, it is not known if CNNs, which have the form g degrees T inherit this property, especially when the kernel size in T is small. In this paper, we show that under suitable conditions, CNNs do inherit the universal approximation property and its sample complexity can be characterized. In ad-dition, we discuss concretely how the nonlinearity of T can improve the approximation power. Finally, we show that when the target function class has a certain compositional form, convolutional networks are far more advantageous compared with fully connected networks, in terms of the number of parameters needed to achieve the desired accuracy.