Title: BOOSTING DILATED CONVOLUTIONAL NETWORKS WITH MIXED TENSOR DECOMPOSITIONS

Abstract: The driving force behind deep networks is their ability to compactly represent rich classes of functions. The primary notion for formally reasoning about this phenomenon is expressive efficiency, which refers to a situation where one network must grow unfeasibly large in order to replicate functions of another. To date, expressive efficiency analyses focused on the architectural feature of depth, showing that deep networks are representationally superior to shallow ones. In this paper we study the expressive efficiency brought forth by connectivity, motivated by the observation that modern networks interconnect their layers in elaborate ways. We focus on dilated convolutional networks, a family of deep models delivering state of the art performance in sequence processing tasks. By introducing and analyzing the concept of mixed tensor decompositions, we prove that interconnecting dilated convolutional networks can lead to expressive efficiency. In particular, we show that even a single connection between intermediate layers can already lead to an almost quadratic gap, which in large-scale settings typically makes the difference between a model that is practical and one that is not. Empirical evaluation demonstrates how the expressive efficiency of connectivity, similarly to that of depth, translates into gains in accuracy. This leads us to believe that expressive efficiency may serve a key role in developing new tools for deep network design.

1. INTRODUCTION:

One of the key attributes fueling the success of deep learning is the ability of deep networks to compactly represent rich classes of functions. This phenomenon has drawn considerable attention from the theoretical machine learning community in recent years. The primary notion for formally reasoning about the representational abilities of different models is expressive efficiency. Given two network architectures A and B, with size parameters (typically the width of layers across a network) r A and r B , we say that architecture A is expressively efficient w.r.t. architecture B if the following two conditions hold: (i) any function realized by B with size r B can be realized (or approximated) by A with size r A ∈ O(r B ); (ii) there exist functions realized by A with size r A that cannot be realized (or approximated) by B unless its size meets r B ∈ Ω(f (r A )) for some superlinear function f . 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 expressively efficient w.r.t. architecture B, and if f is polynomial so is the expressive efficiency of A over B.

To date, works studying expressive efficiency in the context of deep learning (e.g. Delalleau and Bengio (2011) ; Pascanu et al. (2013) ; Montufar et al. (2014) ; Telgarsky (2015) ; Eldan and Shamir (2015) ; Poole et al. (2016) ; Raghu et al. (2016) ; Cohen et al. (2016b) ; Cohen and Shashua (2016) ; Poggio et al. (2015) ; Mhaskar et al. (2016) ) have focused on the architectural feature of depth, showing instances where deep networks are expressively efficient w.r.t. shallow ones. This theoretical focus is motivated by the vast empirical evidence supporting the importance of depth (cf. LeCun et al. (2015) ). However, it largely overlooks an additional architectural feature that in recent years is proving to have great impact on the performance of deep networks -connectivity. Nearly all state of the art networks these days (e.g. Szegedy et al. (2015) ; He et al. (2015) ; Huang et al. (2016b; a) ) deviate from the simple feed-forward (chain) approach, running layers connected under various schemes. Whether or not this relates to expressive efficiency remains to be an open question.

A specific family of deep networks gaining increased attention in the deep learning community is that of dilated convolutional networks. These models form the basis of the recent WaveNet (van den Oord et al. (2016) ) and ByteNet (Kalchbrenner et al. (2016) ) architectures, which provide state of the art performance in audio and text processing tasks. Dilated convolutional networks are frequently applied to sequence data, and consist of multiple succeeding convolutional layers, each comprising non-contiguous filters with a different dilation (distance between neighboring elements). The choice of dilations directly affects the space of functions that may be realized by a network, and while no choice is expressively efficient w.r.t. another, we show in this work that interconnecting networks with different dilations leads to expressive efficiency, and by this demonstrate that connectivity indeed bears the potential to enhance the expressiveness of deep networks.

Our analysis follows several recent works utilizing tensor decompositions for theoretical studies of deep learning (e.g. Janzamin et al. (2015) ; Sedghi and Anandkumar (2016) ), and in particular, builds on the equivalence between hierarchical tensor decompositions and convolutional networks established in Cohen et al. (2016b) and Cohen and Shashua (2016) . We show that with dilated convolutional networks, the choice of dilations throughout a network corresponds to determination of the mode (dimension) tree underlying the respective decomposition. We then define the notion of a mixed tensor decomposition, which blends together multiple mode trees, effectively creating a large ensemble of hybrid trees formed from all possible combinations. Mixed tensor decompositions correspond to mixed dilated convolutional networks, i.e. mixtures formed by connecting intermediate layers of different dilated convolutional networks. This allows studying the expressive properties of such mixtures using mathematical machinery from the field of tensor analysis. We fully analyze a particular case of dilated convolutional arithmetic circuits, showing that a single connection between intermediate layers already leads to an almost quadratic expressive efficiency, which in large-scale settings typically makes the difference between a model that is practical and one that is not.

An experiment on TIMIT speech corpus (Garofolo et al. (1993) ) evaluates the dilated convolutional network architectures covered by our analysis. We find that interconnecting intermediate layers of different networks improves accuracy, with no additional cost in terms of computation or model capacity. This serves as an indication that with the architectural feature of connectivity, similarly to the case of depth, expressive efficiency and improved accuracies go hand in hand. Accordingly, we believe expressive efficiency may serve a key role in developing new tools for deep network design.

2. SUMMARY OF OUR ANALYSIS AND CONTRIBUTIONS:

For the convenience of the reader, we summarize below the analysis and contributions of this paper. The summarized material is delivered fully in sec. 3, 4, 5 and the appendices referenced therein. To keep the manuscript at reasonable length, much of the material is located in the appendices. We refer the reader to Cohen et al. (2017) for a longer, self-contained version of the text.

Our analysis begins in sec. 3, where we present the dilated convolutional network underlying WaveNet (fig. 1 ). We consider this to be the baseline architecture and, following Cohen and Shashua (2016) , facilitate its study through tensor analysis. The key to introducing tensors into the framework is a discretization of the network's input-output mapping. Namely, f (x[t-N +1], . . . , x[t]) -a function realized by the network (t here stands for a natural time index), is conceptually evaluated on a finite (exponentially large) number of input points, generated from all possible assignments of the variables x[t-N +1], . . . , x[t] to each hold one of M predetermined values. This gives rise to an N -dimensional lookup table, with length M in each axis. We refer to this lookup table as a grid tensor (eq. 1). It is shown (app. C) that grid tensors brought forth by the baseline dilated convolutional network (fig. 1 ) can be expressed as a hierarchical tensor decomposition, referred to as the baseline decomposition (eq. 2).

