Year: 2021

Abstract:
Tensor Networks (TN) offer a powerful framework to efficiently represent very high-dimensional objects. TN have recently shown their potential for machine learning applications and offer a unifying view of common tensor decomposition models such as Tucker, tensor train (TT) and tensor ring (TR). However, identifying the best tensor network structure from data for a given task is challenging. In this work, we leverage the TN formalism to develop a generic and efficient adaptive algorithm to jointly learn the structure and the parameters of a TN from data. Our method is based on a simple greedy approach starting from a rank one tensor and successively identifying the most promising tensor network edges for small rank increments. Our algorithm can adaptively identify TN structures with small number of parameters that effectively optimize any differentiable objective function. Experiments on tensor decomposition, tensor completion and model compression tasks demonstrate the effectiveness of the proposed algorithm. In particular, our method outperforms the state-of-the-art evolutionary topology search introduced in [19] for tensor decomposition of images (while being orders of magnitude faster) and finds efficient structures to compress neural networks outperforming popular TT based approaches [24].

heading: 1 INTRODUCTION
text: Matrix factorization is ubiquitous in machine learning and data science and forms the backbone of many algorithms. Tensor decomposition techniques emerged as a powerful generalization of matrix factorization. They are particularly suited to handle high-dimensional multi-modal data and have been successfully applied in neuroimaging [44], signal processing [3, 33], spatio-temporal analysis [1, 31] and computer vision [20]. Common tensor learning tasks include tensor decomposition (finding a low-rank approximation of a given tensor), tensor regression (which extends linear regression to the multi-linear setting), and tensor completion (inferring a tensor from a subset of observed entries).
Akin to matrix factorization, tensor methods rely on factorizing a high-order tensor into small factors. However, in contrast with matrices, there are many different ways of decomposing a tensor, each one giving rise to a different notion of rank, including CP, Tucker, Tensor Train (TT) and Tensor Ring (TR). For most tensor learning problems, there is no clear way of choosing which decomposition model to use, and the cost of model mis-specification can be high. It may even be the case that none of the commonly used models is suited for the task, and new decomposition models would achieve better tradeoffs between minimizing the number of parameters and minimizing a given loss function.
We propose an adaptive tensor learning algorithm which is agnostic to decomposition models. Our approach relies on the tensor network formalism, which has shown great success in the many-body physics community [28, 7, 6] and has recently demonstrated its potential in machine learning for compressing models [24, 39, 8, 23, 14, 41], developing new insights into the expressiveness of deep neural networks [4, 15], and designing novel approaches to supervised [35, 9] and unsupervised [34, 11, 22] learning. Tensor networks offer a unifying view of tensor decomposition models, allowing one to reason about tensor factorization in a general manner, without focusing on a particular model.
In this work, we design a greedy algorithm to efficiently search the space of tensor network structures for common tensor problems, including decomposition, completion and model compression. We start by considering the novel tensor optimization problem of minimizing a loss over arbitrary tensor network structures under a constraint on the number of parameters. To the best of our knowledge,
this is the first time that this problem is considered. The resulting problem is a bi-level optimization problem where the upper level is a discrete optimization over tensor network structures, and the lower level is a continuous optimization of a given loss function. We propose a greedy approach to optimize the upper-level problem, which is combined with continuous optimization techniques to optimize the lower-level problem. Starting from a rank one initialization, the greedy algorithm successively identifies the most promising edge of a tensor network for a rank increment, making it possible to adaptively identify from data the tensor network structure which is best suited for the task at hand.
The greedy algorithm we propose is conceptually simple, and experiments on tensor decomposition, completion and model compression tasks showcase its effectiveness. Our algorithm significantly outperforms a recent evolutionary algorithm [19] for tensor network decomposition on an image compression task by discovering structures that require less parameters while simultaneously achieving lower recovery errors. The greedy algorithm also outperforms CP, Tucker, TT and TR algorithms on an image completion task and finds more efficient TN structures to compress fully connected layers in neural networks than the TT based method introduced in [24].
Related work Adaptive tensor learning algorithms have been previously proposed, but they only consider determining the rank(s) of a specific decomposition and are often tailored to a specific tensor learning task (e.g., decomposition or regression). In [1], a greedy algorithm is proposed to adaptively find the ranks of a Tucker decomposition for a spatio-temporal forecasting task, and in [38] an adaptive Tucker based algorithm is proposed for background subtraction. In [42], the authors present a Bayesian approach for automatically determining the rank of a CP decomposition. In [2] an adaptive algorithm for tensor decomposition in the hierarchical Tucker format is proposed. In [10] a stable rank-adaptive alternating least square algorithm is introduced for completion in the TT format. The problem we consider is considerably more general since we do not assume a fixed tensor network structure (e.g. Tucker, TT, CP, etc.). Exploring other decomposition relying on the tensor network formalism has been sporadically explored. The work which is the most closely related to our contribution is [19] where evolutionary algorithms are used to approximate the best tensor network structure to exactly decompose a given target tensor. However, the method proposed in [19] only searches for TN structures with uniform ranks (with the rank being a hyperparameter) and is limited to the problem of tensor decomposition. In contrast, our method is the first to jointly explore the space of structures and (non-uniform) ranks to minimize an arbitrary loss function over the space of tensor parameters. Lastly, [12] proposes to explore the space of tensor network structures for compressing neural networks, a rounding algorithm for general tensor networks is proposed in [21] and the notions of rank induced by arbitrary tensor networks are studied in [40].

