Theoretical Analysis of Inductive Biases in Deep Convolutional Networks

In this paper, we provide a theoretical analysis of the inductive biases in convolutional neural networks (CNNs). We start by examining the universality of CNNs, i.e., the ability to approximate any continuous functions. We prove that a depth of O(log d) suffices for deep CNNs to achieve this universality, where d in the input dimension. Additionally, we establish that learning sparse functions with CNNs requires only widetildeO(log2d) samples, indicating that deep CNNs can efficiently capture em long-range sparse correlations. These results are made possible through a novel combination of the multichanneling and downsampling when increasing the network depth. We also delve into the distinct roles of weight sharing and locality in CNNs. To this end, we compare the performance of CNNs, locally-connected networks (LCNs), and fully-connected networks (FCNs) on a simple regression task, where LCNs can be viewed as CNNs without weight sharing. On the one hand, we prove that LCNs require Omega(d) samples while CNNs need only widetildeO(log2d) samples, highlighting the critical role of weight sharing. On the other hand, we prove that FCNs require Omega(d2) samples, whereas LCNs need only widetildeO(d) samples, underscoring the importance of locality. These provable separations quantify the difference between the two biases, and the major observation behind our proof is that weight sharing and locality break different symmetries in the learning process.