The baseline decomposition implicitly adheres to a particular tree over tensor modes (axes). This calls for a generalization, and we indeed define a general mode tree (def. 1), followed by a corresponding hierarchical tensor decomposition, referred to as the tree decomposition (eq. 3). Different choices of mode trees lead to tree decompositions characterizing networks with different dilations. We focus on the tree that corresponds to the baseline network (fig. 2 Armed with a framework for representing different dilated convolutional networks through hierarchical tensor decompositions of different mode trees, we head on in sec. 4 and introduce the notion of a mixed tensor decomposition (eq. 4). The mixed decomposition of two mode trees T and T is based on a preselected set of nodes present in both trees, referred to as mixture nodes. Individual tree decompositions of T and T are run in parallel, where at each mixture node, tensors from the two decompositions are swapped. If N and N are the dilated convolutional networks characterized by T and T (respectively), the mixed decomposition characterizes a mixed (interconnected) network M, formed by rewiring intermediate layers of N into N , and vice versa (see illustration in fig. 3 ).

-2 conv: dilation-1 size-2 conv: dilation-2 size-2 conv: dilation-2 L-1 Time t-2 L +1 t+1 L-1 hidden layers N:=2 L time points input output 0 r  1 r  2 r  1 L r   L r  t t-1 t-2 t-3 t-2 L +2 t-2 L     1 1, ,I 1, ,II [ ] , [ 1] , , [ ] h t g t t      a x a x       1 1 ,y,I 1 , ,II [ ] , [ 2 ] , , [ ] L L L L L y y o t g t t      a h a h         2 1 1 2, ,I 2, ,II [ ] , [ 2] , , [ ] h t g t t      a h a h

The heart of our analysis is sec. 5, where we study the expressive efficiency of the mixed network M over the individual networks N and N . Establishing expressive efficiency requires showing that any function realized by N or N can be realized by M with no more than linear growth in size, whereas the converse does not hold, i.e. there exist functions realizable by M that cannot be realized by N or N unless their size is allowed to grow super-linearly. From a tensor decomposition perspective, this translates to the following two propositions:

(i) any tensor generated by a tree decomposition of T or T can be realized by their mixed decomposition with no more than linear growth in size; (ii) there exist tensors realizable by the mixed decomposition of T and T that cannot be realized by their individual tree decompositions without a super-linear growth in size.

We address both propositions through the notion of hybrid mode trees (def. 2; fig. 4 ), which are simply mode trees born from combinations of T and T . We prove (claim 1) that the mixed decomposition of T and T can replicate, with no more than linear growth in size, the tree decomposition of any hybrid tree H. Since T and T are in particular hybrid mode trees of themselves, we obtain an affirmative answer to proposition (i). For addressing proposition (ii), we demonstrate a case (with convolutional arithmetic circuits) where there exists a hybrid tree H whose tree decomposition generates tensors that require the tree decompositions of T and T to grow super-linearly. Since the mixed decomposition of T and T can (by claim 1) replicate the tree decomposition of H with no more than linear growth, proposition (ii) is established, and M is indeed expressively efficient w.r.t. N and N (corollary 1).

The central tool for establishing proposition (ii), or more specifically, for demonstrating the existence of a hybrid tree H whose tree decomposition requires those of T and T to grow super-linearly, is a tight analysis of tensors generated by a tree decomposition in terms of their ranks when arranged as matrices (theorem 1). Matricization ranks under hierarchical tensor decompositions are of interest from a pure tensor analysis perspective (cf. Hackbusch (2012) ), as well as in the context of deep learning (cf. Cohen and Shashua (2017) ). The bounds we provide are much tighter (exact in many cases) and far more general than those existing in the literature, and we expect them to prove useful in different applications. The key idea in deriving these bounds is to consider a matricized form of the tree decomposition, and recursively propagate outwards various matrices (for details see proof of theorem 1 in app. E.2). To conclude this section, we list below the main contributions of the paper:

• We introduce the notion of a mixed tensor decomposition, and prove that it brings forth a representational advantage compared to the individual hierarchical decompositions it comprises. This development is of interest from a pure tensor analysis perspective, independently of convolutional networks, or machine learning in general.

• We provide the first formal evidence for the fact that interconnectivity -an architectural feature prevalent in state of the art deep learning, brings forth expressive efficiency.

• Our central theorem (theorem 1) provides the most comprehensive characterization to date of matricization ranks brought forth by hierarchical tensor decompositions. We study the functions {f y (•)} y , which obviously depend on the convolution weights {a l,γ,I , a l,γ,II } l,γ , through the process of discretization. Namely, we choose a collection of vectors v (1) . . . v (M ) , and for each output coordinate y, define the following tensor:

3. DILATED CONVOLUTIONAL NETWORKS:

EQUATION

v (1) . . . v (M ) are referred to as discretizers, and A y is referred to as the grid tensor of f y (•). The size of a grid tensor is exponential in N , thus treating it directly is intractable. However, the network admits a compact parameterization of grid tensors in terms of its convolution weights (see app. C, and the preliminaries in app. A):

For j = 1. . .N :

φ 0,j,γ = [v (1) γ , . . . , v (M ) γ ] ∀γ ∈ [r0]

For l = 1. . .L , j = 1. . .N/2 l :

EQUATION

This parameterization is in fact a hierarchical tensor decomposition. To highlight its correspondence to the baseline dilated convolutional network (fig. 1 ), we refer to it as the baseline decomposition.

3.2. DILATIONS AND MODE TREES:

The baseline decomposition (eq. 2), corresponding to the baseline dilated convolutional network (fig. 1 ), implicitly adheres to a tree structure 1 In this subsection we generalize the underlying tree, and show that the resulting decompositions capture networks with various dilations throughout their convolutional layers. We begin by defining a general (binary) tree over tensor modes:

Definition 1. Let N ∈ N.

A binary mode tree 2 over [N ] is a full binary tree 3 in which:

• Every node is labeled by a subset of [N ]

• There are exactly N leaves, labeled {1} . . . {N } • The label of an interior (non-leaf) node is the union of the labels of its children If T is a binary mode tree, we identify its nodes with their labels, i.e. with the corresponding subsets of [N ] . The set of all interior nodes is denoted by int(T ) ⊂ 2 [N ] ; the children of an interior node ν ⊂ [N ] are denoted by C I (ν; T ), C II (ν; T ) ⊂ [N ]; and the parent of a non-root node ν ⊂ [N ] is denoted by P (ν; T ). Notice that by definition, the root node is labeled [N ] .

Recall the definition of grid tensors {A y } y (eq. 1), and let T be a binary mode tree over [N ]. T induces a hierarchical decomposition of the grid tensors, referred to as its tree decomposition:

For j = 1. . .N : (1) γ , . . . , v (M ) γ ] ∀γ ∈ [r] For ν in int(T ) (depth-first order):