heading: 2 PRELIMINARIES
text: In this section, we present notions of tensor algebra and tensor networks. We first introduce notations. For any integer k, [k] denotes the set of integers from 1 to k. We use lower case bold letters for vectors (e.g. v 2 Rd1 ), upper case bold letters for matrices (e.g. M 2 Rd1⇥d2 ) and bold calligraphic letters for higher order tensors (e.g. T 2 Rd1⇥d2⇥d3 ). The ith row (resp. column) of a matrix M will be denoted by Mi,: (resp. M:,i). This notation is extended to slices of a tensor in the obvious way.
Tensors and tensor networks We first recall basic definitions of tensor algebra; more details can be found in [17]. A tensor T 2 Rd1⇥···⇥dp can simply be seen as a multidimensional array (T i1,··· ,ip : in 2 [dn], n 2 [p]). The inner product of two tensors is defined by hS,T i =P
i1,··· ,ip Si1···ipT i1···ip and the Frobenius norm of a tensor is defined by kT k 2 F = hT ,T i. The mode-n matrix product of a tensor T and a matrix X 2 Rm⇥dn is a tensor denoted by T ⇥n X. It is of size d1⇥ · · ·⇥dn 1⇥m⇥dn+1⇥ · · ·⇥dp and is obtained by contracting the nth mode of T with the second mode of X, e.g. for a 3rd order tensor T , we have (T ⇥2X)i1i2i3 = P j T i1ji3Xi2j . The nth mode matricization of T is denoted by T (n) 2 Rdn⇥ Q
i 6=n di . Tensor network diagrams allow one to represent complex operations on tensors in a graphical and intuitive way. A tensor network (TN) is simply a graph where nodes represent tensors, and edges represent contractions between tensor modes, i.e. a summation over an index shared by two tensors. In a tensor network, the arity of a vertex (i.e. the number of legs of a node) corresponds to the order of the tensor (see Figure 1). Connecting two legs in a tensor network represents a contraction over the corresponding indices. Consider
the following simple tensor network with two nodes: A x m n . The first node represents a matrix A 2 Rm⇥n and the second one a vector x 2 Rn. Since this tensor network has one dangling leg (i.e. an edge which is not connected to any other node), it represents a first order tensor, i.e., a vector. The edge between the second leg of A and the leg of x corresponds to a contraction between the second mode of A and the first mode of x. Hence, the resulting tensor network represents the classical matrix-vector product, which can be seen by calculating the ith component of this tensor network: A xi = P j Aijxj = (Ax)i . Other examples of tensor network representations
of common operations on matrices and tensors can be found in Figure 2. Lastly, it is worth mentioning that disconnected tensor networks correspond to tensor products, e.g., u v = uv> is the
outer product of u and v with components u vi j= uivj . Consequently, an edge of dimension (or rank) 1 in a TN is equivalent to having no edge between the two nodes, e.g., if R = 1 we have A Bi R j = PR r=1 Ai,rBr,j = Ai,1B1,j = A Bi j.
Tensor decomposition and tensor rank We now briefly present the most common tensor decomposition models, omitting the CP decomposition which cannot be described using the TN formalism unless hyper-edges are allowed (which we do not consider in this work). For the sake of simplicity we consider a fourth order tensor T 2 Rd1⇥d2⇥d3⇥d4 , each decomposition can be straightforwardly extended to higher-order tensors. A Tucker decomposition [36] decomposes T as the product of a core tensor G 2 RR1⇥R2⇥R3⇥R4 with four factor matrices Ui 2 Rdi⇥Ri for i = 1, · · · , 4: T = G ⇥1 U1 ⇥2 U2 ⇥3 U3 ⇥4 U4. The Tucker rank, or multilinear rank, of T is the smallest tuple (R1, R2, R3, R4) for which such a decomposition exists. The tensor ring (TR) decomposition [43, 25, 29] expresses each component of T as the trace of a product of slices of four core tensors G(1) 2 RR0⇥d1⇥R1 , G(2) 2 RR1⇥d2⇥R2 , G(3) 2 RR2⇥d3⇥R3 and G(4) 2 RR4⇥d4⇥R0 : T i1,i2,i3,i4 = Tr(G (1) :,i1,: G(2):,i2,:G (3) :,i3,:
G(4):,i4,:). The tensor train (TT) decomposition [26] (also known as matrix product states in the physics community) is a particular case of the tensor ring decomposition where R0 must be equal to 1 (R0 is thus omitted when referring to the rank of a TT decomposition). Similarly to Tucker, the TT and TR decompositions naturally give rise to an associated notion of rank: the TR rank (resp. TT rank) is the smallest tuple (R0, R1, R2, R3) (resp. (R1, R2, R3)) such that a TR (resp. TT) decomposition exists.
Tensor networks offer a unifying view of tensor decomposition models: Figure 3 shows the TN representation of common models. Each decomposition is naturally associated with the graph topology of the underlying TN. For example, the Tucker decomposition corresponds to star graphs, the TT decomposition corresponds to chain graphs, and the TR decomposition model corresponds to cyclic graphs. The relation between the rank of a decomposition and its number of parameters is different for each model. Letting p be the order of the tensor, d its largest dimension and R the rank of the decomposition (assuming uniform ranks), the number of parameters is in O (Rp + pdR) for Tucker, and O pdR2 for TT and TR. One can see that the Tucker decomposition is not well suited for tensors of very high order since the size of the core tensor grows exponentially with p.

