Published as a conference paper at ICLR 2018 ON THE EXPRESSIVE POWER OF OVERLAPPING ARCHITECTURES OF DEEP LEARNING
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.
The paper studies convolutional neural networks where the stride is smaller than the convolutional filter size; the so called overlapping convolutional architectures. The main object of study is to quantify the benefits of overlap in convolutional architectures.
The main claim of the paper is Theorem 1, which is that overlapping convolutional architectures are efficient with respect to non-overlapping architectures, i.e., there exists functions in the overlapping architecture which require an exponential increase in size to be represented in the non-overlapping architecture; whereas overlapping architecture can capture within a linear size the functions represented by the non-overlapping architectures. The main workhorse behind the paper is the notion of rank of matricized grid tensors following a paper of Cohen and Shashua which capture the relationship between the inputs and the outputs, the function implemented by the neural network. 
(1) The results of the paper hold only for product pooling and linear activation function except for the representation layer, which allows general functions. It is unclear why the generalized convolutional networks are stated with such generality when the results apply only to this special case. That this is the case should be made clear in the title and abstract. The paper makes a point that generalized tensor decompositions can be potentially applied to solve the more general case, but since it is left as future work, the paper should make it clear throughout.
(2) The experiment is minimal and even the given experiment is not described well. What data augmentation was used for the CIFAR-10 dataset? It is only mentioned that the data is augmented with translations and horizontal flips. What is the factor of augmentation? How much translation? These are important because there maybe a much simpler explanation to the benefit of overlap: it is able to detect these translated patterns easily. Indeed, this simple intuition seems to be why the authors chose to make the problem by introducing translations and flips. 
(3) It is unclear if the paper resolves the mystery that they set out to solve, which is a reconciliation of the following two observations (a) why are non-overlapping architectures so common? (b) why only slight overlap is used in practice?  The paper seems to claim that since overlapping architectures have higher expressivity that answers (a). It appears that the paper does not answer (b) well: it points out that since there is exponential increase, there is no reason to increase it beyond a particular point. It seems the right resolution will be to show that after the overlap is set to a certain small value, there will be *only* linear increase with increasing overlap; i.e., the paper should show that small overlap networks are efficient with respect to *large* overlap networks; a comparison that does not seem to be made in the paper. 
(4) Small typo: the dimensions seem to be wrong in the line below the equation in page 3. 
The paper makes important progress on a highly relevant problem using a new methodology (borrowed from a previous paper). However, the writing is hurried and the high-level conclusions are not fully supported by theory and experiments.