Several state of the art convolutional networks rely on inter-connecting different layers to ease the flow of information and gradient between their input and output layers. These techniques have enabled practitioners to successfully train deep convolutional networks with hundreds of layers. Particularly, a novel way of interconnecting layers was introduced as the Dense Convolutional Network (DenseNet) and has achieved state of the art performance on relevant image recognition tasks. Despite their notable empirical success, their theoretical understanding is still limited. In this work, we address this problem by analyzing the effect of layer interconnection on the overall expressive power of a convolutional network. In particular, the connections used in DenseNet are compared with other types of inter-layer connectivity. We carry out a tensor analysis on the expressive power inter-connections on convolutional arithmetic circuits (ConvACs) and relate our results to standard convolutional networks. The analysis leads to performance bounds and practical guidelines for design of ConvACs. The generalization of these results are discussed for other kinds of convolutional networks via generalized tensor decompositions.
SUMMARY
Traditional convolutional neural networks consist of a sequence of information processing layers. However, one can relax this sequential design constraint so that higher layers receive inputs from one, some, or all preceding layers. This modification allows information to travel more freely throughout the network and has been shown to improve performance, e.g., in image recognition tasks. However, it is not clear whether this change in architecture truly increases representational capacity or it merely facilitates network training. 
In this paper, the authors present a theoretical analysis of the gain in representational capacity induced by additional inter-layer connections. The authors restrict their analysis to convolutional arithmetic circuits (ConvACs), a class of networks whose representational capacity has been studied previously. An important property of ConvACs is that the network mapping can be recast as a homogeneous polynomial over the input, with coefficients stored in a "grid tensor" $\mathcal{A}^y$. The grid tensor itself is a function of the hidden weight vectors $\mathbf{a}^{z,i}$. The authors first extend ConvACs to accommodate "dense" inter-layer connections and describe how adding dense connections affects the grid tensor. This analysis gives a potentially useful perspective for understanding the mappings that densely connected ConvACs compute.
The authors' main results (Theorems 5.1-5.3) analyze the "dense gain" of a densely connected ConvAC. This quantity roughly captures how much wider a standard ConvAC would need to be in order to represent the network mapping of a generic densely connected ConvAC. This is in a way a measure of the added representational power obtained from dense connections. The authors give upper bounds on this quantity, but also produce a case in which the upper bound is achieved. Importantly, the upper bounds are inversely proportional to a parameter $\lambda \leq 1$ controlling the rate at which hidden layer widths decay with increasing depth. The implication is that indeed densely connected ConvACs can have greater representational capacity, however the gain is limited to the case where hidden layers shrink exponentially with increasing depth.
These results are partly unsurprising, since densely connected ConvACs contain more trainable parameters than standard ConvACs. In Proposition 3, the authors give some criteria for evaluating when it is nonetheless worthwhile to add dense connections to a ConvAC.
COMMENTS
(1.) The authors address an interesting and important problem: explaining the empirical success of densely connected CNNs such as ResNets & DenseNets, relative to standard CNNs. The tensor algebra machinery built around ConvACs is impressive and seems to generate sound insights. However, I feel the current presentation fails to provide adequate intuition and interpretation of the results. Moreover, there is no overarching narrative linking the formal results together. This makes it difficult for the reader to grasp the main ideas and significance of the work without diving into all the details. For example:
- In Proposition 1, the authors comment that including a dense connection increases the rank of the grid tensor for a shallow densely connected convAC. However, the significance of grid tensor rank is not discussed.
- In Proposition 2, the authors do not explain why it is important that the added term $g(\mathbf{X})$ contains only polynomial terms of strictly smaller degree. It is not clear how Propositions 1 & 2 relate to the main Theorems 5.1-5.3. Is the characterization of the grid tensor in Proposition 1 used to obtain the bounds in the later Theorems?
- In Section 5, the authors introduce a parameter $\lambda \leq 1$ controlling how the widths of the hidden layers decay with increasing depth. This parameter seems central to the following bounds on dense gain, yet the authors do not motivate it, and there is no discussion of decaying hidden layer widths in previous sections.
- The practical significance of Proposition 3 is not sufficiently well explained. First, it is not clear how to use this result if all we have is an upper bound for $G_w$, as given by Theorems 5.1-5.2. It seems we would need a lower bound to be able to conclude that the ratio $\Delta P_{stand}/ \Delta P_{dense}$ is large. Second, it would be helpful if the authors commented on the implication for the special case $k=1$ and $r \leq (1/1+\lambda) \sqrt{M}$, where the dense gain is known.
(2.) Moreover, because the authors choose not to sketch the main proof ideas, it is difficult to identify the key novel insights, and how the special structure of densely connected ConvACs factors into the analysis. After studying the proofs in some detail, I have some specific concerns outlined below, which diminish the significance of the results and raise some doubts about soundness.
- In Theorem 5.1, the authors upper bound the dense gain by showing that arbitrary $(L, r, \lambda, k)$ dense ConvACs can be represented as standard $(L, r^\prime, \lambda, 0)$ ConvACs of sufficient width $r^\prime \geq G_w r$. The mechanism of the proof is to relate the grid tensor ranks of dense and standard ConvACs. However, a worst case bound on the grid tensor rank of a dense ConvAC is used, which does not seem to rely on the formulation of dense ConvACs. Thus, this result does not tell us anything in particular about dense ConvACs, but rather is a general result relating the expressive capacity of arbitrary depth-$L$ ConvACs and $(L, r^\prime, \lambda, 0)$ ConvACs with decaying widths.
- Central to Theorem 5.2 is the observation that a densely connected ConvAC can be viewed as a standard ConvAC, only with "virtually enlarged" hidden layers (of width $\tilde{r}_\ell = (1 + 1/\lambda)r_\ell$ for $k=1$, using the notation of the paper), and blocks of weights fixed to represent the identity mapping. This is a relatively simple idea, and one that seems to hold for general architectures. Thus, I believe Theorem 5.2 can be shown more simply and in greater generality, and without use of the tensor algebra machinery.
- There is some intuitive inconsistency in Theorem 5.3 which I would like some help resolving. We have seen that dense ConvACs can be viewed as standard ConvACs with larger hidden layers and some weights fixed. Effectively, the proof of Theorem 5.3 argues for a regime on $r, \lambda, M$ where this induced ConvAC uses its full representational capacity. This is surprising to me however, as I would have guessed that having some weights fixed makes this impossible. It would be very helpful if the authors could weigh in on this confusion. Perhaps there is an issue with the application of Lemmas 2 & 3 in the proof of Theorem 5.3. In Lemmas 2 & 3, we assume the tensors $\mathcal{A}$ and $\mathcal{B}$ are random. These Lemmas are applied in the proof of Theorem 5.3 to tensors $\phi^{\alpha, j, \gamma}$ appearing in the construction of the dense ConvAC grid tensor. However, the $\phi^{\alpha, j, \gamma}$ tensors do not seem completely random, as there are blocks of fixed weights. Can the authors please clarify how the randomness assumption is satisfied?
(3.) Lastly, I am concerned that the authors do not at least sketch how to generalize these results to architectures of more practical interest. As the authors point out, there is previous work generalizing theoretical results for ConvACs to convolutional rectifier networks. The authors should discuss whether a similar strategy might apply in this case.