heading: 3 A GREEDY ALGORITHM FOR TENSOR NETWORK STRUCTURE LEARNING

heading: 3.1 TENSOR NETWORK OPTIMIZATION
text: We consider the problem of minimizing a loss function L : Rd1⇥···⇥dp ! R+ w.r.t. a tensor W efficiently parameterized as a tensor network (TN). We first introduce our notations for TN.
Without loss of generality, we consider TN having one factor per dimension of the parameter tensor W 2 Rd1⇥···⇥dp , where each of the factors has one dangling leg corresponding to one of the dimensions di (we will discuss how this encompasses TN structures with internal nodes such as Tucker at the end of this section). In this case, a TN structure is summarized by a collection of ranks (Ri,j)1i<jp where each Ri,j 1 is the dimension of the edge connecting the ith and jth nodes of the TN (for convenience, we assume Ri,j = Rj,i if i > j). If there is no edge between nodes i and j in a TN, Ri,j is thus equal to 1 (see Section 2). A TN decomposition of W 2 Rd1⇥···⇥dp is then given by a collection of core tensors G(1), · · · ,G(p) where each G(i) is of size R1,i ⇥ · · ·⇥Ri 1,i ⇥ di ⇥Ri,i+1 ⇥ · · ·⇥Ri,p. Each core tensor is of order p but some of its dimensions may be equal to one (representing the absence of edge between the two cores in the TN structure). We use TN(G(1), · · · ,G(p)) to denote the resulting tensor. Formally, for an order 4 tensor we have
TN(G(1), · · · ,G(4))i1i2i3i4 = R1,2X
j21=1
R1,3X
j31=1
· · ·
R3,4X
j43=1
G(1) i1,j21 ,j 3 1 ,j 4 1 G(2) j21 ,i2,j 3 2 ,j 4 2 G(3) j31 ,j 3 2 ,i3,j 4 3 G(4) j41 ,j 4 2 ,j 4 3 ,i4 .
This definition is straightforwardly extended to TN representing tensors of arbitrary orders.
As an illustration, for a TT decomposition the ranks of the tensor network representation would be such that Ri,j 6= 1 if and only if j = i + 1. The problem of finding a rank (r1, r2, r3) TT decomposition of a target tensor T 2 Rd1⇥d2⇥d3⇥d4 can thus be formalized as
min G(1)2Rd1⇥r1⇥1⇥1,G(2)2Rr1⇥d2⇥r2⇥1, G(3)2R1⇥r2⇥d3⇥r3 ,G(4)2R1⇥1⇥r3⇥d4
L(TN(G(1),G(2),G(3),G(4))) (1)
where L(W) = kT Wk2F . Other common tensor problems can be formalized in this manner. For example, the tensor train completion problem would be formalized similarly with the loss function being L(W) = 1|⌦| P (i1,··· ,ip)2⌦(W i1,··· ,ip T i1,··· ,ip)
2 where ⌦ ⇢ [d1]⇥ · · ·⇥ [dp] is the set of observed entries of T 2 Rd1⇥···⇥dp , and learning TT models for classification [35] and sequence modeling [11] also falls within this general formulation by using the cross-entropy or log-likelihood as a loss function.
We now explain how our formalism encompasses TN structure with internal nodes, such as the Tucker format. Since a rank one edge in a TN is equivalent to having no edge, internal cores can be represented as cores whose dangling leg have dimension 1. Consider for example the Tucker decomposition T = G ⇥1 U1 ⇥2 U2 ⇥3 U3 2 Rd1⇥d2⇥d3 of rank (r1, r2, r3). The tensor T can naturally be seen as a fourth order tensor T̃ 2 R1⇥d1⇥d2⇥d3 , G as G̃ 2 R1⇥r1⇥r2⇥r3 , U1 as Ũ1 2 Rr1⇥d1⇥1⇥1, U2 as Ũ2 2 Rr2⇥1⇥d2⇥1⇥1 and U3 as Ũ3 2 Rr3⇥1⇥1⇥d3 . With these definitions, one can check that TN(G̃, Ũ1, Ũ2, Ũ3) = G ⇥1 U1 ⇥2 U2 ⇥3 U3 = T . More complex TN structure with internal nodes such as hierarchical Tucker can be represented using our formalism in a similar way. The assumption that each core tensor in a TN structure has one dangling leg corresponding to each of the dimensions of the tensor T is thus without loss of generality, since it suffices to augment T with singleton dimensions to represent TN structures with internal nodes.

