Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content:  The authors first extend the convolutional arithmetic circuits to
incorporate the dense connections. The expressiveness of the score
function(to be optimized while training) of the convolutional
arithmetic circuits, can be understood by the rank of a tensor
appearing in a decomposition of the network. Authors derive this
form for the DenseNet variant of convolutional arithmetic circuits,
and give bounds on the rank of the associated tensor and using these
bounds argue the expressive power of the network. The authors also
claim these bounds can help in practical guidelines while designing
the network.
The motivation and attempt is quite good, But the paper is written
quite poorly without any flow, it is very difficult for the reader
to understand the novelty or significance of the work, no intuition
is given and descriptions and so short and cryptic.
After Proposition 1, it is written there is no 'clear advantage' for
large N on using dense connections on a shallow convAC. It is not
very clear or obvious since the upper bound for the rank is
increasing with some parameter increase. This style of writing is
prevalent throughout the paper.
The DenseNet variant is deviating a lot from original Huang et al,
RelU is dropped, forward connections across blocks etc. Interblock
connections is not intuitively motivated. Most readers would find it
very difficult, which of the results apply in case of inter and
intra block connections. Looks like the results are mostly for inter
block connections, for which the empirical results are not there.
Theorem 5.1 and 5.2 gives some upper bound on dense gain(quantity
rough defines how much expressive power comes in by adding dense
connections, compared to standard convAC), but it is not clear how
an upper bound is helpful here. A lower bound would have been
helpful. The statement after theorem 5.1, by tailoring M and widths
'such that we exploit the expressiveness added by dense
connections'. This seems to very loosely written.
Overall I feel, the motivation and attempt is fine. But partly due
to the poor presentation style, deviation from DenseNets and unclear
nature of the practical usefulness of the results, the paper may not
be of contribution to the community at this stage.
review_title: The authors try to give a theoretical justification for DenseNet, which has interconnections between non-successive layers.

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper attempts to provide a theoretical justification for "DenseNet", a neural net architecture proposed by Huang et al. that contains connections between non-successive layers.  The general goal is to look at "arithmetic circuit" (AC) variants of DenseNets, in which ReLUs are replaced by linear combinations and pooling layers are replaced by products.  In AC versions of a network, the complexity of the final function computed (score function) can be understood via the rank of a certain tensor associated with the network. 

The paper shows bounds on the rank, and attempts to identify situations in which dense connections are likely to help increase the complexity of the function computed.

While the goal is good, I find too many aspects of the paper that are confusing, at least to someone not an expert on ConvACs.

- first, the definition of growth rate is quite different from the paper of Huang et al. (here, the rate is defined as the number of forward-layers a given layer is connected to, while Huang et al. define it as the number of 'new features' that get generated in the current layer). 

- second, if ReLUs are replaced by simple summations, then I feel that the point of dense blocks is lost (where the non-linearities in each step potentially add complexity). The paper adds the extra step of forward connections across blocks, but this makes the setup quite different from Huang et al.

- third, it appears that the bounds in Theorems 5.1, 5.2 are only _upper bounds_ on the rank.  From the definition of the dense gain, it seems that one would like to _lower bound_ the gain (as this would show that there is no ConvAC with small r' and k=0 that can realize a ConvAC with higher k and a given r).  Only theorem 5.3 says something of this kind, and even this looks very weak. The gap between r and r' is rather small.

- finally, the only "practical take-aways" (which the paper advertises) seem to be that if the dense gain is close to the general bound on G_w, then dense connections don't help. This seems quite weak to me.  Furthermore, it's not clear how G_w can be computed (given tensor rank is hard).

Overall, I found that the paper has too many red flags, and the lack of clarity in the writing makes it hard to judge.  I believe the paper isn't ready for publication in its current form.
review_title: Paper attempts to provide theoretic justification for 'DenseNet' by looking at an arithmetic circuit variant. There are many red flags and issues with writing, as explained below.

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
review_title: Review of Tensor Analysis of Convolutional Arithmetic Circuits

Meta-review: The paper performs a theoretical analysis of the representation power of convolutional networks with inter-layer connections. Whilst the results themselves are interesting, the current presentation of the paper stands in the way of the reading grasping and appreciating the main insights from the paper.

The authors acknowledge these issues in their rebuttal, but have not yet revised the paper to resolve them. I encourage the authors to revise the paper to address the reviewer comments, and re-submit it to another venue. 
Decision: Reject