φ {j},γ = [v

EQUATION

To conserve space we defer the annotation of the tree decomposition to app. D, noting that r∈N -the number of tensors in each group {φ ν,γ } γ , is referred to as the size constant of the decomposition. 4 Compare the general tree decomposition (eq. 3) to the baseline decomposition (eq. 2). It is not difficult to see that the latter is a special case of the former, corresponding to a binary mode tree T that is perfect, 5 and whose depth-l nodes are adjacent sets of size N/2 l (fig. 2 (a)-right). This implies that such a mode tree, when plugged into the tree decomposition, provides a characterization of the baseline dilated convolutional network (fig. 1 ), i.e. a network whose dilation in layer l is 2 l-1 (fig. 2 (a)-left). If we were to choose a different mode tree, the corresponding dilated convolutional network would change. 6 For example, if we swap connections in the mode tree (fig. 2 

4. MIXED TENSOR DECOMPOSITIONS:

Let T and T be two binary mode trees over [N ] (def. 1). We will now define mixed tensor decompositions, blending together the tree decompositions of T and T (eq. 3). A mixed decomposition of T and T is obtained by choosing a collection of mixture nodes mix(T, T ). These are nodes (subsets of [N ] ) that reside in the interior of both T and T , defining locations in the tree decompositions at which tensors will be exchanged. If mix(T, T ) is chosen as the empty set, the mixed decomposition simply sums the output tensors generated by the tree decompositions of T and T . Otherwise, the tree decompositions of T and T progress in parallel, until reaching a mixture node µ∈mix(T, T ), where they exchange tensors between them. The process continues until all mixture nodes are visited and the root node (of both trees) 1 : For j = 1. . .N :

2 : φ {j},γ = φ{j},γ = [v (1) γ , . . . , v (M ) γ ] ∀γ∈[r] r -decomposition size constant 3 : For µ in mix(T, T ) ∪ {[N ]} (inclusion order): 4 :

For ν in int(T ) ∩ 2 µ \ {nodes in T already visited} (inclusion order):

5 : φ ν,γ = σ (ν;T ) r α=1 a ν,γ,I α • φ C I (ν;T ),α ⊗g r α=1 a ν,γ,II α • φ C II (ν;T ),α ∀γ∈[r]

6. ::

For ν in int( T ) ∩ 2 µ \ {nodes in T already visited} (inclusion order):

EQUATION

Let N and N be the dilated convolutional networks whose input-output mappings are characterized by the tree decompositions of T and T (respectively). The mixed decomposition of T and T (eq. 4) characterizes the input-output mapping of a mixed dilated convolutional network, formed by summing the outputs of N and N , and interconnecting their intermediate layers. The choice of mixture nodes mix(T, T ) effectively determines the locations at which networks N and N are interconnected, where an interconnection simply wires into N outputs of a convolutional layer in N , and vice versa. For example, suppose that N , N , T and T are the networks and trees portrayed in fig. 2 . A possible choice of mixture nodes, and the resulting mixed network, are illustrated in fig. 3 .

5. EXPRESSIVE EFFICIENCY ANALYSIS:

As in sec. 4, let N and N be two dilated convolutional networks whose input-output mappings are characterized by the tree decomposition (eq. 3) with mode trees T and T respectively. Consider the mixed decomposition (eq. 4) resulting from a particular choice of mixture nodes mix(T, T ), and denote its corresponding mixed dilated convolutional network by M. We would like to show that M is expressively efficient w.r. , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 , 2, 3, 4, 5, 6, 7, 8}  {9, 10, 11, 12, 13, 14, 15, 16}   {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}   {1, 2, 3, 4, 9, 10, 11, 12}  {5, 6, 7, 8, 13, 14, 15 Proposition 1. Consider a tree decomposition (eq. 3) with underlying mode tree T or T and size constant r = r tree . This decomposition can be realized by a mixed decomposition of T and T (eq. 4) whose size constant r is linear in r tree . Proposition 2. Consider a mixed decomposition of T and T (eq. 4) with size constant r = r mix . This decomposition can generate grid tensors {A y } y that cannot be generated by tree decompositions of T or T (eq. 3) unless their size constant r is super-linear in r mix .

As a first step in treating prop. 1 and 2, we define the notion of a hybrid mode tree: Definition 2. Let T and T be binary mode trees over [N ] (def. 1), and let mix(T, T ) be a corresponding collection of mixture nodes, i.e. a set of nodes (subsets of [N ]) contained in the interior of both T and T . We say that H is a hybrid mode tree of T and T w.r.t. mix(T, T ), if it is a binary mode tree over [N ], whose interior may be generated by the following process:

int(H) = ∅ For µ in mix(T, T ) ∪ {[N ]} (inclusion order): S = int(T ) ∩ 2 µ \ {nodes in T already assigned to S} S = int( T ) ∩ 2 µ \ {nodes in T already assigned to S} int(H) = int(H)∪S or int(H) = int(H)∪ S

In words, for every µ that is either a mixture node or the root node, int(H) includes a segment from either int(T ) or int( T ), where the segment comprises all descendants of µ from which the path to µ does not cross any other mixture node (see illustration in fig. 4 ).

Claim 1 below states that with proper weight setting, a mixed decomposition of T and T (eq. 4) with size constant r=r mix , can realize any tree decomposition (eq. 3) with size constant r=r mix /2, if the underlying mode tree is a hybrid of T and T . Since T and T are in particular hybrid mode trees of themselves, we obtain an affirmative answer to prop. 1. Claim 1 (proof in app. E.1). Let T and T be binary mode trees over [N ] (def. 1), and let mix(T, T ) be a corresponding collection of mixture nodes. Consider a mixed decomposition of T and T w.r.t. mix(T, T ) (eq. 4), and denote its size constant r by r mix . Let H be a hybrid mode tree of T and T w.r.t. mix(T, T ) (def. 2), and consider the respective tree decomposition (eq. 3), with size constant r=r mix /2. For any setting of weights {a ν,γ,I , a ν,γ,II } ν,γ leading to grid tensors {A y } y in this tree decomposition, there exists a setting of weights {a ν,γ,I , a ν,γ,II } ν,γ , {ā ν,γ,I , āν,γ,II } ν,γ in the mixed decomposition, independent of discretizers {v (i) } i∈ [M ] , that leads to the same grid tensors. 8 Claim 1 not only addresses prop. 1, but also brings forth a strategy for treating prop. 2. The strategy is to find a hybrid mode tree H distinct enough from T and T such that its tree decomposition, which according to claim 1 is easily realized by the mixed decomposition, poses a significant challenge for the individual tree decompositions of T and T . Hereinafter we pursue this line of reasoning, focusing on the particular case of convolutional arithmetic circuits -g(a, b)=a•b. We focus on this special case since it allows the use of a plurality of algebraic tools for theoretical analysis, while at the same time corresponding to models showing promising results in practice (see for example Cohen et al. (2016a) ; Sharir et al. (2016) ). 9

To crisply phrase our central theorem, we define the notion of an index set tiled by a mode tree: Definition 3. Let T be a binary mode tree over [N ] (def. 1), and let I ⊂ [N ] be a non-empty set of indexes. A tiling of I by T is a collection of nodes in the tree, denoted Θ(I; T ), which meets the following two requirements: (i) ∪ ν∈Θ(I;T ) ν = I (ii) ν∈Θ(I; T )⇒P (ν; T ) ⊂I. In words, Θ(I; T ) is a set of nodes in T whose disjoint union gives I, where each node is maximal, i.e. its parent in the tree is not a subset of I. See illustration in fig. 6 (supplementary material).

Theorem 1 below provides a tight characterization of grid tensors generated by a tree decomposition in terms of their ranks when matricized (see app. A) w.r.t. an index set. This result is of general interest from both tensor analysis and deep learning perspectives. We use it to establish prop. 2. Theorem 1 (proof in app. E.2). Let T be a binary mode tree over [N ] (def. 1), and consider the corresponding tree decomposition (eq. 3) with discretizers v (1) . . . v (M ) spanning R r . Assume that g(a, b)=a•b (non-generalized decomposition -see app. A), and suppose the generated grid tensors {A y } y are matricized (see app. A) w.r.t. an index set I⊂[N ], ∅ =I =[N ], whose complement we denote by I c :=[N ]\I. Then, the ranks of the grid tensor matricizations { A y I } y are: • no greater than r min{|Θ(I;T )|,|Θ(I c ;T )|} • at least r |{(ν1,ν2)∈Θ(I;T )×Θ(I c ;T ): ν1 and ν2 are siblings in T with depth>1}| almost always, i.e. for all configurations of weights {a ν,γ,I , a ν,γ,II } ν,γ but a set of Lebesgue measure zero

Given two mode trees T and T , with a corresponding collection of mixture nodes mix(T, T ), the bounds in theorem 1 can be used to find an index set I and a hybrid mode tree H, such that the tree decomposition of H generates grid tensors whose ranks under matricization w.r.t. I are much higher than those brought forth by the tree decompositions of T and T . This fulfills the strategy described above, thereby establishing prop. 2. In app. F we demonstrate this process with the exemplar setting considered throughout the paper (fig. 2, 3, 4 ). The following corollary is reached: Corollary 1. Let N be the baseline dilated convolutional network (fig. 1 ), and let N be a network obtained by swapping dilations of groups of k layers (the case k=2 is illustrated in fig. 2 (b)-left). Denote by M the mixed network obtained by summing the outputs of N and N , while interconnecting their k'th intermediate layer (and possibly additional layers). Assume the networks' convolutional operator g(•) is a product. Then, besides a negligible set, all functions realized by M with r channels in the layers of each interconnected network, cannot be realized by N (or N ) if the number of channels in each of its layers is less than (r/2) 2/(1+2 1-k ) .

Corollary 1 (along with claim 1) demonstrates that interconnecting intermediate layers of different dilated convolutional networks can bring forth expressive efficiency. The lower bound in the corollary -(r/2) 2/(1+2 1-k ) , is essentially quadratic when k ≥ 4. For example, if k = 4 and the number of channels r in each interconnected network is 128, the lower bound implies that in order to maintain representational abilities with an individual network, over 1500 channels in each layer are required -far beyond acceptable practice in deep learning.

6. EXPERIMENT:

To assess the practical implications of the expressive efficiency brought forth by mixing dilated convolutional networks, a simple experiment was conducted. We trained a baseline dilated convolutional network N (dilation 2 l-1 in layer l -see sec. 3.1) with architectural parameters similar to those used in WaveNet (van den Oord et al. ( 2016)), to classify individual phonemes in the TIMIT acoustic speech corpus (Garofolo et al. (1993) ). In addition to the baseline model, we also trained a companion network N obtained by swapping dilations of even and odd layers. The mode trees corresponding to these networks (illustrated in fig. 2 ) -T and T , share interior nodes of even depth, thus any subset of those nodes may serve as mixture nodes for a mixed decomposition (eq. 4). We evaluate mixed dilated convolutional networks M corresponding to different choices of mixture nodes (see fig. 3 for illustration of a particular case). Specifically, we consider choices of the following form: mix(T, T ) := {ν ∈ int(T )∩int( T ) : depth of ν (in T and T ) ≥ threshold}. Varying the threshold yields mixed networks with a varying number of interconnections. In the extreme case mix(T, T ) = ∅ (high threshold), M simply sums the outputs of N and N . As the threshold decreases interconnections between hidden layers are added -starting from hidden layer 2, then including hidden layer 4, and so on. The intuition from our analysis (sec. 5) is that additional interconnections result in a larger ensemble of hybrid mode trees, which in turn boosts the expressive power of the mixed network M. As fig. 5 shows, this intuition indeed complies with the results in practice -classification accuracy improves as we increase the number of interconnections, without any additional cost in terms of computation or model capacity. 10 It is important to stress that our objective in the experiment was to evaluate, in the most controlled setting possible, the exact models covered by our analysis. We did not compare to state of the art results, as all phoneme recognition rates reported in the literature deviate from our basic settingthey heavily rely on data pre-processing (e.g. Mel-Frequency Cepstral Coefficients), prediction postprocessing (e.g. Conditional Random Fields), or both. The recent DeepLab model (Chen et al. (2016) ) has demonstrated that when combined with other techniques, mixing dilated convolutions can lead to state of the art image segmentation performance. We are currently pursuing similar results in the context of sequence processing tasks.

To conclude this section, we briefly convey implementation details behind the experiment. TIMIT dataset is an acoustic-phonetic corpus comprising 6300 sentences manually labeled at the phoneme level. We split the data into train and validation sets in accordance with Halberstadt (1998), and as advised by Lee and Hon (1989) , mapped the 61 possible phoneme labels into 39 plus an additional "garbage" label. The task was then to classify individual phonemes into one of the latter categories. In accordance with WaveNet, the baseline dilated convolutional network had ReLU activation (g(a, b)= max{a+b, 0} -see sec. 3.1), 11 32 channels per layer, and input vectors of dimension 256 holding one-hot quantizations of the audio signal. The number of layers L was set to 12, corresponding to an input window of N =2 L =4096 samples, spanning 250ms of audio signalstandard practice with TIMIT dataset. The framework chosen for running the experiment was Caffe toolbox (Jia et al. (2014) ), and we used Adam optimizer (Kingma and Ba (2014) ) for training (with default hyper-parameters: moment decay rates β 1 = 0.9, β 2 = 0.999; learning rate α = 0.001).

Weight decay and batch size were set to 10 -5 and 128 respectively. Models were trained for 35000 iterations, with learning rate decreased by a factor of 10 after 80% of iterations took place.

7. CONCLUSION:

Nearly all state of the art deep networks these days (e.g. Szegedy et al. (2015) ; He et al. (2015) ; Huang et al. (2016b; a) ) deviate from the simple feed-forward (chain) approach, employing various connectivity schemes between their layers. In this paper we studied the representational implications of connectivity in the context of dilated convolutional networks, a family of deep models delivering state of the art performance in audio and text processing tasks, underlying Google's WaveNet (van den Oord et al. ( 2016)) and ByteNet (Kalchbrenner et al. (2016) ). We formulated our study through the notion of expressive efficiency, which refers to a situation where one network must grow unfeasibly large to realize (or approximate) functions of another. Our analysis shows that interconnecting hidden layers of different dilated convolutional networks can bring forth a model that is expressively efficient w.r.t. the individual networks it comprises. In particular, we show that a single connection between hidden layers can already lead to an almost quadratic gap, which in large-scale settings typically makes the difference between a model that is practical and one that is not. We empirically evaluate the analyzed networks, and find that the expressive efficiency brought forth by interconnectivity coincides with improved accuracies.

To date, formal analyses studying expressive efficiency have focused on the architectural feature of depth, showing instances where deep networks are expressively efficient w.r.t. shallow ones. These studies were motivated by the vast empirical evidence supporting the importance of depth. Our work thus provides a second exemplar of an architectural feature for which expressive efficiency and superior accuracies go hand in hand. This leads us to believe that expressive efficiency may serve a key role in the development of new tools for deep network design.

NOTES:

1 For every (l, j), there exists a group of tensors {φ l,j,γ }γ, formed through combinations of tensors from its "child" groups {φ l-1,2j-1,γ }γ and {φ l-1,2j,γ }γ.

2 Binary mode trees lead to decompositions (eq. 3) that correspond to networks with size-2 convolutions.

We limit ourselves to this case for simplicity of presentation. Our formulation can easily be extended to account for convolutions of arbitrary size by considering mode trees that are not necessarily binary, and by modifying the decomposition in eq. 3 to take (generalized) tensor products between an arbitrary number of tensors (not necessarily two).

3 A full binary tree is a tree in which all interior (non-leaf) nodes have exactly two children.

4 In general the number of tensors in the group {φ ν,γ }γ may vary across nodes ν, but for simplicity of presentation we assume that all groups comprise exactly r tensors.

5 A perfect binary tree is a tree in which all interior (non-leaf) nodes have exactly two children and all leaves have exactly the same depth.

6 It is important to stress that not all choices of mode trees lead to networks resembling ones used in practice.

For example, if different leaves in a tree have different depths, different inputs in the corresponding network pass through a different number of layers. Conversely, not every type of dilated convolutional network used in practice corresponds to a mode tree -only ones in which an input is connected to the output through a single path.

7 A few remarks are in order at this point:

• The number of channels in each layer of N or N corresponds to the constant r in the respective tree decomposition (eq. 3 with underlying mode tree T or T respectively). Similarly, the number of channels in each layer of each interconnected network in M corresponds to r in the respective mixed decomposition (eq. 4). In both the tree and mixed decompositions, r, referred to as the size constant, stands for the number of tensors {φ ν,γ }γ (respectively { φν,γ }γ) held in each node ν (respectively ν).

We set this number uniformly across nodes, corresponding to uniformly sized layers across networks, merely for simplicity of presentation. Our formulations and analysis can easily be adapted to account for varying layer sizes, by allowing different nodes in a decomposition to hold a different number of tensors. Note that an implication of our uniform setting is that a network's input and output dimensions vary along with the size of its hidden layers. When replicating a function realized by a network using a larger network, we simply pad input vectors with zeros, and ignore the excess output coordinates.

• An additional simplification we made relates to weight sharing. In both the tree and mixed decompositions, each interior node ν (respectively ν) has a separate set of weights {a ν,γ,I , a ν,γ,II }γ (respectively {ā ν,γ,I , āν,γ,II }γ). This implies that in the corresponding networks, convolution filters may vary through time, i.e. different weights may be used against different portions of a convolved sequence. The more commonplace setting of stationary filters (standard convolutions) is obtained by restricting different nodes in a decomposition to possess the same weights. We do not introduce such restrictions into our formulations, as they make little difference in terms of the analysis, but on the other hand significantly burden presentation.

8 In accordance with the remark given at the beginning of this section, when using the (larger) mixed decomposition, we pad discretizers with zeros, and ignore the excess output tensors.

9 Treatment of additional cases can be achieved by deriving a result analogous to theorem 1, i.e. by characterizing matricization ranks brought forth by a tree decomposition (eq. 3) whose underlying operator g(•) corresponds to the architecture of interest (e.g. g(a, b) = max{a + b, 0} for networks with ReLU activation). Results along this line were established in Cohen and Shashua (2016) {9,10,11,12,13,14,15,16} {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 

A PRELIMINARIES:

The constructions and analyses delivered in this paper rely on concepts from the field of tensor analysis. Below we provide the minimal background required in order to follow our arguments. 1The core concept in tensor analysis is a tensor, which for our purposes may simply be thought of as a multi-dimensional array. The order of a tensor is defined to be the number of indexing entries in the array, which are referred to as modes. The dimension of a tensor in a particular mode is defined as the number of values that may be taken by the index in that mode. For example, a 4-by-3 matrix is a tensor of order 2, i.e. it has two modes, with dimension 4 in mode 1 and dimension 3 in mode 2. If A is a tensor of order N and dimension M i in each mode i ∈ {1, . . . , N }, the space of all configurations it can take is denoted, quite naturally, by

R M1×•••×M N .

A fundamental operator in tensor analysis is the tensor product (also known as outer product), which we denote by ⊗. It is an operator that intakes two tensors A ∈ R M1×•••×M P and B ∈ R M P +1 ×•••×M P +Q (orders P and Q respectively), and returns a tensor A ⊗ B ∈ R M1×•••×M P +Q (order P +Q) defined by: (A⊗B) d1...d P +Q = A d1...d P •B d P +1 ...d P +Q . In Cohen and Shashua (2016) a generalization of the tensor product is defined, by replacing multiplication with a general operator g(•). Specifically, for a function g : R × R → R that is commutative (g(a, b) = g(b, a) for all a, b ∈ R), the generalized tensor product, denoted ⊗ g , is defined to be the operator that for input tensors A ∈ R M1×•••×M P and B ∈ R M P +1 ×•••×M P +Q (orders P and Q respectively), returns the tensor A ⊗ g B ∈ R M1×•••×M P +Q (order P + Q) given by: (A ⊗ g B) d1...d P +Q = g(A d1...d P , B d P +1 ...d P +Q ).

An additional operator we make use of is mode permutation. Let A be a tensor of order N , and let σ(•) be a permutation over N (bijective mapping from {1, . . . , N } to itself). The mode permutation of A w.r.t. σ(•), which by a slight abuse of notation is denoted σ(A), is the order-N tensor defined by: σ(A) d1...d N = A d σ(1) ...d σ(N ) . In words, σ(A) is the tensor obtained by rearranging the modes of A in accordance with σ(•).

When studying tensors, it is oftentimes useful to arrange them as matrices, a procedure referred to as matricization. Let A be a tensor of order N and dimension M i in each mode i ∈ {1, . . . , N }, and let I ⊂ {1, . . . , N } be a set of mode indexes, whose complement {1, . . . , N } \ I we denote by I c . We may write I = {i 1 , . . . , i |I| } where i 1 < • • • < i |I| , and similarly

I c = {j 1 , . . . , j |I c | } where j 1 < • • • < j |I c | . The matricization of A w.r.t. I, denoted A I , is the |I| t=1 M it -by- |I c | t=1 M jt matrix holding the entries of A such that A d1...d N is placed in row index 1 + |I| t=1 (d it -1) |I| t =t+1 M i t and column index 1 + |I c | t=1 (d jt -1) |I c | t =t+1 M j t . If I = ∅ or I = {1, . . . , N }, then by definition A I is a row or column (respectively) vector of dimension N t=1 M t holding A d1...d N in entry 1 + N t=1 (d t -1) N t =t+1 M t .

To conclude this appendix, we hereinafter list notational conventions used throughout the paper. We denote tensors with uppercase calligraphic letters, e.g. A, and in some cases, with the Greek letters φ, ϕ or ψ. Subscripts are used to refer to individual tensor entries, e.g. A d1...d N ∈ R, whereas superscripts indicate the location of a tensor in some annotated collection, for example A y stands for the y'th tensor in the collection A 1 . . . A r . Vectors are typically denoted with boldface lowercase letters, e.g. a, where again subscripts refer to an individual entry (e.g. a α ∈ R), and superscripts to the identity of a vector within some annotated collection (e.g. a l,j is the (l, j)'th vector in the set {a l,j } l=1...L,j=1...N ). We use non-boldface lowercase or uppercase letters (e.g. l or L) to denote scalars, and in this case, both subscripts and superscripts distinguish between objects in an annotated set (e.g. l i , l i , L i , L i ∈ R). Finally, for a positive integer N ∈ N, we use [N ] as shorthand for the set {1, . . . , N }.

B DETAILED DESCRIPTION OF THE BASELINE ARCHITECTURE:

In this appendix we describe in detail the architecture of the baseline dilated convolutional network (fig. 1 ). The input to the network is a sequence of vectors (x[t]) t ⊂ R r0 , where t is a natural time index. A size-2 convolutional layer with dilation-1, i.e. with contiguous filters, maps this input into the hidden sequence (h (1) [t]) t ⊂ R r1 . Specifically, entry γ ∈ [r 1 ] of h (1) [t] is obtained by applying the filter formed by a 1,γ,I , a 1,γ,II ∈ R r0 to time points t-1, t of the input: h (1) [t] γ = g( a 1,γ,I , x[t-1] , a 1,γ,II , x[t] ). We use g(•) here to denote the binary function combining two size-1 convolutions into a single size-2 convolution with non-linearity. Different choices of g(•) lead to different convolutional operators, for example g(a, b) := max{a + b, 0} leads to standard convolution followed by rectified linear activation (ReLU, Nair and Hinton (2010) ), whereas g(a, b) = a•b gives rise to what is known as a convolutional arithmetic circuit (Cohen et al. (2016b) ). Following the first hidden layer, L-1 size-2 convolutional layers with increasing dilations are applied. Specifically, for l = 2, . . ., L-1, hidden layer l maps the sequence (h (l-1) [t]) t ⊂ R r l-1 into (h (l) [t]) t ⊂ R r l using filters with dilation-2 l-1 , i.e. with an internal temporal gap of 2 l-1 -1 points:

h (l) [t] γ = g( a l,γ,I , h (l-1) [t-2 l-1 ] , a l,γ,II , h (l-1) [t] ). The last convolutional layer maps (h (L-1) [t]) t into network output sequence (o[t]) t ⊂ R r L using filters with dilation-2 L-1 : o[t] y = g( a L,y,I , h (L-1) [t-2 L-1 ] , a L,y,II , h (L-1) [t] ).

Altogether, the architectural parameters of the network are the number of convolutional layers L, the convolutional operator g(•), the input dimension r 0 , the number of channels r l for each hidden layer l ∈ [L-1], and the output dimension r L . The learnable parameters are the convolution weights a l,γ,I , a l,γ,II ∈ R r l-1 for channel γ ∈ [r l ] of layer l ∈ [L].

C DERIVATION OF THE BASELINE DECOMPOSITION:

In this appendix we derive the baseline decomposition (eq. 2) -a parameterization of grid tensors (eq. 1) discretizing input-output mappings of the baseline dilated convolutional network (fig. 1 ; app. B). As discussed in sec. 3.1, o[t] -the network output at time t, is a function of x[t-N +1] . . . x[t] -its input over the last N := 2 L time points. We would like to show that for any d 1 . . .d N ∈ [M ], entry (d 1 , . . . , d N ) of a tensor A y generated by eq. 2, is equal to coordinate y of network output o[t] under the following input assignment:

x[t-N +1] = v (d1) , . . . , x[t] = v (d N ) .

To achieve this, we prove by induction that under the latter assignment, for every l ∈ , d (j-1 )2 l +2 l ) of the tensor φ l,j,γ in the baseline decomposition (eq. 2). The desired result then follows from the case l = L, j = 1, γ = y.

[L] ∪ {0}, j ∈ [N/2 l ] and γ ∈ [r l ], coordinate γ of the network's depth-l sequence (input (x[t]) t for l = 0; hidden sequence (h (l) [t]) t for l ∈ [L -1]; output (o[t]) t for l = L) at time t -N + j•2 l , is equal to entry (d (j-1)2 l +1 , . . .

When l = 0, the inductive hypothesis is trivial -coordinate γ of the input sequence at time t-N +j, i.e. x[t -N + j] γ , is by definition of our assignment equal to v (dj ) γ -entry d j of the tensor φ 0,j,γ (see eq. 2). Assume now that the inductive hypothesis holds whenever l = k, and consider the tensor φ k+1,j,γ for some j ∈ [N/2 k+1 ] and γ ∈ [r k+1 ]. From the baseline decomposition (eq. 2):

φ k+1,j,γ = r k α=1 a k+1,γ,I α • φ k,2j-1,α ⊗ g r k α=1 a k+1,γ,II α • φ k,2j,α

Focusing on entry (d (j-1)2 k+1 +1 , . . . , d (j-1)2 k+1 +2 k+1 ) of the left-hand side, while recalling the definition of the generalized tensor product ⊗ g (app. A), we may write:

φ k+1,j,γ d (j-1)2 k+1 +1 ,...,d (j-1)2 k+1 +2 k+1 = g r k α=1 a k+1,γ,I α • φ k,2j-1,α d (2j-2)2 k +1 ,...,d (2j-2)2 k +2 k , r k α=1 a k+1,γ,II α • φ k,2j,α d (2j-1)2 k +1 ,...,d (2j-1)2 k +2 k (5)

By our inductive assumption:

φ k,2j-1,α d (2j-2)2 k +1 ,...,d (2j-2)2 k +2 k = h (k) [t -N + (2j -1)•2 k ] α ∀α ∈ [r k ] φ k,2j,α d (2j-1)2 k +1 ,...,d (2j-1)2 k +2 k = h (k) [t -N + 2j•2 k ] α ∀α ∈ [r k ]

where we overload notation in the case k = 0, letting (h (0) [t]) t stand for the input sequence (x[t]) t .

Plugging the latter into eq. 5, we obtain:

φ k+1,j,γ d (j-1)2 k+1 +1 ,...,d (j-1)2 k+1 +2 k+1 = g a k+1,γ,I , h (k) [t -N + (2j -1)•2 k ] , a k+1,γ,II , h (k) [t -N + 2j•2 k ]

By the definition of the baseline dilated convolutional network (fig. 1 ; app. B), the latter expression is precisely equal to coordinate γ of the sequence

(h (k+1) [t]) t (or (o[t]) t if k = L -1) at time t - N + j•2 k+1

. This proves that our inductive hypothesis holds when l = k + 1, and in general.

D ANNOTATIONS OF THE TREE AND MIXED DECOMPOSITIONS:

In this appendix we describe the tree and mixed decompositions (eq. 3 and 4 respectively), whose annotations were omitted from the text due to lack of space.

Let T be a binary mode tree over [N ] (def. 1). The tree decomposition of T (eq. 3) iteratively assigns a group of (2 |ν| -order) tensors {φ ν,γ } γ∈ [r] for each node ν in T , based on weight vectors {a ν,γ,I , a ν,γ,II ∈ R r } γ∈[r] defined for each interior node ν∈int(T ). Specifically, the decomposition traverses through T in a depth-first fashion, and for each node ν, assigns the tensor group {φ ν,γ } γ as follows:

• If ν is a leaf, i.e. ν={j} for some j ∈ [N ], its tensors ({φ ν,γ } γ ) are set directly by the discretizers v (1) . . .

EQUATION

γ in eq. 3 stands for coordinate γ of v (i) ). • If ν is an interior node, i.e. ν∈int(T ), its tensors are set through combinations of the tensors of its children ({φ CI(ν;T ),γ } γ and {φ CII(ν;T ),γ } γ ). These combinations are based on the weight vectors {a ν,γ,I } γ and {a ν,γ,II } γ , as depicted in eq. 3 (a ν,γ,I α and a ν,γ,II α there stand for coordinate α of a ν,γ,I and a ν,γ,II respectively). The permutation σ (ν;T ) (•) in the assignment of φ ν,γ arranges the modes of the tensor (see app. A) such that these comply with a sorted ordering of ν. Namely, if we denote by i

