Title: A TENSOR ANALYSIS ON DENSE CONNECTIVITY VIA CONVOLUTIONAL ARITHMETIC CIRCUITS

Abstract: 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.

1. INTRODUCTION:

Recently, densely connected networks such as FractalNet (Larsson et al., 2016) , ResNet (He et al., 2016) , and DenseNet (Huang et al., 2016) , have obtained state of the art performance on large problems where highly deep network configurations are used. Adding dense connections between different layers of a network virtually shortens its depth, thus allowing a better flow of information and gradient through the network. This makes possible the training of highly deep models. Models with these types of connections have been successfully trained with hundreds of layers. More specifically, DenseNets have achieved state of the art performance on the CIFAR-10, CIFAR-100, SVHN, and ImageNet datasets, using models of up to 1 thousand layers in depth. Nevertheless, whether these connections provide a fundamental enhancement on the expressive power of a network, or just improve the training of the model, is still an open question. In Huang et al. (2016) , DenseNet models with 3 times less parameters than its counterpart (ResNets) were able to achieve the same performance on the ImageNet challenge. Moreover, a theoretical understanding of why the connections used by DenseNets lead to better performance compared with FractalNets or ResNets is still pending.

Despite the popularity of these models, there are few theoretical frameworks explaining the power of these models and providing insights to their performance. In Cohen et al. (2016a) , the authors considered convolutional networks with linear activations and product pooling layers, called convolutional arithmetic circuits (ConvACs), and argued for the expressiveness of deep networks using a tensor based analysis. This analysis has been extended to rectifier based convolutional networks via generalization of the tensor product Cohen & Shashua (2016a) . In Cohen & Shashua (2016a) , it was shown that ConvACs enjoy a greater expressive power than rectifier based models despite the popularity of rectifier based networks in practice. Indeed the empirical relevance of ConvAC was demonstrated through an architecture called SimNets Cohen et al. (2016b) . In addition, the generative ConvAC of Sharir et al. (2016) achieved state of the art performance in classification of images with missing pixels. These results served as motivation for the works of Cohen & Shashua (2016b) ; Cohen et al. (2017) ; Levine et al. (2017) ; Sharir & Shashua (2017) , where different aspects of ConvACs were studied from a theoretical perspective.

In Cohen & Shashua (2016b) the inductive bias introduced by pooling geometries was studied. Later, Levine et al. (2017) makes use of the quantum entanglement measure to analyze the inductive bias introduced by the correlations among the channels of ConvACs. Moreover, Sharir & Shashua (2017) generalizes the convolutional layer of ConvACs by allowing overlapping receptive fields, in other words permitting stride values lower than the convolution patch size. These locally overlapping connections led to an enhancement on the expressive capacity of ConvACs. The notion of inter-layer connectivity for ConvACs was addressed by Cohen et al. (2017) in the context of sequential data processing, such as audio and text related tasks. In that work, the expressive capabilities of interconnecting processing blocks from a sequence was studied. Nevertheless, these types of interconnections are related to the sequential nature of the problem and different from the ones used in ResNet, FractalNet and DenseNet.

In this work, we extend the tensor analysis framework of Cohen et al. (2016a) to obtain insightful knowledge about the effect of dense connections, from the kind used in DenseNets, FractalNet and ResNet, on the expressiveness of deep ConvACs. We study the expressive capabilities provided by different types of dense connections. Moreover, from these results we derive performance bounds and practical guidelines for selection of the hyperparameters of a deep ConvAC, such as layer widths and the topology of dense connections. These results serve as the first step into understanding dense connectivity in rectifier networks as well, since they can be further extended to include rectifier linear units, in the same spirit as the generalization of the tensor products done by Cohen & Shashua (2016a) .

The remainder of this paper is organized as follows. In Section 2, we introduce the notation and basic concepts from tensor algebra. In Section 3, we present the tensor representation of ConvACs as introduced by Cohen et al. (2016a) , and later in Section 4, we obtain tensor representations for densely connected ConvACs. In Section 5, performance bounds and design guidelines are derived for densely connected ConvACs.

2. PRELIMINARIES:

The term tensor refers to a multi-dimensional array, where the order of the tensor corresponds to the number of indexes required to access one of its entries. For instance, a vector is a tensor of order 1 while a matrix is a tensor of order 2. In general a tensor A of order N requires N indexes (d 1 , . . . , d N ) to access one of its elements. For the sake of notation, given I ∈ N, we use the expression [I] to denote the set {1, 2, . . . , I}. In addition, the (d 1 , . . . , d N )-th entry of a given tensor of order N and size

M 1 × M 2 × • • • × M N is denoted as A d1,...,d N , where d i ∈ [M i ] for all i ∈ [N ].

Moreover, for the particular case of tensors of order N with symmetric sizes

M 1 = M 2 = • • • = M N = M , we use (R M ) ⊗N as shorthand notation for R M ×•••×M . A crucial

operator in tensor analysis is the tensor product ⊗, since it is necessary for defining the rank of a tensor. For two tensors B ∈ R 

EQUATION

where Z ∈ N is sufficiently large and v

(i) z ∈ R Mi for i ∈ [N ].