heading: 3.2 PROBLEM STATEMENT
text: A large class of TN learning problems consist in optimizing a loss function w.r.t. the core tensors of a fixed TN structure; this is, for example, the case of the TT completion problem: the rank of the decomposition may be selected using, e.g., cross-validation, but the overall structure of the TN is fixed a priori. In contrast, we propose to optimize the loss function simultaneously w.r.t. the core tensors of the TN and the TN structure itself. This joint optimization problem can be formalized as
min Ri,j,
1i<jp
min G(1),··· ,G(p)
L(TN(G(1), · · · ,G(p))) s.t. size(G(1), · · · ,G(p))  C (2)
where L is a loss function, each core tensor G(i) is in RR1,i⇥···⇥Ri 1,i⇥di⇥Ri,i+1⇥···⇥Ri,p , C is a bound on the number of parameters, and size(G(1), · · · ,G(p)) is the number of parameters of the TN, which is equal to Pp i=1 diR1,i · · ·Ri 1,iRi,i+1 · · ·Ri,p. Note that if K is the maximum arity of a node in a TN, its number of parameters is in O pdRK where d = maxi di and R = maxi,j Ri,j .
Problem 2 is a bi-level optimization problem where the upper level is a discrete optimization over TN structures, and the lower level is a continuous optimization problem (assuming the loss function is continuous). If it is possible to solve the lower level continuous optimization, an exact solution can be found by enumerating the search space of the upper level, i.e. enumerating all TN structures satisfying the constraint on the number of parameters, and selecting the one achieving the lower value of the objective. This approach is, of course, not realistic since the search space is combinatorial in nature, and its size will grow exponentially with p. Moreover, for most tensor learning problems, the lower-level continuous optimization problem is NP-hard [13]. In the next section, we propose a general greedy approach to tackle this problem.