1 < • • • <i |CI(ν;T )| the elements of C I (ν; T )⊂[N ], and by j 1 < • • • <j |CII(ν;T )| the elements of C II (ν; T )⊂[N ], the permutation σ (ν;T ) : [2 |ν| ] → [2 |ν| ]

is the one that sorts the tuple (i 1 , . . . , i |CI(ν;T )| , j 1 , . . . , j |CII(ν;T )| ) in ascending order. The final outcome of the tree decomposition, i.e. the generated grid tensors {A y } y , are precisely the tensor group {φ [N ],γ } γ corresponding to the root of T ([N ]).

Heading on to the mixed decomposition (eq. 4), let T be an additional binary mode tree over [N ] (def. 1). When considering the tree decomposition of T , we use { φν,γ } γ∈[r] to denote the tensor group of node ν∈ T , and {ā ν,γ,I , āν,γ,II } γ∈ [r] to denote the weights of interior node ν∈int( T ). For a chosen collection of mixture nodes mix(T, T )⊂int(T )∩int( T ), the mixed decomposition of T and T blends together their tree decompositions by running these in parallel, while exchanging tensors whenever a mixture node is reached. The procedure is formulated in eq. 4 -annotation follows:

• As in the basic tree decomposition (eq. 3), the first step (lines 1-2) is to assign tensors corresponding to the leaf nodes ({1} . . . {N }) via discretizers v (1) . . . v (M ) . • The outer loop in line 3 traverses µ through mixture nodes and the root node in inclusion order, i.e. such that a node (subset of [N ]) is always reached after all nodes strictly contained in it. • Lines 4-5 (respectively 6-7) are the same as in the tree decomposition (eq. 3), except that instead of running through the entire interior of T (respectively T ), they cover a segment of it. This segment continues where the previous ones left off, and comprises only nodes (subsets of [N ]) contained in µ (including µ itself).