Note that this statement is trivial for Z = N i=1 M i . On the other hand, when Z is the minimum number such that (1) is satisfied, the rank of the tensor is defined to be rank(A) = Z and (1) becomes equivalent to the well known CANDECOMP/PARAFAC (CP) decomposition of A. Another operator, that is on the core of the former works of Cohen & Shashua (2016a) ; Cohen et al. (2016a) ; Levine et al. (2017) , is the matricization operator. The operator [A] denotes the matricization of a tensor A ∈ R ×M N of order N . This matricization of the tensor A re-orders its elements into a matrix

[A] ∈ R M1•M3•••M N -1 ×M2•M4•••M N with A y d1,...,d N in the row 1 + N/2 i=1 (d 2i-1 -1) N/2 j=i+1 M 2j-1 and column 1 + N/2 i=1 (d 2i-1 -1) N/2 j=i+1 M 2j

. This is operator is of great use since it enjoys properties such as [A ⊗ B] = [A] [B] and rank(A) ≥ rank([A]), where denotes the Kronecker product of two matrices. Note that, since the Kronecker product is multiplicative in the rank, we have that rank

(A ⊗ B) ≥ rank([A ⊗ B]) = rank([A])rank([B]

) which is a central property of this theoretical analysis framework. A ConvAC is a convolutional neural network that utilizes linear activation functions with product pooling, unlike most popular convolutional networks which make use of rectifier activations with max or average pooling. Moreover, the input of the network is modeled by X = (x 1 , . . . , x N ) ∈ (R s ) N , where x i ∈ R s denotes the vectorization of the i-th patch of the input image. For this analysis, it is assumed that a set of M features is obtained from every patch, that is

3. CONVOLUTIONAL ARITHMETIC CIRCUITS AS TENSOR DECOMPOSITIONS:

M Z Z f θ d (x i ) conv(i, z) = a z,i , δ i δ i = [f θ1 (x i ), . . . , f θ M (x i )] pool(z) = N i=1 conv(i, z) h y (X) = a y , pool(:) conv pool (a) M r 0 r L-1 f θ d (x i ) conv 0 (j, γ) = a 0,j,γ , δ j δ i = [f θ1 (x i ), . . . , f θ M (x i )] pool 0 (j, γ) = j ∈{2j-1,2j} conv 0 (j , γ) h y (X) = a L,1,y , pool L-1 (:) • • • r L-1 r 0 pool L-1 (γ) = j ∈{1,2} conv L-1 (j , γ) (b)

f θ d (x i ) ∈ R for all i ∈ [N ], d ∈ [M ]

. These features are selected from a given parametric family F = {f θ : R s → R : θ ∈ Θ}, such as Gaussian kernels, wavelet functions, or learned features. Then, to determine whether an input X belongs to a class belonging to the set Y, the network evaluates the some score functions h y (X) ∈ R and decides for the class y ∈ Y such that

h y (X) = max y∈Y h y (X) .

Using this formulation, in Figure 1 (a) we observe an example of a single hidden layer ConvAC, while in Figure 1 (b) we observe the general case of a deep arithmetic circuit of L layers. As shown by Cohen et al. (2016a) , any score function of a ConvAC can be expressed as an homogeneous polynomial with degree N on the input features of the form

EQUATION

where A y d1,...,d N ∈ R are the polynomial coefficients stored in the grid-tensor

A y ∈ (R M ) ⊗ N . In other words, a score function h y (X) is a polynomial of M N variables f θ d (x i ) ∈ R for all i ∈ [N ], d ∈ [M ],

degree N , and M N polynomial coefficients stored in the grid-tensor A y .

For the special case of a shallow ConvAC with 1 × 1 convolutions and Z hidden units1 , shown in Figure 1 (a), the score functions are computed from the weight vectors a z,i [a z,i 1 , . . . , a z,i M ] T ∈ R M and a y [a y 1 , . . . , a y Z ] T ∈ R Z for all i ∈ [N ] and z ∈ [Z]. This leads to the score function

EQUATION

The first step of the tensor analysis framework is to obtain an expression (in terms of the network parameters a y z and a z,i d ) of the grid-tensor A y that represents this concrete network architecture. In other words, obtaining the expression for A y that transforms (2) into (3). This expression was already obtained in Cohen & Shashua (2016a) as

EQUATION

where ⊗ denotes the tensor product. Note that ( 4) is in the form of a standard CP decomposition of the grid tensor A y . This implies that the rank of A y is bounded by rank(A y ) ≤ Z. Moreover, the obtained results where generalized in Cohen et al. (2016a) for the case of a deep ConvAC with size-2 pooling windows2 , thus L = log 2 N hidden layers as shown in Figure 1 (b), leading to a grid-tensor given by the hierarchical tensor decomposition

EQUATION

where r 0 , . . . , r L-1 ∈ N are the number of channels in the hidden layers, {a 0

,j,γ ∈ R M } j∈[N ],γ∈[r0]

are the weights in the first hidden convolutions, {a l,j,γ ∈ R M } j∈[N/2 l ],γ∈[r l ] are the weights of the hidden layers, and a L,1,y ∈ R r L-1 stores the weights corresponding to the output y in the output layer.

4. DENSELY CONNECTED ARITHMETIC CIRCUITS:

The recent empirical success of densely connected networks (DenseNets), presented by Huang et al. (2016) , has served as motivation for our theoretical analysis on dense connectivity. Dense connectivity in a convolutional neural network refers to the case when a number k ∈ N (known as growth rate) of previous layers serve as input of the forthcoming layer. More precisely, in Huang et al. (2016) , a DenseNet performs this via concatenation along the feature dimension of the current layer inputs with the preceding layer features. Note that these feature must have compatible sizes along the spatial dimension for the concatenation to be possible. To address this issue, Huang et al. (2016) proposed to group blocks of the same spatial dimensions into a dense block, as shown in Figure 2 . These dense blocks do not contain operations such as pooling, that alter the spatial dimensions of the input features. Moreover, in the DenseNet architecture the layers that perform the pooling operation are called transition layers, since they serve as transition between dense blocks. For example, in Figure 2 we depict a dense block of 4 layers with growth rate k = 2, followed by a transition layer. In the original DenseNet these transition layers included one convolution layer before the pooling operation. Nevertheless, for this work we consider transition layers composed of only pooling operations. Note that this does not affect the generality of the model, since avoiding dense connections on the convolutional layer preceding the transition layer is equivalent to including a convolution in that transition layer3 .

Dense Block:

In the case of ConvACs, any dense block of size greater than 1 can be represented as a dense block of size 1, since the activation function is the linear function (the non-linearity comes from the product pooling operator in the transition layer). Therefore, for ConvACs, it is only reasonable to analyze dense blocks of size 1. Note that, if we only allow dense connections between hidden layers within a dense block, a ConvAC is limited to a maximum growth rate of k = 1. In order to analyze the effect of broader connectivity we extend the concept of growth rate by allowing dense connections between dense blocks. With proper pooling, outputs of hidden layers belonging to different dense blocks can also be concatenated along the feature dimension. In the reminder of this paper we refer to the dense connections between hidden layers of the same block as intra-block connections, while the connections between hidden layers of different blocks as inter-block connections.

4.1. DENSE INTRA-BLOCK CONNECTIONS:

In this section we analyze the effect of intra-block connections. We first start by constructing a densely connected version of a single hidden layer ConvAC. The resulting network with growth rate k = 1 is shown in Figure 3 (a). In the same manner as in (3), this architecture leads to the score function

EQUATION

Then, we present the following proposition regarding shallow ConvACs with dense connections of growth rate k = 1.

Proposition 1 The network's function of a densely connected shallow ConvAC shown in (6) corresponds to the grid tensor

EQUATION

where Sdiag N a y z+Z M z=1 ∈ (R M ) ⊗N denotes the super-diagonal tensor of order N with a y Z+1 , . . . , a y Z+M in its diagonal.

Proof See appendix B.1.

Note that the rank of this tensor is now bounded by rank(A y ) ≤ Z + M instead of Z, but adding these dense connections increases the number of parameters of the network from M N Z +Z +M . Then, for large values of N , there is no clear advantage on using dense connections on a shallow ConvAC. Nevertheless, in Section 5 we show that dense connections are capable of increasing the expressive power of deep ConvACs, specially for large values of N .

M N Z + Z to M Z Z f θ d (x i ) conv(i, z) = a z,i , δ i δ i pool(z) = N i=1 conv(i, z) h y (X) = a y , pool(:) M M conv pool concat (a) M r 0 r 2 r 2 r 0 r 1 r 1 M M r 0 r 0 r 1 r 1 (b) M r 0 r 2 r 2 r 0 r 1 r 1 M M (c)

We now generalize the obtained results for the case of a L-layered dense arithmetic circuit, with growth rare k = 1, as the one in Figure 3 (b). Similarly to (5), the obtained grid tensor has the hierarchical decomposition given by

EQUATION

. . .

EQUATION

From this result we observe that inter block connections account for virtually increasing the width of the network's hidden layers from r l to rl r l + r l-1 for all l = 0, 1, . . . , L -1, where r -1

M . Note that this increased width comes at the expense of increasing the network's parameters. Moreover, in Section 5 we discuss whether increasing the network's width via intra block dense connections leads to an enhancement in its overall expressive power.

4.2. DENSE INTER-BLOCK CONNECTIONS:

In this section we study broader connectivity via dense inter-block connections. As discussed in Section 4, proper pooling of the preceding features must take place before the concatenating them into the current layer. Since this type of connections have not been considered in the former DenseNets, we propose 3 possible ways of realizing such connections (via product, average, or max pooling).

For a ConvAC with pooling window size w pool , an inter block connection that connects block l ∈

[L] with block p ∈ [L] is said to be of jump length L jump ∈ [L -1] if p = l + L jump .

An example of an inter block connection of jump length L jump = 1 can be seen in Figure 3 (c). To perform this inter block connections, the sizes along the spatial dimensions of preceding features must be reduced by L jump w pool , before concatenating them along the feature dimension of layer l. This spatial size reduction may be realized via pooling of the preceding features with window size L jump w pool . When using a pooling layer the size along the feature dimension remains unchanged. Moreover, the type of pooling employed (product, average, or maximum) affects the expressive potential of the resulting ConvAC. Furthermore, the following proposition addresses the effect that adding dense inter block connections, via average pooling, has on the network function of a ConvAC.