heading: 3.3 GREEDY ALGORITHM
text: We propose a greedy algorithm which consists in first optimizing the loss function L starting from a rank one initialization of the tensor network, i.e. Ri,j is set to one for all i, j and each core tensor G(i) 2 RR1,i⇥···⇥Ri 1,i⇥di⇥Ri,i+1⇥···⇥Ri,p is initialized randomly. At each iteration of the greedy algorithm, the most promising edge of the current TN structure is identified through some efficient heuristic, the corresponding rank is increased, and the loss function is optimized w.r.t. the core tensors of the new TN structure initialized through a weight transfer mechanism. In addition, at each iteration, the greedy algorithm identifies nodes that can be split to create internal nodes in the TN structure by analyzing the spectrum of matricizations of its core tensors.
The overall greedy algorithm, named Greedy-TN, is summarized in Algorithm 1. In the remaining of this section, we describe the continuous optimization, weight transfer, best edge identification and node splitting procedures. For Problem 2, a natural stopping criterion for the greedy algorithm is when the maximum number of parameters is reached, but more sophisticated stopping criteria can be used. For example, the algorithm can be stopped once a given loss threshold is reached, which leads to an approximate solution to the problem of identifying the TN structure with the least number of parameters achieving a given loss threshold. For learning tasks (e.g., TN classifiers or tensor completion), the stopping criterion can be based on validation data (e.g., using early stopping).
Continuous Optimization Assuming that the loss function L is continuous and differentiable, standard gradient-based optimization algorithms can be used to solve the inner optimization problem (line 12 of Algo. 1). E.g., in our experiments on compressing neural network layers (see Section 4) we use Adam [16]. For particular losses, more efficient optimization methods can be used: in our experiments on tensor completion and tensor decomposition, we use the Alternating Least-Squares (ALS) [17, 5] algorithm which consists in alternatively solving the minimization problem w.r.t. one of the core tensors while keeping the other ones fixed until convergence.
Weight Transfer A key idea of our approach is to restart the continuous optimization process from the previous iteration of the greedy algorithm: we initialize the new slices of the two core tensors connected by the incremented edge to values close to 0, while keeping all the other parameters of the TN unchanged (line 8-10 of Algo. 1). E.g., for a tensor network of order 4, increasing the rank of the edge (1, 2) by 1 is done by adding a slice of size d1 ⇥R1,3 ⇥R1,4 (resp. d2 ⇥R2,3 ⇥R2,4) to the second mode of G(1) (resp. first mode of G(2)). After this operation, the new shape of G(1) will
Algorithm 1 Greedy-TN: Greedy algorithm for tensor network structure learning.
Input: Loss function L : Rd1⇥···⇥dp ! R, splitting node threshold ". 1: // Initialize tensor network to a random rank one tensor and optimize loss function. 2: Ri,j 1 for 1  i < j  p 3: Initialize core tensors G(i) 2 RR1,i⇥···⇥Ri 1,i⇥di⇥Ri,i+1⇥···⇥Ri,p randomly 4: (G(1), · · · ,G(p)) optimize L(TN(G(1), · · · ,G(p))) w.r.t. G(1), · · · ,G(p) 5: repeat 6: (i, j) find-best-edge(L, (G(1), · · · ,G(p))) 7: // Weight transfer 8: Ĝ(k) G(k) for k 2 [p] \ {i, j}; Ri,j Ri,j + 1 9: Ĝ(i) add-slice(G(i), j) // add new slice to the jth mode of G(i) 10: Ĝ(j) add-slice(G(j), i) // add new slice to the ith mode of G(j) 11: // Optimize new tensor network structure 12: (G(1), · · · ,G(p)) optimize L(TN(G(1), · · · ,G(p))) from init. Ĝ(1), · · · , Ĝ(p) 13: // Add internal nodes if possible (number of cores p may be increased after this step) 14: (G(1), · · · ,G(p)) split-nodes((G(1), · · · ,G(p)), ") 15: until Stopping criterion
be d1 ⇥ (R1,2 + 1)⇥R1,3 ⇥R1,4 and the one of G(2) will be (R1,2 + 1)⇥ d2 ⇥R2,3 ⇥R2,4. The following proposition shows that if these slices were initialized exactly to 0, the resulting TN would represent exactly the same tensor as the original one. In practice, we initialize the slices randomly with small values to break symmetries that could constrain the continuous optimization process.
Proposition 1. Let G(k) 2 RR1,k⇥···⇥Rk 1,k⇥dk⇥Rk,k+1⇥···⇥Rk,p for k 2 [p] be the core tensors of a tensor network and let 1  i < j  p. Let R̃i0j0 = Ri0,j0 + 1 if (i0, j0) = (i, j) and Ri0,j0 otherwise, and define the core tensors G̃(k) 2 RR̃1,k⇥···⇥R̃k 1,k⇥dk⇥R̃k,k+1⇥···⇥R̃k,p for k 2 [p] by
(G̃(i))(j) =  (G(i))(j) 0 , (G̃(j))(i) =  (G(j))(i) 0 and G̃(k) = G(k) for k 2 [p] \ {i, j}
where 0 denotes a row vector of zeros of the appropriate size in each block matrix.
Then, the core tensors G̃(k) correspond to the same tensor network as the core tensors G(k), i.e., TN(G̃(1), · · · , G̃(p)) = TN(G(1), · · · ,G(p)).
The proof of the proposition can be found in Appendix A. The weight transfer mechanism leads to a more efficient and robust continuous optimization by transferring the knowledge from each greedy iteration to the next and avoiding re-optimizing the loss function from a random initialization at each iteration. An ablation study showing the benefits of weight transfer is provided in Appendix C.3.
Best Edge Selection As mentioned previously, we propose to optimize the inner minimization problem in Eq. 2 using iterative algorithms, namely gradient based algorithms or ALS depending on the loss function L. In order to identify the most promising edge to increase the rank by 1 (line 6 of Algo. 1), a reasonable heuristic consists in optimizing the loss for a few epochs/iterations for each possible edge and select the edge which led to the steepest decrease in the loss. One drawback of this approach is its computational complexity: e.g., for ALS, each iteration requires solving p least-squares problem with di Q k 6=i Ri,k unknowns for i 2 [p]. We propose to reduce the complexity of the exploratory optimization in the best edge identification heuristic by only optimizing L w.r.t. the new slices of the core tensors. Thus, at each iteration of the greedy algorithm, for each possible edge to increase, we transfer the weights from the previous greedy iteration, optimize only w.r.t. the new slices for a small number of iteration, and choose the edge which led to the steepest decrease of the loss. For ALS, this reduces the complexity of each iteration to the one of solving 2 least-squares problems with di Q k2[p]\{i,j} Ri,k and dj Q k2[p]\{i,j} Ri,k unknowns, respectively, where (i, j) is the edge being considered in the search. When using gradient-based optimization algorithms, the same approach is used where the gradient is only computed for (and back-propagated through) the
new slices. It is worth mentioning that the greedy algorithm can seamlessly incorporate structural constraints by restricting the set of edges considered when identifying the best edge for a rank increment. For example, it can be used to adaptively select the ranks of a TT or TR decomposition.
Internal Nodes Lastly, we design a simple approach for the greedy algorithm to add internal nodes to the TN structure relying on a common technique used in TN methods to split a node into two new nodes using truncated SVD (see, e.g., Fig. 7.b in [35]). To illustrate this technique, let M 2 Rm1⇥m2⇥n1⇥n2 be the core tensor associated with a node in a TN we want to split into two new nodes A 2 Rm1⇥m2⇥r and B 2 Rn1⇥n2⇥r: the first two legs of A (resp. B) will be connected to the core tensors that were connected to M by its first two legs (resp. last two legs), and the third leg of A and B will be connected together. This is achieved by taking the rank r truncated SVD of (M)(1,2) ' UDV> 2 Rm1m2⇥n1n2 (the matricization of M having modes 1 and 2 as rows and modes 3 and 4 as columns), and letting A(3) = U> 2 Rr⇥m1m2 and B(3) = DV> 2 Rr⇥n1n2 . If the truncated SVD is exact, the resulting TN will represent exactly the same tensor as the one before splitting the core M. This node splitting procedure is illustrated in the following TN diagram.
m1 m2
n1 n2 M ' m1 m2 U D V r r n1 n2 = m1 m2 A Br n1 n2
In order to allow the greedy algorithm to learn TN structures with internal nodes, at the end of each greedy iteration, we perform an SVD of each matricization of G(k) for k 2 [p] (line 14 of Algo. 1). For each matricization, we split the corresponding node only if there are enough singular values below a given threshold " in order for the new TN structure to have less parameters than the initial one. While this approach may seem computationally heavy, the cost of these SVDs is negligible w.r.t. the continuous optimization step which dominates the overall complexity of the greedy algorithm.
The details of all subroutines of Algorithm 1 as well as its complexity are given in the Appendix B.