• Line 8 is where the mixing takes place -here half the tensors corresponding to node µ in the decomposition of T ({φ µ,γ } γ ), are exchanged for half the tensors corresponding to µ in the decomposition of T ({ φµ,γ } γ ).

• Finally, after µ has reached the root node [N ] and the decompositions of T and T have concluded, line 9 sums the output tensors of these decompositions ({φ [N ],y } y and { φ[N],y } y respectively), producing the grid tensors {A y } y .

E DEFERRED PROOFS E.1 PROOF OF CLAIM 1:

We initiate the proof by introducing notations that will allow a more compact presentation. Hereinafter, we let {a H,ν,γ,I , a H,ν,γ,II ∈ R rmix/2 } ν∈int(H),γ∈[rmix/2] stand for the weights in the tree decomposition of the hybrid mode tree H (eq. 3 with size constant r = r mix /2 and underlying mode tree given by def. 2). Similarly, we use {a T,ν,γ,I , a T,ν,γ,II ∈ R rmix } ν∈int(T ),γ∈[rmix] and {a T ,ν,γ,I , a T ,ν,γ,II ∈ R rmix } ν∈int( T ),γ∈ [rmix] to denote the weights, corresponding to T and T (respectively), in the mixed decomposition (eq. 4 with size constant r = r mix ). Recall that by construction (def. 2), int(H) -the interior of H, consists of different segments (collections of nodes), each taken from either int(T ) or int( T ). We define t : int(H) → {T, T } to be the function indicating which tree an interior node in H came from. Specifically, if the node ν∈int(H) originated from T we have t(ν) = T , and on the other hand, if its source is T then t(ν) = T . By convention, feeding t(•) with an argument outside int(H) yields something that is different from both T and T . For example, if ν∈int(H) is the root node, i.e. ν = [N ], then P (ν; H) -its parent in H, is undefined and we have t(P (ν; H)) =t(ν). Similarly, if the child C I (ν; H) of ν∈int(H) is a leaf, it is outside the domain of t(•) and thus t(ν) =t(C I (ν; H)).