Proposition 2 Adding inter block connections via average pooling of jump length L jump ≥ 1 to a standard ConvAC with grid-tensor A y ∈ (R M ) ⊗N leads to a network function of the form

h y (X) = M d1,...,d N =1 A y d1,...,d N N i=1 f θ d i (x i ) + g(X) ,

where g(X) contains polynomial terms on

f θ d (x i ) for d ∈ [M ], i ∈ [N ] of degree lower than N .

Remark 1 This result is also valid when the connections are done by addition instead of concatenation, as it is done in ResNet and FractalNet.

Proof See appendix B.2.

From this proposition we conclude that adding inter block connections average pooling does not alter the grid tensor A y , instead these connections account for extra polynomial terms of degree strictly less than N . Note that, for the special case where the input features belong to an exponential kernel family, such as F = {f θ (x) = e θ T x : R s → R : θ ∈ Θ} or F = {f θ (x) = e θ-x p : R s → R : θ ∈ Θ} where • p denotes the p norm with p ∈ N, the number of polynomial terms is equivalent to the number of exponential basis that the network function can realize. Therefore, the another valid measure of expressiveness is the number of polynomial terms a ConvAC is able to realize. Given a certain ConvAC topology, the number of polynomial terms can be computed inductively by expanding the polynomial products of every layer via generalized binomial expansions. Such an analysis is left for future contributions. Moreover, if we perform this connections via product poling, the features to be concatenated correspond to polynomial terms of the same order. This leads to a generalization of the intra-block connections from 4.1, leading to virtually increased widths rl r l + Ljump q=1 r l-1-q . Finally, we leave the analysis of inter-block connections via maximum pooling for future work and consider only product pooling inter-block connections in the remainder of this paper.

5. PRACTICAL IMPLICATIONS:

For the sake of comparison, let us assume networks with hidden layer widths r l decaying (or increasing) at an exponential rate of λ ∈ R. Formally, this is r l = λr l-1 ∈ N, thus r l = (λ) l r for all l = 0, 1, . . . , L -1, where r r 0 . To shorten the notation, we denote as (L, r, λ, k) to a ConvAC with of exponential width decay λ ∈ R, length L ∈ N, initial with r ∈ N and growth-rate k ∈ N. A growth-rate of k = 0 refers to a standard ConvAC with no dense connections.

Definition 1 Suppose that the weights of a (L, r, λ, k) ConvAC, with L, k ∈ N and r, λ ∈ R, are randomly drawn according to some continuous non-vanishing distribution. Then, this (L, r, λ, k) ConvAC is said to have weak dense gain G w ∈ R if, with probability p > 0, we obtain score functions that cannot be realized by a (L, r , λ, 0) ConvAC with r < G w r. When p = 1, this (L, r, λ, k) ConvAC is said to have a strong dense gain G s = G w ∈ R.

Using this definition we present a bound for the weak dense gain G w in the following theorem.

Theorem 5.1 Given M ∈ N, any a (L, r, λ, k) ConvAC with L > 1, r ≤ M, λ ≤ 1, k > 0 has a dense gain is bounden by G w ≤ M λr .

Proof See appendix B.3.

This general bound may serve as guideline for tayloring M and the widths r 0 , . . . , r L-1 such that we exploit the expressiveness added by dense connections.

Theorem 5.2 For the particular case of theorem 5.1 when k = 1, the weak dense gain is bounded by G w ≤ min 1 + 1 λ , M λr .

Proof See appendix B.3.

Using this result, we able able to quantify the expressive gain provided by dense inter block connections. If a ConvAC has a dense gain G w = (1 + 1 λ ) that is already close to the general bound from Theorem 5.1 it is less encouraging to include broader dense connections, since it would increase the number of parameters of the model while there is no room for a significant expressive gain increase. In this scenario, connections as the ones in ResNet and FractalNet may result more beneficial since they do not increase the size of the model, while at the same time enhancing its trainability.

Theorem 5.3 For the particular case of theorem 5.1 when k = 1, if r ≤ 1 1+λ √ M , then the bound of theorem 5.2 is achieved with equality and strong dense gain G s = 1 + 1 λ .

Proof See appendix B.3.

This last theorem shows that there exist a regime where this bounds can be achieved with strong dense gain. Whether this is true outside this regime is still an open question, since further knowledge about the rank of random tensors is limited. Moreover, these theorems does not consider the additional amount of parameters added by dense connections. We complete our analysis by addressing this issue in the following proposition.

Proposition 3 Let ∆P dense ∈ N be the additional number of parameters that are added to a (L, r, λ, 0) ConvAC when we introduce dense connections of growth-rate k > 0. In the same manner, let ∆P stand ∈ N be the number of parameters that are added to a (L, r, λ, 0) ConvAC when we increase its initial width r by a factor G ∈ R. Then the ratio between ∆P dense and ∆P stand is greater than

∆P stand ∆P dense ≥ (G -1)M r k q=1 λ -1-q L l=1 ( λ 2 2 ) l + (G 2 -1) k q=1 λ -q . Proof See appendix B.4.

