  Expressive efficiency refers to the relation between two architectures A and
B, whereby any function realized by B could be replicated by A, but there
exists functions realized by A, which cannot be replicated by B unless its size
grows significantly larger. For example, it is known that deep networks are
exponentially efficient with respect to shallow networks, in the sense that a
shallow network must grow exponentially large in order to approximate the
functions represented by a deep network of polynomial size. In this work, we
extend the study of expressive efficiency to the attribute of network
connectivity and in particular to the effect of "overlaps" in the convolutional
process, i.e., when the stride of the convolution is smaller than its filter
size (receptive field). To theoretically analyze this aspect of network's
design, we focus on a well-established surrogate for ConvNets called
Convolutional Arithmetic Circuits (ConvACs), and then demonstrate empirically
that our results hold for standard ConvNets as well. Specifically, our analysis
shows that having overlapping local receptive fields, and more broadly denser
connectivity, results in an exponential increase in the expressive capacity of
neural networks. Moreover, while denser connectivity can increase the
expressive capacity, we show that the most common types of modern architectures
already exhibit exponential increase in expressivity, without relying on
fully-connected layers.