Given a setting of weights {a H,ν,γ,I , a H,ν,γ,II } ν,γ for the tree decomposition of H, we would like to show that there exists a setting of weights {a T,ν,γ,I , a T,ν,γ,II } ν,γ and {a T ,ν,γ,I , a T ,ν,γ,II } ν,γ for the mixed decomposition of T and T , such that the latter generates grid tensors identical to those of the former. More precisely, for any collection of discretizers {v (i) ∈ R rmix/2 } i∈[M ] fed into the tree decomposition of H, leading the latter to produce grid tensors {A y } y∈[rmix/2] , we would like the mixed decomposition to be such that when fed with the padded discretizers {[(v (i) ) 0] ∈ R rmix } i∈[M ] , the first r mix /2 grid tensors it generates are equal to {A y } y∈[rmix/2] . We prove existence of the sought after weight setting constructively, by presenting an explicit procedure for assigning {a T,ν,γ,I , a T,ν,γ,II } ν,γ and {a T ,ν,γ,I , a T ,ν,γ,II } ν,γ based on {a H,ν,γ,I , a H,ν,γ,II } ν,γ : Initialize:

a T,ν,γ,I = a T,ν,γ,II = 0 ∀ν∈int(T ), γ ∈ [r mix ] a T ,ν,γ,I = a T ,ν,γ,II = 0 ∀ν∈int( T ), γ ∈ [r mix ]

For ν in int(H) (depth-first order):

EQUATION

The idea behind this assignment is as follows. The computation corresponding to a node in the tree decomposition of H, is carried out, in the mixed decomposition of T and T , by the respective node in the respective source tree. That is to say, the computation of ν∈int(H) in the tree decomposition is carried out by ν∈int(t(ν)) in the mixed decomposition. ν∈int(t(ν)) uses half (r mix /2) of its weight vectors, and in each used weight vector, half (r mix /2) of the coordinates hold actual (nonzero) values -a copy of the respective weight from ν∈int(H). The choice of which weight vectors to use, and which coordinates to use in the active weight vectors, depends on the tree-transitioning scheme. If the parent of ν in H came from the same tree as ν, i.e. t(P (ν; H)) = t(ν), ν∈int(t(ν)) in the mixed decomposition uses weight vectors with higher indexes (γ∈r mix /2 + [r mix /2]), as these relate to tensors that are not exchanged (see eq. 4). On the other hand, if t(P (ν; H)) =t(ν), weight vectors with lower indexes (γ ∈ [r mix /2]) are used, so that the computations (tensors) will be sent to the opposite tree. The analogous rationale holds for the children of ν in H (C I (ν; H) and C II (ν; H)).

If a child came from the same tree as ν, upper coordinates of the appropriate weight vectors are used, so that computations (tensors) coming from the present tree are collected. On the other hand, if the child came from the opposite tree, lower coordinates are used and computations (tensors) from that tree are fetched. Altogether, the assignment in eq. 6 meets our requirements, and thus concludes the proof.

E.2 PROOF OF THEOREM 1 E.2.1 SKETCH The proof proceeds in three stages. In the first stage we matricize the tree decomposition of T , i.e. transform it from a tensor decomposition generating {A y } y to a matrix decomposition generating { A y I } y . In this transformation, instances of the tensor product ⊗ (⊗ g with g(a, b) = a•b -see app. A) convert to a Kronecker product . The second stage of the proof establishes the upper bound stated in the theorem, by showing that for each y, A y I is equal to a product of matrices, one of which has size r |Θ(I;T )| -by-r |Θ(I c ;T )| . The key idea in this stage is the propagation of elements out of the matrix decomposition, using the relation (AA ) (BB ) = (A A )(B B ). The third and final stage of the proof establishes the lower bound stated in the theorem. Here again, elements are propagated out of the matrix decomposition, allowing the construction of a concrete configuration of weights ({a ν,γ,I , a ν,γ,II } ν,γ ) for which the lower bound holds. The fact that the lower bound holds almost always is then a direct corollary of app. G, where it is shown that the tree decomposition admits maximal matricization ranks almost always when g(•) is the product operator.

The study of matricization ranks under hierarchical tensor decompositions is of significant interest, particularly in the context of deep learning. Cohen et al. (2016b) proved the lower bound in the theorem for the specific case where T is the mode tree corresponding to the baseline dilated convolutional network (see fig. 2(a) ), and I = {1, 3, . . . , N -1}. The result was used to establish exponential expressive efficiency of deep convolutional arithmetic circuits w.r.t. shallow ones. Cohen and Shashua (2017) later extended the analysis by deriving upper bounds for arbitrary index sets I, using them to study the ability of deep convolutional arithmetic circuits to model correlations among regions of their input. The bounds used in Cohen and Shashua (2017) were loose, and in fact trivial for many choices of index sets I. We here treat arbitrary mode trees T and index sets I, proving upper and lower bounds that are tight, oftentimes exact. Such tight bounds are necessary for identifying expressive efficiency that is not exponential, as we do in this paper. The key to deriving the bounds is the aforementioned idea of propagating elements out of a matrix decomposition. E.2.2 COMPLETE PROOF Since we are dealing with a single particular mode tree T , we omit it from our notations throughout the proof. Specifically, we denote by C I (ν) and C II (ν) (instead of C I (ν; T ) and C II (ν; T )) the children of an interior node ν∈int(T ); by Θ(I) and Θ(I c ) (instead of Θ(I; T ) and Θ(I c ; T )) the tilings of I and I c (respectively) w.r.t. T (see def. 3); and by σ (ν) (•) (instead of σ (ν;T ) (•)) the permutation corresponding to ν∈int(T ) in the tree decomposition (eq. 3).

The first stage of the proof is to derive a matricized form of the tree decomposition, shedding light into the manner in which grid tensor matricizations { A y I } y are generated. As a preparatory step in this direction, we define the notion of an index set reduction. Let ν ⊂ [N ] be a node in T , whose elements we denote by i 1 < • • • < i |ν| . The reduction of I onto ν is defined as follows:

I| ν := {j ∈ [|ν|] : i j ∈ I ∩ ν} (7)

In words, it is the set of indexes corresponding to the intersection I ∩ ν inside ν. Besides index set reduction, an additional tool we will be using is the Kronecker product -a matrix operator we denote by . For two matrices A ∈ R M1×M2 and B ∈ R N1×N2 , A B is the matrix in R M1N1×M2N2 holding A ij B kl in row index (i -1)N 1 + k and column index (j -1)N 2 + l.

Consider the central relation in the tree decomposition (eq. 3), while noticing that ⊗ g ≡ ⊗ in our setting (g(•) is the product operator -see app. A):

EQUATION

Suppose we would like to matricize the tensor φ ν,γ w.r.t. the reduction I| ν . If all elements of C I (ν) were smaller than those of C II (ν), the permutation σ (ν) (•) would be the identity (see sec. 3.2), and the following matrix relation would hold:

φ ν,γ I|ν = r α=1 a ν,γ,I α • φ CI(ν),α ⊗ r α=1 a ν,γ,II α • φ CII(ν),α I|ν = r α=1 a ν,γ,I α • φ CI(ν),α I| C I (ν) r α=1 a ν,γ,II α • φ CII(ν),α I| C II (ν) = r α=1 a ν,γ,I α • φ CI(ν),α I| C I (ν) r α=1 a ν,γ,II α • φ CII(ν),α I| C II (ν)

In general however, elements in C I (ν) could be greater than ones in C II (ν), and so eq. 8 includes a tensor mode sorting via σ (ν) (•). In matricized form, this amounts to rearranging rows and columns through appropriate permutation matrices Q (ν) and Q(ν) respectively:

φ ν,γ I|ν = Q (ν) r α=1 a ν,γ,I α • φ CI(ν),α I| C I (ν) r α=1 a ν,γ,II α • φ CII(ν),α I| C II (ν) Q(ν)

We thus arrive at the following matrix form of eq. 3, referred to as the matricized tree decomposition:

For j = 1. . .N :

φ {j},γ I| {j} = [v (1) γ , . . . , v (M ) γ ] I| {j} ∀γ ∈ [r]

For ν in int(T ) (depth-first order):

EQUATION

Next, we move on to the second stage of the proof, where we establish the upper bound stated in the theorem:

EQUATION

We begin by "propagating outwards" the permutation matrices Q ([N ]) and Q([N]) corresponding to the root node [N ] in the matricized tree decomposition (eq. 9). Namely, for every γ ∈ [r], we replace the matrix φ [N ],γ I| [N ] by:

B [N ],γ := r α=1 a [N ],γ,I α φ C I ([N ]),α I| C I ([N ]) r α=1 a [N ],γ,II α φ C II ([N ]),α I| C II ([N ])

and accordingly move Q ([N ]) and Q([N]) to the assignments of { A y I } y . This gives rise to the following decomposition:

For j = 1. . .N :

φ {j},γ I| {j} = [v (1) γ , . . . , v (M ) γ ] I| {j} ∀γ ∈ [r]

For ν in int(T ) \ {[N ]} (depth-first order):

φ ν,γ I|ν = Q (ν) r α=1 a ν,γ,I α φ C I (ν),α I| C I (ν) r α=1 a ν,γ,II α φ C II (ν),α I| C II (ν) Q(ν) ∀γ ∈ [r] B [N ],γ = r α=1 a [N ],γ,I α φ C I ([N ]),α I| C I ([N ]) r α=1 a [N ],γ,II α φ C II ([N ]),α I| C II ([N ]) ∀γ ∈ [r] A y I = Q ([N ]) B [N ],y Q([N]) ∀y ∈ [r]

Consider now C I ([N ]) -a child of the root node [N ], and suppose we would like to similarly propagate outwards its permutation matrices Q (CI([N ])) and Q(CI([N])) . We may define, for every γ∈[r]:

B C I ([N ]),γ := r α=1 a C I ([N ]),γ,I α φ C I (C I ([N ])),α I| C I (C I ([N ])) r α=1 a C I ([N ]),γ,II α φ C II (C I ([N ])),α I| C II (C I ([N ]))

which in turn implies:

B [N ],γ = r α=1 a [N ],γ,I α Q (C I ([N ])) B C I ([N ]),α Q(C I ([N ])) r α=1 a [N ],γ,II α φ C II ([N ]),α I| C II ([N ]) = Q (C I ([N ])) r α=1 a [N ],γ,I α B C I ([N ]),α Q(C I ([N ])) r α=1 a [N ],γ,II α φ C II ([N ]),α I| C II ([N ])

Now, for any matrices A, A , B, B such that AA and BB are defined, the following equality holds: (AA ) (BB ) = (A A )(B B ) (see Bellman (1970) for proof). We may therefore write:

B [N ],γ = Q (C I ([N ])) I r α=1 a [N ],γ,I α B C I ([N ]),α r α=1 a [N ],γ,II α φ C II ([N ]),α I| C II ([N ]) Q(C I ([N ])) Ī

where I and Ī are identity matrices of appropriate sizes. Propagating outwards the matrices Q (CI([N ])) I and Q(CI([N])) Ī (while redefining B [N ],γ appropriately), we arrive at the following decomposition:

For j = 1. . .N :

φ {j},γ I| {j} = [v (1) γ , . . . , v (M ) γ ] I| {j} ∀γ ∈ [r] For ν in int(T ) \ {[N ], CI([N ])} (depth-first order): φ ν,γ I|ν = Q (ν) r α=1 a ν,γ,I α φ C I (ν),α I| C I (ν) r α=1 a ν,γ,II α φ C II (ν),α I| C II (ν) Q(ν) ∀γ ∈ [r] B C I ([N ]),γ = r α=1 a C I ([N ]),γ,I α φ C I (C I ([N ])),α I| C I (C I ([N ])) r α=1 a C I ([N ]),γ,II α φ C II (C I ([N ])),α I| C II (C I ([N ])) ∀γ ∈ [r] B [N ],γ = r α=1 a [N ],γ,I α B C I ([N ]),α r α=1 a [N ],γ,II α φ C II ([N ]),α I| C II ([N ]) ∀γ ∈ [r] A y I = Q ([N ]) (Q (C I ([N ])) I) B [N ],y ( Q(C I ([N ])) Ī) Q([N]) ∀y ∈ [r]

Continuing this process, we propagate outwards the permutation matrices Q (ν) and Q(ν) of all nodes ν in the tree that are not members of the tilings Θ(I) or Θ(I c ) (see def. 3), and are not descendants of such. This brings forth the following decomposition:

For j = 1. . .N :

φ {j},γ I| {j} = [v (1) γ , . . . , v (M ) γ ] I| {j} ∀γ ∈ [r]

For ν in int(T )∩{nodes in Θ(I) or Θ(I c ) or descendants of such} (depth-first order):

φ ν,γ I|ν = Q (ν) r α=1 a ν,γ,I α φ C I (ν),α I| C I (ν) r α=1 a ν,γ,II α φ C II (ν),α I| C II (ν) Q(ν) ∀γ ∈ [r] For ν in Θ(I) ∪ Θ(I c ): B ν,γ = φ ν,γ I|ν ∀γ ∈ [r]

For ν in int(T )\{nodes in Θ(I) or Θ(I c ) or descendants of such} (depth-first order):

B ν,γ = r α=1 a ν,γ,I α B C I (ν),α r α=1 a ν,γ,II α B C II (ν),α ∀γ ∈ [r] A y I = A•B [N ],y • Ā ∀y ∈ [r],

for appropriate matrices A and Ā

Consider now a node ν∈int(T ) whose child belongs to a tiling -without loss of generality C I (ν) belongs to Θ(I). Notice that in this case B CI(ν),α is a column vector for every α ∈ [r]. We may thus define B CI(ν) to be the matrix whose α'th column is B CI(ν),α , and get the following equalities:

B ν,γ = B C I (ν) a ν,γ,I r α=1 a ν,γ,II α B C II (ν),α = B C I (ν) I a ν,γ,I r α=1 a ν,γ,II α B C II (ν),α

where again, I is an appropriately sized identity matrix. This implies that we can propagate outwards B CI(ν) I, just as we have done with permutation matrices. Applying this procedure to all nodes in the tilings Θ(I) and Θ(I c ), we arrive at the decomposition below:

For ν in Θ(I):

B ν,γ = e (γ) ∀γ ∈ [r]

For ν in Θ(I c ):

B ν,γ = (e (γ) ) ∀γ ∈ [r]

For ν in int(T )\{nodes in Θ(I) or Θ(I c ) or descendants of such} (depth-first order):

B ν,γ = r α=1 a ν,γ,I α B C I (ν),α r α=1 a ν,γ,II α B C II (ν),α ∀γ ∈ [r] A y I = A•B [N ],y • Ā ∀y ∈ [r],

for appropriate matrices A and Ā

Notice that for compactness in writing we made use of the fact that a ν,γ,I = r α=1 a ν,γ,II α e (α) , where e (α) , α ∈ [r], is the vector in R r holding 1 in entry α and 0 in the rest. Note also that in this decomposition, as opposed to the previous ones, the matrices A and Ā are not global constants that depend only on T . Rather, they also depend on φ ν,γ

I|ν for tiling nodes ν ∈ Θ(I) ∪ Θ(I c ), and thus are ultimately determined through a hidden computation that is not specified above. This hidden computation is outside our scope, as we are only interested in the size of the matrices {B [N ],y } y . It is not difficult to see that this size is precisely r |Θ(I)| -by-r |Θ(I c )| , meaning that the ranks of {B [N ],y } y are no more than r min{|Θ(I)|,|Θ(I c )|} . Since these ranks are greater than or equal to those of { A y I } y , the sought after upper bound (eq. 10) indeed holds.

In the third and final stage of the proof, we establish the lower bound stated in the theorem, namely, that for all configurations of weights {a ν,γ,I , a ν,γ,II } ν,γ but a set of Lebesgue measure zero:

rank A y I ≥ r |{(ν1,ν2)∈Θ(I)×Θ(I c ): ν1 and ν2 are siblings in T with depth>1}| ∀y (11)

We reduce the problem in three successive steps:

• A tree decomposition (eq. 3) with a product operator g(•) admits maximal matricization ranks almost always (see app. G). Therefore, to prove that eq. 11 holds for all weight settings but a set of Lebesgue measure zero, it suffices to find a particular weight setting for which the inequality holds. • By assumption, the discretizers {v (i) } i∈[M ] span R r . Without loss of generality, assume that {v (i) } i∈[r] are linearly independent, and consider the sub-tensors of {A y } y formed by restricting their indexes to the range 1. . .r (instead of 1. . .M ). The matricizations of these sub-tensors w.r.t. I are sub-matrices of { A y I } y , thus any lower bound on ranks of the former matricizations immediately translates to a lower bound on ranks of the latter. Since the sub-tensors are precisely the grid tensors that would have been generated by the tree decomposition (eq. 3) had we omitted the trailing discretizers {v (i) } i∈[M ]\[r] , establishing eq. 11 in the case M = r proves that it holds in general (M ≥r).

• Bearing in mind that we assume M = r (and linear independence of {v (i) } i∈[r] ), denote by V the r-by-r matrix holding v (i) in its i'th row, i.e. V := [v (1) • • • v (r) ] . From the tree decomposition (eq. 3) it is evident that the discretizers affect generated grid tensors only through products of the form V a ν,γI or V a ν,γII , where ν is a parent of a leaf node in T . Since V is invertible ({v (i) } i∈[r] are linearly independent), its exact value has no effect on the class of representable grid tensors -any change it undergoes may be accounted for by the weights a ν,γI and a ν,γII that multiply it (these weights do not appear elsewhere in the decomposition). Accordingly, for establishing a lower bound on achievable grid tensor matricization ranks, the value of V is irrelevant (so long as it is invertible), and we may assume, without loss of generality, that V is the identity matrix, i.e. that v (i) = e (i) for all i ∈ [r].

Taking into account the above reductions, our objective is to show that there exists a setting of weights {a ν,γ,I , a ν,γ,II } ν,γ , such that the following special case of the matricized tree decomposition (eq. 9) generates matricizations meeting the lower bound in eq. 11:

For j in I: For ν in int(T ) (depth-first order): Similarly to the procedure carried out in the second stage of the proof (establishing the upper bound in eq. 10), we now propagate outwards the permutation matrices Q (ν) and Q(ν) corresponding to all interior nodes ν∈int(T ). This brings forth the following decomposition:

φ ν,γ I|ν = Q (ν)

For j in I:

B {j},γ = e (γ) ∀γ ∈ [r]

For j in I c :

B {j},γ = (e (γ) ) ∀γ ∈ [r]

For ν in int(T ) (depth-first order): The matrices A and Ā in the assignments of { A y I } y essentially collect all permutation matrices {Q (ν) } ν and { Q(ν) } ν (respectively) that have been propagated outwards. Specifically, A (respectively Ā) is a product of factors, each of the form I Q (ν) I (respectively I Q(ν) I ) for a different interior node ν and appropriately sized identity matrices I and I . Since permutation matrices are invertible, and since the Kronecker product between two invertible matrices is invertible as well (see Bellman (1970) for proof), we conclude that the matrices A and Ā are invertible. Therefore, for every y ∈ [r], the rank of A y I is equal to that of B [N ],y . It thus suffices to find a setting of weights {a ν,γ,I , a ν,γ,II } ν,γ for which: rank(B [N ],γ ) ≥ r |{(ν1,ν2)∈Θ(I)×Θ(I c ): ν1 and ν2 are siblings in T with depth>1}| ∀γ ∈ [r]