The factor G from this proposition directly relates to the dense gain of a ConvAC, thus this ratio may be used to decide whether is interesting to add dense connections to a model (we want this ratio to be as large as possible). Finally Theorems 5.1 and 5.2 directly bound this ratio, which give the practitioner a guideline to decide which connections (if any) should be added to a given model.

A PRELIMINARY LEMMAS:

Lemma 1 Given Z ∈ N, let A ∈ (R M ) ⊗ P be a random tensor of even order P ≥ 2 such that

A = Z z=1 a (1) z ⊗ • • • ⊗ a (P ) z ,

where a

(k)

z ∈ R M are randomly drawn from a non-vanishing continuous distribution for all k ∈ [P ] and z ∈ [Z]. Then, if Z ≤ M P/2 we have that rank(A) = rank([A]) = Z with probability 1. This lemma also holds when for a subset Z ⊆ [Z] we have that a (k) z = a z e z ∈ R M for all z ∈ Z, where a z ∈ R are randomly drawn from a non-vanishing continuous distribution.

Proof Using the definition of the matricization operator, we get that the matricization A is

EQUATION

)

Note that, from this expression, it is straight forward to see that the rank of [A] is always less or equal than Z.

Let Z ⊆ [M P/2 ] be the subset Z = {z : z = M (P /2) -1 M -1 (z -1) + 1 : z ∈ [Z]} and U ∈ R M (P /2) ×M (P /2)

be a permuted version of [A] such that the first Z rows of U correspond to the rows z ∈ Z of [A], and the first Z columns of U correspond to the columns z ∈ Z of [A]. Since permuting the rows and the columns of a matrix does not alter its rank, we have that U has the same rank as [A] . Now, let us partition U into blocks as

U = P Q W Z ,

where P is of size Z-by-Z, and Q, W, Z have matching dimensions. Note that, if rank(P) = Z then rank(U) ≥ Z, which leads to

Z ≤ rank(U) = rank([A]) ≤ Z, thus rank([A]) = Z.

Therefore, it is sufficient to show that rank(P) = Z with probability 1 to conclude this proof. To that end, let us define the mapping from x ∈ R M P Z to P = P(x) as

x a

(1) T 1 , . . . , a

(1) T Z , a

(2) T 1 , . . . , a

(P ) T Z T .

Note that this definition of x implies that a 10), we have that [A] = [A](x), thus Q = Q(x) and P = P(x). Now, det P(x) is a polynomial on x, then it either vanishes in a set of measure zero or its the zero-polynomial (see Caron & Traynor (2005) ).

