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. One of the most fundamental attributes of deep networks, and the reason for driving its empirical success, is the "Depth Efficiency" result which states that deeper models are exponentially more expressive than shallower models of similar size. Formal studies of Depth Efficiency include the early work on boolean or thresholded circuits BID19 BID25 Håstad and Goldmann, 1991; Hajnal et al., 1993) , and the more recent studies covering the types of networks used in practice BID13 BID12 Eldan and Shamir, 2016; BID5 BID23 BID16 . What makes the Depth Efficiency attribute so desirable, is that it brings exponential increase in expressive power through merely a polynomial change in the model, i.e. the addition of more layers. Nevertheless, depth is merely one among many architectural attributes that define modern networks. The deep networks used in practice consist of architectural features defined by various schemes of connectivity, convolution filter defined by size and stride, pooling geometry and activation functions. Whether or not those relate to expressive efficiency, as depth has proven to be, remains an open question.In order to study the effect of network design on expressive efficiency we should first define "efficiency" in broader terms. Given two network architectures A and B, we say that architecture A is expressively efficient with respect to architecture B, if the following two conditions hold: (i) any function h realized by B of size r B can be realized (or approximated) by A with size r A ∈ O(r B ); (ii) there exist a function h realized by A with size r A , that cannot be realized (or approximated) by B, unless r B ∈ Ω(f (r A )) for some super-linear function f . The exact definition of the sizes r A and r B depends on the measurement we care about, e.g. the number of parameters, or the number of "neurons". The nature of the function f in condition (ii) determines the type of efficiency taking place -if f is exponential then architecture A is said to be exponentially efficient with respect to architecture B, and if f is polynomial so is the expressive efficiency. Additionally, we say A is completely efficient with respect to B, if condition (ii) holds not just for some specific functions (realizable by A), but for all functions other than a negligible set.In this paper we study the efficiency associated with the architectural attribute of convolutions, namely the size of convolutional filters (receptive fields) and more importantly its proportion to their stride. We say that a network architecture is of the non-overlapping type when the size of the local receptive field in each layer is equal to the stride. In that case, the sets of pixels participating in the computation of each two neurons in the same layer are completely separated. When the stride is smaller than the receptive field we say that the network architecture is of the overlapping type. In the latter case, the overlapping degree is determined by the total receptive field and stride projected back to the input layer -the implication being that for the overlapping architecture the total receptive field and stride can grow much faster than with the non-overlapping case.As several studies have shown, non-overlapping convolutional networks do have some theoretical merits. Namely, non-overlapping networks are universal BID5 , i.e. they can approximate any function given sufficient resources, and in terms of optimization, under some conditions they actually possess better convergence guaranties than overlapping networks. Despite the above, there are only few instances of strictly non-overlapping networks used in practice (e.g. BID17 ; van den BID24 ), which raises the question of why are non-overlapping architectures so uncommon? Additionally, when examining the kinds of architectures typically used in recent years, which employ a mixture of both overlapping and nonoverlapping layers, there is a trend of using ever smaller receptive fields, as well as non-overlapping layers having an ever increasing role BID10 BID20 BID21 . Hence, the most common networks used practice, though not strictly non-overlapping, are increasingly approaching the non-overlapping regime, which raises the question of why having just slightly overlapping architectures seems sufficient for most tasks?In the following sections, we will shed some light on these questions by analyzing the role of overlaps through a surrogate class of convolutional networks called Convolutional Arithmetic Circuits (ConvACs) BID5 ) -instead of non-linear activations and average/max pooling layers, they employ linear activations and product pooling. ConvACs , as a theoretical framework to study ConvNets, have been the focused of several works, showing, amongst other things, that many of the results proven on this class are typically transferable to standard ConvNets as well . Though prior works on ConvACs have only considered non-overlapping architectures, we suggest a natural extension to the overlapping case that we call Overlapping ConvACs. In our analysis, which builds on the known relation between ConvACs and tensor decompositions, we prove that overlapping architectures are in fact completely and exponentially more efficient than non-overlapping ones, and that their expressive capacity is directly related to their overlapping degree. Moreover , we prove that having even a limited amount of overlapping is sufficient for attaining this exponential separation. To further ground our theoretical results, we demonstrate our findings through experiments with standard ConvNets on the CIFAR10 image classification dataset. The common belief amongst deep learning researchers has been that depth is one of the key factors in the success of deep networks -a belief formalized through the depth efficiency conjecture. Nevertheless, depth is one of many attributes specifying the architecture of deep networks, and each could potentially be just as important. In this paper, we studied the effect overlapping receptive fields have on the expressivity of the network, and found that having them, and more broadly denser connectivity, results in an exponential gain in the expressivity that is orthogonal to the depth.Our analysis sheds light on many trends and practices in contemporary design of neural networks. Previous studies have shown that non-overlapping architectures are already universal BID5 , and even have certain advantages in terms of optimization BID0 , and yet, real-world usage of non-overlapping networks is scarce. Though there could be multiple factors involved, our results clearly suggest that the main culprit is that non-overlapping networks are significantly handicapped in terms of expressivity compared to overlapping ones, explaining why the former are so rarely used. Additionally, when examining the networks that are commonly used in practice, where the majority of the layers are of the convolutional type with very small receptive field, and only few if any fully-connected layers BID18 BID20 He et al., 2016) , we find that though they are obviously overlapping, their overlapping degree is rather low. We showed that while denser connectivity can increase the expressive capacity, even in the most common types of modern architectures already exhibit exponential increase in expressivity, without relying on fully-connected layers. This could partly explain that somewhat surprising observation, as it is probable that such networks are sufficiently expressive for most practical needs simply because they are already in the exponential regime of expressivity. Indeed, our experiments seems to suggests the same, in which we saw that further increases in the overlapping degree beyond the most limited overlapping case seems to have insignificant effects on performance -a conjecture not quite proven by our current work, but one we wish to investigate in the future.There are relatively few other works which have studied the role of receptive fields in neural networks. Several empirical works BID9 BID8 have demonstrated similar behavior, showing that the classification accuracy of networks can sharply decline as the degree of overlaps is decreased, while also showing that gains from using very large local receptive fields are insignificant compared to the increase in computational resources. Other works studying the receptive fields of neural networks have mainly focused on how to learn them from the data Jia et al., 2012) . While our analysis has no direct implications to those specific works, it does lay the ground work for potentially guiding architecture design, through quantifying the expressivity of any given architecture. Lastly, BID11 studied the effective total receptive field of different layers, a property of a similar nature to our total receptive field, where they measure the the degree to which each input pixel is affecting the output of each activation. They show that under common random initialization of the weights, the effective total receptive field has a gaussian shape and is much smaller than the maximal total receptive field. They additionally demonstrate that during training the effective total receptive field grows in size, and suggests that weights should be initialized such that the initial effective receptive field is large. Their results strengthen our theory, by showing that trained networks tend to maximize their effective receptive field, taking full potential of their expressive capacity.To conclude, we have shown both theoretically and empirically that overlapping architectures have an expressive advantage compared to non-overlapping ones. Our theoretical analysis is grounded on the framework of ConvACs, which we extend to overlapping configurations. Though are proofs are limited to this specific case, previous studies have already shown that such results could be transferred to standard ConvNets as well, using most of the same mathematical machinery. While adapting our analysis accordingly is left for future work, our experiments on standard ConvNets (see sec. 5) already suggest that the core of our results should hold in this case as well. Finally, an interesting outcome of moving from non-overlapping architectures to overlapping ones is that the depth of a network is no longer capped at log 2 (input size), as has been the case in the models investigated by Cohen et al. DISPLAYFORM0 Figure 7: The original Convolutional Arithmetic Circuits as presented by BID5 .
We analyze how the degree of overlaps between the receptive fields of a convolutional network affects its expressive power. The paper studies the expressive power provided by "overlap" in convolution layers of DNNs by considering linear activations with product pooling. This paper analyzes the expressivity of convolutional arithmetic circuits and shows that an exponentialy large number of non-overlapping ConvACs are required to approximate the grid tensor of an overlapping ConvACs.