heading: 4 EXPERIMENTS
text: In this section we evaluate Greedy-TN on decomposition, completion, and model compression.
Tensor decomposition We first consider a tensor decomposition task. We randomly generate four target tensors of size 7⇥ 7⇥ 7⇥ 7⇥ 7 with the following TN structures:
TT target tensor
2 3 6 5
TR target tensor
2 3 4 5
5
Tucker target tensor
2 3 4 3 2
5 2 5
2 2
“Triangle” target tensor
We run Greedy-TN until it recovers an almost exact decomposition (stopping when the relative error falls below 10 6). We compare Greedy-TN with CP, Tucker and TT decomposition (using the implementations from the TensorLy python package [18]) of increasing rank as baselines (we use uniform ranks for Tucker and TT). We also include a simple random walk baseline based on Greedy-TN, where the edge for the rank increment is chosen at random at each iteration. Reconstruction errors averaged over 100 runs of this experiment are reported in Figure 4, where we see that the greedy algorithm outperforms all baselines for the the four target tensors. Notably, Greedy-TN outperforms TT/Tucker even on the TT/Tucker targets. This is because the rank of the TT and Tucker targets are not uniform and Greedy-TN is able to adaptively set different ranks to achieve the best compression ratio. Furthermore, Greedy-TN is able to recover the exact TN structure of the triangle target tensor on almost every run. Lastly, we observe that the internal node search of Greedy-TN is only beneficial on the Tucker target tensor, which is expected due to the absence of internal nodes in the other target TN structures. As an illustration of the running time, for the TR target, one iteration of Greedy-TN takes approximately 0.91 second on average without the internal node search and 1.18 seconds with the search. The most common TN structures recovered by Greedy-TN are shown in Appendix C.1. This experiment showcases the potential cost of model mis-specification: both CP and Tucker struggle to efficiently approximate most target tensors. Interestingly, even the random walk outperforms CP and Tucker on the TR target tensor.
Tensor completion We compare Greedy-TN with the TT and TR alternating least square algorithms proposed in [37] and the CP and Tucker decomposition algorithms from Tensorly [18] on an
image completion task. We consider an experiment presented in [37]: the completion of an RGB image of Albert Einstein reshaped into a 6⇥ 10⇥ 10⇥ 6⇥ 10⇥ 10⇥ 3 tensor (see [37] for details) where 10% of entries are randomly observed. The ranks of methods other than Greedy-TN are successively increased by one until the number of parameters gets larger than 25,000 (we use uniform ranks for TT, TR and Tucker*). The relative errors as a function of number of parameters are reported in Figure 5 (left) where we see that Greedy-TN outperforms all methods. The best recovered images for all methods are shown in Figure 5 (right) along with the original image and observed pixels. The best recovery error (9.45%) is achieved by Greedy-TN at iteration 42 with 21,375 parameters. The second best recovery error (10.83%) is obtained by TR-ALS at rank 18 with 17,820 parameters. At iteration 31, Greedy-TN already recovers an image with an error of 10.60% with 10,096 parameters, which is better than the best result of TR-ALS both in terms of parameters and relative error. The images recovered at each iteration of Greedy-TN are shown in Appendix C.2. In this experiment, the total running time of Greedy-TN is comparable to the one of TR-ALS (on the order of hours), which is larger than the one of the other three methods.
Image compression In this experiment, we compare Greedy-TN with the genetic algorithm for TN decomposition recently introduced in [19], denoted by GA(rank=6) and GA(rank=7) where the rank is a hyper-parameter controlling the trade-off between accuracy and compression ratio (the results of TT and TR, which are worst than GA, are available in Table 3 in [19]). Following [19], we select 10 images of size 256 ⇥ 256 from the LIVE dataset [32], tensorize each image to an order-8 tensor of size 48 and run Greedy-TN to decompose each tensor using a squared error loss. Greedy-TN is stopped when the lowest RSE reported in [19] is reached. In Table 1, we report the log compression ratio and root square error averaged over 50 random seeds. For all images,
*For Tucker, the completion is performed on the original image rather than the tensor reshaping since the number of parameters of Tucker grows exponentially, leading to very poor results on the tensorized image.
our method results in a higher compression ratio compared to GA(rank=7). Moreover, for images 1 to 9 our method even outperforms GA(rank=6) by achieving both higher compression ratios and significantly lower RSE. For image 0, setting the greedy stopping criterion to the RSE of GA(rank=6), Greedy-TN also achieves a higher compression ratio than GA(rank=6): 1.085(0.128). Our method is also orders of magnitude faster—few minutes compared to several hours for GA.
Compressing neural networks Following [24], we apply our algorithm to compress a neural network with one hidden layer on the MNIST dataset. The hidden layer is of size 1024⇥ 1024 which we represent as a fifth-order tensor of size 16 ⇥ · · · ⇥ 16. We use Greedy-TN to train the core tensors representing the hidden layer weight matrix alongside the output layer end-to-end. We select the best edge for the rank increment using the validation performance on a separate random split of the train dataset with 5, 000 images. In Figure 6, we report the train and test accuracies of the TT based method introduced in [24] as well as a TR tensorized model for uniform ranks 1 to 8 and Greedy-TN (it is worth noting that we use our own implementation of the TT method with dropout and achieve higher accuracies than the ones reported in [24]). For every model size, our method reaches higher accuracy. The best test accuracy of Greedy-TN is 98.74% with 15,050 parameters, while TT reaches its best accuracy of 98.46% with 14,602 parameters, and TR achieves its best accuracy of 98.42% with 14,154 parameters. At iteration 10, Greedy-TN already achieves an accuracy of 98.46% with only 12,266 parameters. The running time of each iteration of Greedy-TN is comparable with training one tensorized neural network with TT or TR.
Implementation details We use PyTorch [27] and the NCON function [30] to implement Greedy-TN. For the continuous optimization step, we use the Adam [16] optimizer with a learning rate of 10 3 and a batch size of 256 for 50 epochs for compressing neural network, and we use ALS for the other three experiments (ALS is stopped when convergence is reached). The number of iterations/epochs for the best edge identification is set to 2 for tensor decomposition, 5 for image compression and 10 for image completion and compressing neural networks. The singular values threshold for the internal node search is set to " = 10 5. In all experiments except the tensor decomposition on the Tucker target, the internal node search did not lead to any improvement of the results. All experiments were performed on a single 32GB V100 GPU.