(i) z = a (i) z (x) for all z ∈ [Z] and i ∈ [P ]. Therefore, since [A] is computed as in (

If we set x to be equal to some x 0 ∈ R M P Z such that a

(i) z = e z for all z ∈ [Z] and i ∈ [P ], we have that ã(odd) z = ã(even) z = e z ∈ R M P /2 with z ( P/2-1 n=0 M n )(z -1) + 1 = M (P /2) -1 M -1 (z - 1) + 1. Therefore, since [A] is calculated as in (10) and ã(odd) z ã(even) T

z is now a matrix with 1 on the entry (z, z) and zero elsewhere, we have that [A](x 0 ) is a diagonal matrix with ones on the diagonal elements z ∈ Z and zero elsewhere. This leads to P(x 0 ) = I Z which has a determinant det P(x 0 ) = 0. Finally, since there exist x 0 such that the polynomial det P(x 0 ) is not zero, we conclude that det P(x) is not the zero-polynomial, which means that det P(x) = 0 with probability 1, thus proving this lemma.

Lemma 2 Let A ∈ (R M ) ⊗ P and B ∈ (R M ) ⊗ P be random tensors of even order P ≥ 2 and Z ∈ N be tensors such that

A = Z1 z=1 a (1) z ⊗ • • • ⊗ a (P ) z , B = Z2 z=1 b (1) z ⊗ • • • ⊗ b (P ) z , B DEFERRED PROOFS B.1 PROOF PROPOSITION 1

Proof We reformulate this (6) to have the same form as (3). To that end we define a d,i z , for z = Z + 1, . . . , Z + M , to be a z,i d = 1 if z -Z = d and zero otherwise. This definition of a z,i d leads to

M d=1 a z,i d f θ d (x i ) = f θ z-Z (x i ) for z = Z + 1, . . . , Z + M . Using this relation we get h y (X) = Z z=1 a y z N i=1 M d=1 a z,i d f θ d (x i ) + Z+M z=Z+1 a y z N i=1 M d=1 a z,i d f θ d (x i ) = Z+M z=1 a y z N i=1 M d=1 a z,i d f θ d (x i ) ,

which has the same form as (3). Therefore, as done in (4), we obtain the grid tensor for this architecture as

A y = Z+M z=1 a y z a z,1 ⊗ a z,2 ⊗ • • • ⊗ a z,N = Z z=1 a y z a z,1 ⊗ a z,2 ⊗ • • • ⊗ a z,N + Z+M z=Z+1 a y z a z,1 ⊗ a z,2 ⊗ • • • ⊗ a z,N = Z z=1 a y z a z,1 ⊗ a z,2 ⊗ • • • ⊗ a z,N + Z+M z=Z+1 a y z e z-Z ⊗ e z-Z ⊗ • • • ⊗ e z-Z = Z z=1 a y z a z,1 ⊗ a z,2 ⊗ • • • ⊗ a z,N + Sdiag N a y z+Z M z=1 ,

thus proving this proposition.

B.2 PROOF PROPOSITION 2:

Proof Given x

[f θ1 (x 1 ), • • • , f θ M (x 1 ), f θ2 (x 1 ), • • • , f θ M (x N )] T ∈ R M N

, the output of the l-th layer of a (L, r, λ, 0) ConvAC can be stored into the vectors of mappings δ l,j (x) [δ l,j 1 (x), . . . , δ l,j r l (x)] T ∈ R r l for j ∈ [N/2 l ] and l ∈ [L]. Moreover, since the entries of these vectors are the result of l -1 convolution-pooling layers with product pooling of window size 2, all the mappings δ l,j 1 (x) can be expressed as a sum of polynomial terms on x of degree 2 l . Now, let the coefficient vectors a l,j,γ [a l,j,γ 1 , . . . , a l,j,γ r l ] T ∈ R r l for j ∈ [N/2 l ] and γ ∈ [r l+1 ], be the weight vectors for the convolution of the l-th layer. To shorten the notation we use a l,j,γ , δ l,j = r l d=1 a l,j,γ d δ l,j d as shorthand for the convolution between these vectors. Then, the outputs the the layer l of this ConvAC are given by δ l+1,j ∈ R r l+1 with δ l+1,j γ = a l,2j-1,γ , δ l,2j-1 a l,2j,γ , δ l,2j for j ∈ [N/2 l+1 ], γ ∈ [r l+1 ]. If we recursively calculate these out vectors up to the L-th layer we obtain the score functions h y stand (x) δ L,1 (x) = δ L,1 1 (x) ∈ R. We now consider the effecct of adding dense connections via average pooling from some k ∈ N preceding layers l -1, . . . , l -k. To this end, let rl = k q=1 r l-q be the total size along the feature dimesnion of the vectors to be concatenated. In addition, let ω l,j (x)

[ω l,j 1 (x), . . . , ω l,j rl (x)] T ∈ R rl be the vectors of mappings of the corresponding preceeding features at the layer l for j ∈ [N/r l ]. In order to compute the convolutions of this layer, an additional vector of coefficients is required as b l,j,γ [b l,j,γ 1 , . . . , b l,j,γ rl ] T ∈ R rl . Then, the outputs of the l-th layer of this (L, r, λ, k) ConvAC are the denoted as the vectors δl,j (x) [ δl,j 1 (x), . . . , δl,j r l+1 (x)] T ∈ R r l+1 for j ∈ [N/2 l+1 ] where δl+1,j = a l,2j-1,γ b l,2j-1,γ , δ l,2j-1 ω l,2j-1 a l,2j,γ b l,2j,γ , δ l,2j ω l,2j .

From this expression it follows δl+1,j = ( a l,2j-1,γ , δ l,2j-1 + b l,2j-1,γ , ω l,2j )( a l,2j,γ , δ l,2j + b l,2j,γ , ω l,2j ) = δ l+1,j + ω l+1,j , where ω l+1,j = b l,2j-1,γ , ω l,2j-1 a l,2j,γ , δ l,2j + a l,2j-1,γ , δ l,2j-1 b l,2j,γ , ω l,2j

+ b l,2j-1,γ , ω l,2j-1 b l,2j,γ , ω l,2j .

Note that the entries of ω l,j (x) are assumed to come from preceding layers with an appropiate average pooling. Since performing avergae pooling does not increase the degree of the polynomial terms involved (only product pooling does) and the jump length Ljump is at least 1, the entries of ω l,j (x) have at most polynomial degree 2 l-1 , which is strictly less than the degree of the entries of δ l,j (x) (i.e., 2 l ). Therefore, from the obtained expression of ω l+1,j we observe that it has polynomials withb degree no greater than 2 l + 2 l-1 , while the entries of δ l+1,j have a strictly higher degree of

2 l + 2 l = 2 l+1 .

Moreover, since a l,j,γ , δ l,j + ω l,j can be expressed as a l,j,γ , δ l,j + ω l,j = a l,j,γ a l,j,γ ,

EQUATION

we can make use of the obtained results in an unductive manner up to the L-th layer, thus leading to

h y dense (x) = h y stand (x) + g(x)

, where g(x) contains polynomial terms of x of order strictly less than N , thus proving this theorem. Note that this result also applies to additive and resudial connections, as de ones used in ResNet and FractalNet, since they can be expressed as in (11).

B.3 PROOF OF THEOREMS 5.1 TO 5.3

Proof Given M ∈ N, a (L, r, λ, 0) ConvAC with L > 1, r ≤ M, λ ≤ 1 has a grid tensor A y stand ∈ (R M ) ⊗N . For the forthcoming analysis let us assume r 0 ≤ M . This assumption is done, so that we can write min{r 0 , M } = r 0 , merely for notation purposes since we show that this does not affect the generality of the results. Using this assumption, we upper bound the rank of the grid tensor as

rank φ 1,j,γ = rank r0 α=1 a 1,j,γ α a 0,2j-1,α ⊗ a 0,2j,α ≤ min{r 0 , M } = r 0 rank φ 2,j,γ ≤ r1 α=1 rank φ 1,2j-1,α ⊗ φ 1,2j,α ≤ r1 α=1 rank φ 1,2j-1,α rank φ 1,2j,α = r 1 r 2 0 . . . rank φ l,j,γ ≤ r l-1 α=1 rank φ l-1,2j-1,α ⊗ φ l-1,2j,α ≤ r l-1 α=1 rank φ l-1,2j-1,α rank φ l-1,2j,α . (12)

It was shown in Cohen & Shashua (2016a) that, when the weights are independently generated from some continuous distribution, we have that rank φ 1,j,γ = min{r 0 , M } with probability 1. Note that, the bounds obtained for r 0 values greater than M is the same as for r 0 = M , thus implying that the assumption of r 0 ≤ M does not affect the generality of the results. Finally, by induction up to the L-th layer, we obtain a bound for the grid tensor rank as

EQUATION

Since we assumed networks with hidden layer widths r l decaying (or increasing) at an exponential rate of λ ∈ R. Formally, this is r l = λr l-1 ∈ N, thus r l = (λ) l r for all l = 0, 1, . . . , L -1, where r r 0 . Therefore, we may simplify the obtained bound to

rank (A y stand ) ≤ L-1 l=0 ((λ) l r) 2 L-l-1 = (λ) L-1 l=0 l2 L-l-1 r L-1 l=0 2 L-l-1 = (λ) 2 L -1-L r 2 L -1 .

We this analysis by proving Theorem 5.1. To that end let A y dense be the grid tensor of a dense (L, r, λ, k) ConvAC with k > 0, while A y stand is the grid tensor of a (L, r , λ, 0) ConvAC with r ∈ R. As discussed in Section 4, this dense version of the former (L, r, λ, 0) ConvAC is equivalent to virtually increasing the widths of the ConvAC, which translates extra additive terms in the expressions from 12. Moreover, using corollary 1 we observe that, if the ranks of the tensors φ l,j,γ are additive and multiplicative up to rank(A y dense ) > rank(A y stand ), so they are up to rank(A y stand ). A weak dense gain value G w ∈ R is achieved when there is a set of functions realized by the (L, r, λ, k) ConvAC that cannot be realized by (L, r , λ, 0) ConvAC unless r = G w r. To bound this gain, let us assume the best case scenario where rank(A y dense ) reaches the maximum possible rank, from the size of A y dense this can be at most rank(A y dense ) = M 2 L -1 . As discussed, would imply that the ranks of the tensors φ l,j,γ are additive up to M 2 L -1 for both ConvACs. Therefore, A y stand achieves its maximum rank given by rank (A y stand ) = (λ) 2 L -1-L (r ) 2 L -1 . Then, a (L, r , λ, 0) ConvAC is able to realize the functions of a (L, r, λ, k) ConvAC when rank (A y stand ) = rank (A y dense ), thus (λ) 2 L -1-L (r ) 2 L -1 = M 2 L -1 . Finally, since r = G w r, this leads to a maximum value of

G w = M λr λ L 2 L -1 ≤ M λr ,

which proves Theorem 5.1.

For Theorem 5.2 we use consider the particular case of k = 1, which yields a core tensor given by the hierarchical tensor decomposition from (9). We use the same assumption of r 0 ≤ M and define the virtually increased widths rl r l + r l-1 ∈ N for l = 1, . . . , L -1 and r0 M . This leads to rank φ 1,j,γ = rank

EQUATION

Note that for r l = λr l-1 ∈ N (λ ∈ R), we get virtually increased widths rl = (1 + λ) l r = λ 1 + 1 λ l r, for all l = 0, 1, . . . , L -1, leading to

EQUATION

)