B ν,γ =

(13) Disregard the trivial case where there exist siblings ν 1 ∈ Θ(I) and ν 2 ∈ Θ(I c ) of depth 1,2 and consider the following weight setting:

• ν is a node in Θ(I) or Θ(I c ), or a descendant of such: a ν,γ,I = a ν,γ,II = e (γ) ∀γ ∈ [r]

• ν has one child in Θ(I) and the other in Θ(I c ):

a ν,γ,I = a ν,γ,II = e (γ) ∀γ ∈ [r]

• ν is the root node [N ]: a ν,γ,I = a ν,γ,II = e (1) ∀γ ∈ [r]

• ν meets neither of the above (0 and 1 here denote the all-zero and all-one vectors in R r , respectively): a ν,1,I = 1 , C I (ν) has one child in Θ(I) and the other in Θ(I c ) e (1) , otherwise a ν,1,II = 1 , C II (ν) has one child in Θ(I) and the other in Θ(I c ) e (1) , otherwise a ν,γ,I = a ν,γ,II = 0 ∀γ ∈ [r] \ {1} Plugging this into the decomposition in eq. 12, one readily sees that:

• For every ν ∈ Θ(I), {B ν,γ } γ∈[r] are indicator column vectors (one entry holds 1, the rest hold 0) such that B ν,γ =B ν,γ if γ = γ . The same holds for ν ∈ Θ(I c ), but with the vectors being rows.

• If ν has one child in Θ(I) and the other in Θ(I c ), {B ν,γ } γ∈[r] are indicator matrices, where both the row and column indexes of the active entry do not repeat as γ varies.

• The matrices {B [N ],γ } γ∈[r] corresponding to the root node [N ] are equal to one another, given by a joint Kronecker product between all of the following: -B ν,1 for every node ν in either Θ(I) or Θ(I c ) which does not have a sibling in the other r α=1 B ν,α for every node ν that has one child in Θ(I) and the other in Θ(I c ) According to the first observation above, B ν,1 has rank 1 for every ν in Θ(I) or Θ(I c ). The second observation implies that r α=1 B ν,α has rank r for every node ν that has one child in Θ(I) and the other in Θ(I c ). In turn, and while taking into account the rank-multiplicative property of the Kronecker product (rank(A A ) = rank(A)•rank(A ) -see Bellman (1970) for proof), the third observation implies: rank(B [N ],γ ) = r |{(ν1,ν2)∈Θ(I)×Θ(I c ): ν1 and ν2 are siblings in T }| ∀γ ∈ [r]

We thus have found weights {a ν,γ,I , a ν,γ,II } ν,γ for which eq. 13 holds. 3 This establishes the sought after lower bound on matricization ranks (eq. 11), completing the proof of the theorem.

:

We note that in addition to the mixed dilated convolutional network M, we also evaluated the individual networks N and N -both reached accuracies comparable to M in the case of zero interconnections (output summation only).

The case of convolutional arithmetic circuits (g(a, b)=a•b) was also evaluated, leading to the exact same trends as those observed with ReLU (fig.5).

The viewpoint we adopt is actually a concrete special case of a more abstract algebraic viewpoint of tensor analysis, as presented for example inHackbusch (2012). We limit ourselves to this concrete viewpoint since it suffices for our needs and is easier to grasp.

In this case I and I c are the children of the root node [N ], and the maximal rank of B [N ],γ is 1 for every γ ∈ [r].

This applies to all but the trivial case where I is such that there exist siblings ν1 ∈ Θ(I) and ν2 ∈ Θ(I c ) of depth 1 (I and I c are the children of the root node [N ]). In the latter case the lower bound in eq. 13 can be met trivially.

If c is a scalar and S is a set, c + S stands for the set obtained by adding c to each element in S.

Figures and Tables:

(a)), and on those corresponding to networks obtained by swapping dilations of different layers (fig. 2(b), for example).

size

Figure 1: Baseline dilated convolutional network architecture (see description in app. B).

Figure 2: Best viewed in color. Dilated convolutional networks (left) and the mode trees underlying their respective tensor decompositions (right). (a) Baseline architecture -dilation 2 l-1 in layer l. (b) Architecture obtained by swapping dilations of even and odd layers.

(b)-right), we obtain a decomposition that characterizes a network whose dilations are swapped (fig. 2(b)-left).

Figure 3: To be viewed in color. (a) Two mode trees T and T (given on the right of fig. 2), along with a possible choice of mixture nodes mix(T, T ) for the mixed decomposition (eq. 4). (b) Mixed dilated convolutional network corresponding to chosen mixed decomposition. Networks N and N associated with T and T (fig. 2, left) are combined through output summation and rewiring of an intermediate convolutional layer (green).

Figure 4: Best viewed in color. (a) Two mode trees T and T along with a possible choice of mixture nodes (same as in fig. 3(a)). (b) Sample of the resulting hybrid mode trees (def. 2).

Figure 5: Experimental results -increasing the number of interconnections between hidden layers of different dilated convolutional networks improves accuracy, with no additional cost in computation or model capacity.

Figure 6: Mode tree T along with a specific index set I and the resulting tiling Θ(I; T ) (def. 3).

{j},γ  I| {j} = e (γ) ∀γ ∈ [r]For j in I c :φ {j},γ I| {j} = (e (γ) ) ∀γ ∈ [r]

= A•B [N ],y • Ā ∀y ∈ [r],for appropriate matrices A and Ā (12)

[N ]  is reached. At this point tensors are summed and returned as output. The formal definition of the mixed decomposition, annotated in detail in app. D, is as follows:

Table content: <table><tr><td>(a)</td><td/><td/><td/><td/><td/><td colspan="3">mode tree T</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>mode tree T</td></tr><tr><td/><td/><td/><td/><td colspan="6">{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}</td><td/><td colspan="2">mix(T,T)</td><td/><td/><td/><td/><td colspan="2">{1,2,3,4,5,6,7,8,9</td></tr><tr><td/><td/><td colspan="3">{1,2,3,4,5,6,7,8}</td><td/><td/><td/><td/><td colspan="2">{9,10,11,12,13,14,15,16}</td><td/><td/><td/><td colspan="4">{1,2,3,4,9,10,11,12}</td><td>{5,6,7,8,13,14,15,16}</td></tr><tr><td/><td colspan="2">{1,2,3,4}</td><td/><td/><td colspan="2">{5,6,7,8}</td><td/><td colspan="2">{9,10,11,12}</td><td colspan="2">{13,14,15,16}</td><td/><td colspan="2">{1,2,3,4}</td><td/><td/><td colspan="2">{5,6,7,8}</td><td>{9,10,11,12}</td><td>{13,14,15,16}</td></tr><tr><td colspan="2">{1,2}</td><td colspan="2">{3,4}</td><td colspan="2">{5,6}</td><td colspan="2">{7,8}</td><td>{9,10}</td><td>{11,12}</td><td>{13,14}</td><td>{15,16}</td><td colspan="2">{1,3}</td><td colspan="2">{2,4}</td><td colspan="2">{5,7}</td><td>{6,8}</td><td>{9,11}</td><td>{10,12}</td><td>{13,15}</td><td>{14,16}</td></tr><tr><td>{1}</td><td>{2}</td><td>{3}</td><td>{4}</td><td>{5}</td><td>{6}</td><td>{7}</td><td>{8}</td><td colspan="4">{9} {10} {11} {12} {13} {14} {15} {16}</td><td>{1}</td><td>{2}</td><td>{3}</td><td>{4}</td><td>{5}</td><td>{6}</td><td>{7}</td><td>{8}</td><td>{9} {10} {11} {12} {13} {14} {15} {16}</td></tr><tr><td>(b)</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="3">output</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td colspan="2">dilation-8</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="3">network</td><td/><td colspan="2">dilation-4</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>N</td><td/><td/><td colspan="2">dilation-2</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td colspan="2">dilation-1</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="3">input</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td colspan="2">dilation-2</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="3">network</td><td/><td colspan="2">dilation-1</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>N</td><td/><td/><td colspan="2">dilation-8</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td colspan="2">dilation-4</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2018):
 This paper theoretically validates that interconnecting networks with different dilations can lead to expressive efficiency, which indicates an interesting phenomenon that connectivity is able to enhance the expressiveness of deep networks. A key technical tool is a mixed tensor decomposition, which is shown to have representational advantage over the individual hierarchical decompositions it comprises. Pros: Existing work have focused on understanding the depth of the networks and established that deep networks are expressively efficient with respect to shallow ones. On the other hand, this paper focused on the architectural feature of connectivity. The problem is fundamentally important and its theoretical development is solid. The conclusion is useful for developing new tools for deep network design. Cons: In order to show that the mixed dilated convolutional network is expressively efficient w.r.t. the corresponding individual dilated convolutional network, the authors prove it in two steps: Proposition 1 and Proposition 2. However, in the proof of Proposition 2 (see Theorem 1), the authors only focus on a particular case of convolutional arithmetic circuits, i.e., . In the experiments, see line 4 of page 9, the authors instead used ReLU activation . Can authors provide some justifications of such different choices of activation functions? It would be great if authors can discuss how to generate the activation function in Theorem 1 to more general cases.