heading: 5 CONCLUSION
text: We introduced a greedy algorithm to jointly optimize an arbitrary loss function and efficiently search the space of TN structures and ranks to adaptively find parameter efficient TN structures from data. Our experimental results show that Greedy-TN outperforms common methods tailored for specific decomposition models on model compression and tensor decomposition and completion tasks. Even though Greedy-TN is orders of magnitude faster than the genetic algorithm introduced in [19], its computational complexity can still be limiting in some scenarios. In addition, the greedy algorithm may converge to locally optimal TN structures. Future work includes exploring more efficient discrete optimization techniques to solve the upper-level discrete optimization problem and scaling up the method to discover TN structures suited for efficient compression of larger neural network models.

Review summaries:
First, the idea of rank incremental method for Tensor network decomposition and determination of TN structures is not novel.  Second, decomposition with weight transfer is obvious and widely used in the rank incremental method.  For generalized tensor networks decomposition, the authors should consider the works.  S.  Handschuh,  “Numerical  Methods  in  Tensor  Networks,” PhD  thesis,Facualty of Mathematics and Informatics, University Leipzig, Germany,Leipzig, Germany, 2015.  Mike Espig, Wolfgang Hackbusch, Stefan Handschuh, and Reinhold Schneider,   Optimization Problems in Contracted Tensor Networks, 2012

In this paper, a greedy algorithm that can find a structure of a certain class of tensor networks is proposed. The algorithm consists of bi-level optimization, where tensor network structure is optimized in the outer loop and tensor decomposition is computed to approximate a given tensor in the inner loop. The tradeoff between error and the number of parameters of the proposed algorithm is empirically compared with synthetic data, image compression, and neural network compression.