Deep neural networks are surprisingly efficient at solving practical tasks,
 but the theory behind this phenomenon is only starting to catch up with
 the practice. Numerous works show that depth is the key to this efficiency.
 A certain class of deep convolutional networks – namely those that correspond
 to the Hierarchical Tucker (HT) tensor decomposition – has been
 proven to have exponentially higher expressive power than shallow networks.
 I.e. a shallow network of exponential width is required to realize
 the same score function as computed by the deep architecture. In this paper,
 we prove the expressive power theorem (an exponential lower bound on
 the width of the equivalent shallow network) for a class of recurrent neural
 networks – ones that correspond to the Tensor Train (TT) decomposition.
 This means that even processing an image patch by patch with an RNN
 can be exponentially more efficient than a (shallow) convolutional network
 with one hidden layer. Using theoretical results on the relation between
 the tensor decompositions we compare expressive powers of the HT- and
 TT-Networks. We also implement the recurrent TT-Networks and provide
 numerical evidence of their expressivity. Deep neural networks solve many practical problems both in computer vision via Convolutional Neural Networks (CNNs) BID19 ; BID31 ; BID14 ) and in audio and text processing via Recurrent Neural Networks (RNNs) BID11 ; BID21 BID8 ). However, although many works focus on expanding the theoretical explanation of neural networks success BID20 ; BID6 ; ), the full theory is yet to be developed.One line of work focuses on expressive power, i.e. proving that some architectures are more expressive than others. showed the connection between Hierarchical Tucker (HT) tensor decomposition and CNNs, and used this connection to prove that deep CNNs are exponentially more expressive than their shallow counterparts. However, no such result exists for Recurrent Neural Networks. The contributions of this paper are three-fold.1. We show the connection between recurrent neural networks and Tensor Train decomposition (see Sec. 4); 2. We formulate and prove the expressive power theorem for the Tensor Train decomposition (see Sec. 5), which -on the language of RNNs -can be interpreted as follows: to (exactly) emulate a recurrent neural network, a shallow (non-recurrent) architecture of exponentially larger width is required; DISPLAYFORM0 Figure 1: Recurrent-type neural architecture that corresponds to the Tensor Train decomposition. Gray circles are bilinear maps (for details see Section 4). In this paper, we explored the connection between recurrent neural networks and Tensor Train decomposition and used it to prove the expressive power theorem, which states that a shallow network of exponentially large width is required to mimic a recurrent neural network. The downsides of this approach is that it provides worst-case analysis and do not take optimization issues into account. In the future work, we would like to address the optimization issues by exploiting the Riemannian geometry properties of the set of TT-tensors of fixed rank and extend the analysis to networks with non-linearity functions inside the recurrent connections (as was done for CNNs in ).
We prove the exponential efficiency of recurrent-type neural networks over shallow networks. The authors compare the complexity of tensor train networks with networks structured by CP decomposition