As in for the proof of Theorem 5.1, the maximum dense gain G w is obtained when rank(A y dense ) reaches the maximum possible rank. In this particular case, this corresponds to rank(A y dense ) = min (λ

EQUATION

is required, thus proving Theorem 5.2.

Finally, for proving Theorem 5.3 we show that this bound can be attained with probability 1.

Note that this bound is achieved when the inequalities from (12) hold with equality for all l ∈ [L].

The first inequality of (12) holds when the tensors φ l-1,2j-1,1 ⊗ φ l-1,2j,1 , • • • , φ l-1,2j-1,r l-1 ⊗ φ l-1,2j,r l-1 are additive on the rank. This can be proven to be true with probability 1 when

r l-1 α=1 rank φ l-1,2j-1,α ⊗ φ l-1,2j,α ≤ M 2 l-1

(16) by applying Lemma 3. In the same manner, the second inequality of (12) holds when the tensor pairs φ l-1,2j-1,α , φ l-1,2j,α are multiplicative in the tensor rank. We may use Lemma 2 to prove this is the case with probability 1 if we can bound

EQUATION

)

In summary, if equations ( 16) and ( 17) hold, we may use Lemmas 3 and 2 to prove that (12) reaches equality with probability 1, thus implying that (13) also reaches equality everywhere outside a set Lebesgue measure zero. It is straight forward to see that, if (16) holds, so does (17).

For the case of a network with exponential width decay λ and r ≤ 1 λ √ M we have that r l-1 α=1 rank φ l-1,2j-1,α ⊗ φ l-1,2j,α ≤ (λ) 2 l -1-l r 2 l -1 ≤ (λ) 2 l r 2 l ≤ (λ) 2 l 1 λ

EQUATION

thus ( 16) holds. Therefore, within this regime of r ≤ 1 λ √ M , we may ensure that the tensor rank is additive and multiplicative with probability 1. Now we apply the same reasoning for a densely connected arithmetic circuit of L layers and width decay λ such that r ≤ 1 1+λ √ M = 1 λ(1+1/λ) √ M . In the same manner as for the standard ConvAC we bound r l-1 α=1 rank φ l-1,2j-1,α ⊗ φ l-1,2j,α ≤ (λ(1 + 1/λ))

2 l -1-l r 2 l -1 ≤ (λ(1 + 1/λ))

2 l r 2 l ≤ (λ(1 + 1/λ)) 2 l 1 λ(1 + 1/λ) √ M 2 l = M 2 l-1

, which enables us to make use of Lemmas 3 and 2 to prove that (15) holds with equality everywhere except from a set of Lebesgue measure zero. Note that, for r ≤ 1 1+λ √ M < 1 λ √ M , we have that both equations ( 13) and ( 15) reach equality with probability 1, thus proving Theorem 5.3.

B.4 PROOF PROPOSITION 3:

Proof Let P (L, r, λ, k) ∈ N be the number of parameters of a (L, r, λ, k) ConvAC. A standard (L, r, λ, 0) ConvAC is composed of the weights {a 0,j,γ ∈ R M } j∈[N ],γ∈ [r0] in the first hidden convolutions, {a l,j,γ ∈ R M } j∈[N/2 l ],γ∈[r l ] in the hidden layers, and a L,1,y ∈ R r L-1 in the weights corresponding to the output y in the output layer. Therefore, this ConvAC has a number of weights P (L, r, λ, 0) = M N r 0 + L l=1 N 2 l r l r l-1 + Y r L When adding dense connections of growth-rate k, we need additional weights for the convolution between the preceding layers and the current layer. Therefore, at the l-th layer we have an extra k q=1 N 2 l r l r l-1-q weights, which leads to

P (L, r, λ, k) = M N r 0 + L l=1 N 2 l r l r l-1 + L l=1 k q=1 N 2 l r l r l-1-q + Y r L .

By definition, we have that ∆P std = P (L, Gr, λ, 0) -P (L, Gr, λ, 0) and ∆P dense = P (L, Gr, λ, k) -P (L, r, λ, 0), thus yielding

∆P std = (G -1)(M N r 0 + Y r L ) + (G 2 -1) L l=1 N 2 l r l r l-1 = (G -1)(M N r + λ L Y r) + (G 2 -1) L l=1 N 2 l λ 2l-1 r 2 = (G -1)(M N + λ L Y )r + (G 2 -1)N λ -1 r 2 L l=1 ( λ 2 2 ) l

and

∆P dense = k q=1 L l=1 N 2 l r l r l-1-q = N r 2 k q=1 λ -1-q L l=1 ( λ 2 2 ) l .

Finnaly, we use these expressions to compute the ratio of interest as

∆P std ∆P dense = (G -1)(M N + λ L Y )r + (G 2 -1)N λ -1 r 2 L l=1 ( λ 2 2 ) l N r 2 k q=1 λ -1-q L l=1 ( λ 2 2 ) l = (G -1)(M N + λ L Y ) N r k q=1 λ -1-q L l=1 ( λ 2 2 ) l + (G 2 -1) k q=1 λ -1-q ≥ (G -1)M r k q=1 λ -1-q L l=1 ( λ 2 2 ) l + (G 2 -1)

k q=1 λ -q which proves this proposition.

:

We must mention that the generalization to w × w convolutions is straightforward and was already covered byCohen & Shashua (2016a).

Note that the generalization to different pooling sizes is straight forward and was done byCohen & Shashua (2016a).

This would effectively reduce the dense block size by 1.

Figures and Tables:

Figure 1: (a) Example of a shallow (i.e., L = 1) convolutional arithmetic circuit. (b) Example of a deep convolutional arithmetic circuit.

Figure 2: Example of a dense block of size 4 with growth rate k = 2.

Figure 3: (a) Example of a shallow (L = 1) convolutional arithmetic circuit with one intra-block connection. (b) Example of a 3 layered (L = 3) convolutional arithmetic circuit with multiple intrablock connections. (c) Example of a 3 layered (L = 3) convolutional arithmetic circuit with one inter-block connection.

M1×

Table content: <table/>

Mp+1×

Table content: <table/>

••×Mp+q , the tensor product is defined such that B ⊗ C ∈ R

Table content: <table/>

M1×

Table content: <table/>

••×Mp+q and (B ⊗ C) d1,...,dp+q = B d1,...,dp C dp+1,...,dp+q for all (d 1 , . . . , d p+q ). In tensor algebra, a tensor

Table content: <table/>

M1×

Table content: <table/>

Peer review (iclr2018):
 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.