Adaptive Learning of Tensor Network Structures
Authors: Meraj Hashemizadeh
Michelle Liu
Jacob Miller
Guillaume Rabusseau
Venue: ICLR 2022 Submitted (2022)
Keywords: Tensor Networks
Tensor Network Topology
Structure Learning
Tensor Completion
Tensor Decomposition

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 [Li and Sun, 2020] for tensor decomposition of images (while being orders of magnitude faster) and finds efficient tensor network structures to compress neural networks outperforming popular TT based approaches [Novikov et al., 2015].

Under review as a conference paper at ICLR 2022
ADAPTIVE LEARNING OF TENSOR NETWORK STRUC- TURES
Anonymous authors Paper under double-blind review
ABSTRACT
Tensor Networks (TN) offer a powerful framework to efficiently represent very nigh-ddmensiooal 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 given task is challenging. In this work, we leverage the TN formalism to develop 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 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 tensor decomposition, tensor completion and model compression tasks demonstrate the effectiveness of the proposed algorithm. In particular, our method outperforms the tfate-of-the-art evolutionary topology search introduced in [99] 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]
INTRODUCTION
Matrix factorization ubiquitous in machine learning and data science and forms the backbone of many algorithms. Tensor decomposition techniques emerged as powerful generalization of matrix factorization. They are particularly suited handle high-dimensional multi-modal data and have been successfully applied in neuroimaging 44] signal processing
+ 33 apatio-temporal analysis [1 [
and computer vision (20). Common tensor learning tasks include tensor decomposition (finding a low-rank approximation of given tensor), tensor regression (which extends linear regression the multi-linear setting), and tensor completion (inferring a tensor from a subset of observed entries).
Akin to matrix factorization, tensor methods rely factorizing high-order tensor into small factors. However, in contrast with matrices, there are many different ways of decomposing a tensor, each one giving rise 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 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 tradeoff's between minimizing the number of parameters and minimizing 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 228 7
and has recently demonstrated its potential in machine learning for 41 developing new insights into the expressiveness of deep neural networks 4 15 and designing novel approaches to supervised 35 9 and unsupervised [34] ||| learning. Tensor networks offer a unifying view of tensor decomposition models, allowing one reason about tensor factorization in general manner, without focusing
compressing models 24
particular model.
In this work, we design a greedy algorithm to efficiently search the space 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 constraint the number of parameters. To the best of our knowledge,

---

Under review as a conference paper at ICLR 2022
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 continuous optimization of 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 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 recent evolutionary algorithm [9 for tensor network decomposition on an image com- pression 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 !
Related work Adaptive tensor learning algorithms have been previously proposed. but they only consider determining the rank(s) of specific decomposition and are often tailored to specific tensor learning task ge.g., decomposition or regression). In [I. a greedy algorithm is proposed to adaptively find the ranks of Tucker decomposition for spatio-temporal forecasting task, and in [38] an adaptive Tucker based algorithm is proposed for background subtraction. In 44)], the authors present 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 IC 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 [9 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 limited to the problem of tensor decomposition. In contrast, our method is the first to jointly explore the space of structures and (non- moon-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 2] and the notions of rank induced by arbitrary tensor networks are studied in 20
2 PRELIMINARIES
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 E Rd,,, upper case bold letters for matrices (e.g. M E Rdix and bold calligraphic letters for higher order tensors (e.g. T E R4 xd). The ith row (resp. column) of a matrix M will be denoted by M., (resp. M..). This notation extended to slices of a tensor 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 E xdixxxx, can simply be seen as a multidimensional array iT ip in [du]. n (p)). The inner product of two tensors is defined by (S, T) Enn..,,, iy S Si T iip and the Frobenius norm of a tensor is defined by ||T = (T, T). The mode-n matrix product of a tensor T and matrix X E Rmxxd is a tensor denoted by T xn X. It of size d1 x... x dn-> the second mode of X, e.g. for a 3rd order tensor T, we have (T X2 X2XX)iiii =E, T injia X.zj- The
d,+1 x... dp and is obtained by contracting the nth mode of T with
nthh mode matricization of T' is denoted by T(x) E dR. xII.yn d, Tensor network diagrams allow one to represent complex operations on tensors in graphical and intuitive way. A tensor network (TN) is simply graph where nodes represent tensors, and edges represent contractions between tensor modes, ie. a summation over an index shared by two tensors. In tensor network, the arity of vertex (i.e.
the number of legs of a node) corresponds to the order of the tensor (see Figure []] Connecting two legs in tensor network represents a contraction over the corresponding indices. Consider
2

---

Under review as a conference paper at ICLR 2022
M
d
Figure 1: Tensor network representation of vector v E RR matrix M E m and tensor
T E x
B
AB
Tr(A)
T T3
I
Figure Tensor network representation of common operation on matrices and tensors.
the following simple tensor network with two nodes: matrix A E R= and the second one vector x E RR. Since this tensor network has one dangling leg (i.e. an edge which is not connected any other node), it represents first order tensor, i.e., vector. The edge between the second leg of A and the leg of x corresponds to a contraction between the second mode of and the first mode x. Hence, the resulting tensor network represents the classical matrix-vector product, which can be seen by calculating the ith component of this tensor
The first node represents
Σ, Ai,x, = (Ax); Other examples of tensor network representations of common operations on matrices and tensors can be found Figure Lastly, is worth mentioning that disconnected tensor networks correspond to tensor products, e.g.,
network:
uv the ターj= u,V, Consequently, edge of
outer product of and with components dimension (or rank) in TN is equivalent to having no edge between the two nodes, e.g., if R we have
= Σ A Br.j AI, =
Tensor decomposition and tensor rank We now briefly present the most common tensor decom- position 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 fourth order tensor T Red xdgxdxxd4, each decomposition can be straightforwardly extended to higher-order tensors. A Tucker decomposition 66 decomposes T as the product of a core tensor g E R. RR
with four factor matrices U, R4xR,, for
1.... 4:
T = 9 X1 U1 X2 U2 X3 U3 X, U4. The Tucker rank, or multilinear rank, of T is the smallest tuple R R2. Rg. R4) for which such a decomposition exists. The tensor ring (TR) decomposi-
tion 44
25
20 expresses each component of T the trace of product of slices of four
tensors
(1)
R Roxxx XB,
g (2)
Bilixd X (3)
X and (4)) R.
((4) :....). The tensor train (TT) decomposition 26 (also known as matrix product states in the physies community) is particular case of the tensor ring decomposition where Rg must be equal Similarly to Tucker, the TT and TR decompositions naturally give rise to associated notion of rank: the TR rank (resp. TT rank) the smallest tuple (Ro, R1, R2, Ra) (resp. (R1, R2, Ra)) such that TR (resp. TT) decomposition exists.
T $1.22.fa.1a Tr
(Ro is thus omitted when referring to the rank of a TT decomposition).
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 a decomposition and its number of parameters is different for each model. Letting p be the order of the tensor, 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 Rpd for TT and TR. One can see that the Tucker decomposition not well suited for tensors of very high order since the size of the core tensor grows exponentially with p.
3

---

Under review as a conference paper at ICLR 2022
Tucker
Tensor Train
Tensor Ring
Hierarchical Tucker
Figure 3: Tensor network representation of common decomposition models for a 4th order tensor.
A GREEDY ALGORITHM FOR TENSOR NETWORK STRUCTURE LEARNING
3.1 TENSOR NETWORK OPTIMIZATION
We consider the problem of minimizing a loss function C IRdxx...x + R w.r.t tensor W efficiently parameterized
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 W E Idd x=*x,,, where each of the factors has one dangling leg corresponding to one of the dimensions dj (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 (ssijsss where each R,, 2 is the dimension of the edge connecting the ith and jth nodes of the TN (for convenience, we assume R, = R if i j). If there is edge between nodes and j in a TN, R. is thus equal to (see Section 2 A TN decomposition of W R& xd is then given by collection of core tensors ((1)
(P)) where each g is of size R1, X ... x R4-1, x d, x Ra,++1 X... x R..p. Each core tensor is of order but some of its dimensions may be equal to one (representing the absence of edge between the two cores in the TN we have
structure). We use (N(g(1) (()) denote the resulting tensor. Formally, for order 4 tensor
R
R 3
Ra.4
Σ
R R R. St
This definition is straightforwardly extended to TN representing tensors of arbitrary orders.
As an illustration, for a decomposition the ranks the tensor network representation would be such that Rıj * if and only if === 1. The problem of finding rank (21, ra) TT decomposition of target tensor T dRd, xdxxdsxd can thus be formalized as
min x glg)e perixdeee x1 g(3) g(4) ea
C( g())
(())))
(I)
where L(W) = I 2 Other common tensor problems can formalized this manner. For example, the tensor train completion problem would be formalized similarly with the loss function
being L(W)= = [ Σ dy)n
, - -T "T.."... .i,)² where C [di) x.. [dp] is the set of
observed entries of T Rd,x--x,, and learning TT models for classification (5 and sequence
modeling [1] also falls within this general formulation by using the cross-entropy or log-likelihood as 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 TN is equivalent to having edge, internal cores can be represented as cores whose dangling leg have dimension 1. Consider for example the Tucker decomposition T g X1 U1 X2 U2 X3 U3 Rd4 (M1xdxxd, xds of rank (r1. r2, r3). The tensor T can naturally be seen as fourth order tensor 7 IR Ig xds, as 9 Rixxixpxxxs U, as Ü E Rrixdıxix1 U2 as U2 E xr2xIxdxx1x1 and U3 as Üg E IRrsxxxxxss With these definitions, one can check that TN(G, U, U2 Úz) g x U, X2 U2 X3 U3 T. More complex TN structure with internal nodes such as hierarchical Tucker can be represented using our formalism in similar way. The assumption that each core tensor in TN structure has dangling leg corresponding to each the dimensions the tensor T is thus without loss generality, since suffices to augment T with singleton dimensions represent TN structures with internal nodes.
4

---

Under review as a conference paper at ICLR 2022
3.2 PROBLEM STATEMENT
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 C(TN(G . g(P))) s.t. size(g(), ((())"")...)))))))
...)))))))) SC
min
g g(,,..ggm gg)))
where C is a loss function, each core tensor g (t) is in R R1, x... 1, R4 X.. RBE, C. is bound on the number of parameters, and si size((())
g(r)) is the number of parameters of the Ri, Note that if K is the maximum arity of
TN, which is equal > d. ... 1, node in TN, its number of parameters is in O (pdRk) where d max; dl and R = maxi,j Ra.j-
Problem 2 is bi-level optimization problem where the upper level is a discrete optimization over TN structures, and the lower level is 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 [3] In the next section, we propose a general greedy approach to tackle this problem.
3.3 GREEDY ALGORITHM
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, and each core tensor g() E R ..........1.1111.. - Rt. 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 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 | In the remaining of this section, we describe the continuous optimization, weight transfer, best edge identification and node splitting procedures. For Problem 2 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 the problem of identifying the TN structure with the least number of parameters achieving a given loss threshold. For learning tasks (e.g.. TNN 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 prob- lem (line 12 of Algo. D. E.g., in our experiments on compressing neural network layers (see Section 4 we use Adam [66. For particular losses, more efficient optimization methods can be tensor completion and tensor decomposition,
used: in our experiments
use the Alternating 17 5 algorithm which consists in alternatively solving the minimization problem w.r.t. of the core tensors while keeping the other ones fixed until convergence.
Least-Squares (ALS)
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 tensors connected by the incremented edge to values close to O, while keeping all the other parameters of the TN unchanged (line 8 of Algo. [ E.g., for a tensor network of order 4, increasing the rank of the edge (1,2) by 1 is done by adding slice of size d1 x RL3 x R1,4 (resp. de x R233 x R2,4) to the second mode of (1) (resp. first mode of (2)). After this operation, the new shape of (1) will
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Greedy-TTV -N: Greedy algorithm for tensor network structure learning.
Input: Loss function Rdd Xxxxpp - RR splitting node threshold
1: I/ Initialize tensor network to a random rank one lensor and optimize loss function.
2: Rag + 1 for S i
3: Initialize core tensors g E R
RR. X.., L:xd, x Re.i xx.xx Ra randomly
4: (g(1)... "( g( + optimize C(TN(g ,.. (((,)) w.r.t g(v),.. (p)
5: repeat
6:
(i.j) + find-best- (g ,(())
7:
I/ Weight transfer
g (()) ( for k E [p] \\ {i,s}: R R +1
8:
9 + add-slice(g(), .) 11 add new slice the jth mode of (())
9:
g g add-slice(gPi
Il add new slice the ith mode of g()
11:
I/ Optimize new lensor network structure
(g ..... .()))) + optimize C(TN(G .g(l)) from init. g0))
g
12:
11 Add internal nodes if possible (number of cores p may be increased after this step)
(g g(P)) + split-nodess(( -oodes((g))))) .... g(
14:
15:
until Stopping criterion
be d1 x (R1, + X R1,3 x R1,4 and the one of (2) will be (R1.2 2 + 1) d2 x R2.3 x R2 The following proposition shows that if these slices were initialized exactly O. 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 (k) E R x...x - xds x RR, 44, 1 x x Re.p for k E [p] be the core tensors of a tensor network and let S < S Let Rey = Res + 1 (') (i.j) and Ry.y otherwise,
and define the core tensors g (k)
E RR Ro-1 Re X... Re.p for E [p] by
gg (1) ( = (g (g))
(c (0) = [-0-
[(g and g( g( for & E [pl {i.5}
where O denotes a row vector of zeros of the appropriate size in each block matrix.
Then, the core tensors (()) correspond to the same tensor network as the core tensors (kk), ie. TN(ğ (1) .....g(7) TN( (())).
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
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 I (line 6 of Algo. D. a reasonable heuristic consists 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 d; Heye R unknowns for i E [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 the one of solving 2 least-squares problems with d, [IsEpe (i,)) R and d, [ R2 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 only computed for (and back mack-propagated through) the

---

Under review as a conference paper at ICLR 2022
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 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 common technique used in TN methods to split node into two new nodes using truncated SVD (see, e.g.. Fig. 7.b in [35)). To illustrate this technique, let xm1
M E
R
mm x x*2 be the core tensor associated with node in TN we want to split into two
new nodes A E IR X and B E TR X x the first two legs of AA (resp. B) will be connected connected 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) UDV " x" (the matricization of M having modes 1 and 2 as rows and modes and as columns), and letting A(3) = U E Rr m2 and (3) = DVT T E R2 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.
to the core tensors that
M/1
1/12
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 ( for k [p] (line 14 Algo. I For each matricization, we split the corresponding node only if there are enough singular values below a given threshold E 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 ! as well as its complexity are given in the Appendix B
4 EXPERIMENTS
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 x 7 7 x 7 with the following TN structures:
TT target tensor
TR target tensor
Tucker target tensor
"Triangle" target tensor
We run Greedy TN until it recovers an almost exact decomposition (stopping when the relative error falls below 10 10-9). We compare Greedy-TN with CP, Tucker and TT decomposition (using the implementations from the TensorLy python package [8] of increasing rank 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 each iteration. Reconstruction eтrors 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 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. This experiment showcases the potential cost of model mnisspeciiiication: 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 rithms proposed in 7 and the CP and Tucker decomposition algorithms from Tensorly [88 on
We compare Greedy-TK, TN with the TT and TR alternating least square algo-
7

---

Under review as a conference paper at ICLR 2022
tensor TT tensor
TR target tensor
Tucker target tensor
Triangle target tensor
Oreebs
64
Nerdomaal
Tacler
tudker
64
359 3508
Figure 4: Evaluation of Greedy-TN on tensor decomposition. Curves represent the reconstruction error averaged over 100 runs, shaded areas correspond to standard deviations and the vertical line represents the number of parameters of the target TN. Greedy corresponds to Greedy TN without the search for internal nodes (line 14 of Algo. I while Greedy-int includes this search.
Original Image
Chserved plaets
CP (rank=366)
Tucker (2a)ke=20)
TT (rankm20) 20 90% (12249)
TR (1ank=18) 10 85% (18060
Einstein Image Completion
12 42% (201
15 90% (19209]
45-
Greedy
CP
Tucker
TT
35
TR
20
Greedy (term:5) 31.28% [ais]
Greedy (ttewa)) 25.199% (478)
Greedy (iter 12.88 [469c]
Grendy (iter31)) 50% [10000]
Greedy (iter 42) 9.45% [21375)
Greedy (tor 45) 9.47% [34300]
25
20
30
10000 15000
parameters
Figure 5: Image completion with 10% of the entries randomly observed. (left) Relative reconstruction error. (right) Best recovered images for CP. Tucker, TT and TR, and 6 recovered images at different iteration of greedy (image title: RSE% [number of parameters]).
image completion task. We consider an experiment presented in 37: the completion of an RGB image of Albert Einstein reshaped into a 6 x 10 x 10 x 6 x 10 x 10 x 3 tensor (see Rr 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 Tucke D. The relative errors as a function of number of parameters are reported in Figure 5 (left) where we see that Greedy-Th outperforms all methods. 'he best recovered images for all methods are shown in Figure S (right) along with the original image and observed pixels. The best recovery eπror (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 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 O In this experiment, the total running time of Greedy-Th 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 with error of 10.60% with
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 hyper-parametee 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 x 256 from the LIVE dataset h2 tensorize each image to an order-8 tensor of size 4 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 very poor results on the tensorized image.
8

---

Under review as a conference paper at ICLR 2022
Image
1 Log compression ratio CRJ and (RSE))
aand
0.990
Greedy
GA(rank=G) G)
GAtrank= ()
0.716 1O5 22.1000.00
0.901(0
0.600T0 113)
0.985
2.313 (5.100))))))1
10010.00000
1.3/2(0.155
1119900.133
accuracy
0.980
2
(. 167 (270000))000
1 (.268(0.171)
Greedy test
3.00D (.166) 1 000055(0.002)
1693
1,47600.15 189)
0.975
Greedy train TT test
0.874 00..000011000.00...000
0.629(0.152]
0.621 121)
0.970
3.668 0.080 ( 001)
0.026)
(.548(0.033)
TT train
6
2.205(0.097) (00000000/..3111000000 (0.170000004)
1.14100 10-1)
0.965
test
2.132 00.001115500.220.oooo
1.5)3
1.40(00.12 (20)
TR train
3.634(0..00 +0.14/00000
(679(0.085)
(.00(0
9
0.90610.188 1.161
12000
13000
14000
15000
parameters
Table 1: LLog compression ratio and RSE for 10 different images selected from the LIVE dataset.
Figure 6: Train and test accuracies on the MNIST dataset for different model sizes.
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 O, setting the greedy stopping criterion to the RSE of GA(rank=)), Greedy-IV TN also achieves a higher compression ratio than GA(rank=6): 1.085 (0.100.)28)) Our method 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 of size 1024 1024 which we represent as fifth-order tensor of size 16 x ... x 16. We use Greedy 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 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 well as TR tensorized model for uniform ranks 1 to 8 and the TT method with dropout and achieve higher accuracies than the ones reported in 244). For every model size, method reaches higher accuracy. The best test accuracy of Greedy- -evedy--T 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.422 42.4 with 14,154 parameters. At iteration 10, Greedy-Th 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.
Greedy TN (it is worth noting that we use our own implementation
Implementation details We use PyTorch [2 and the NCON function Greedy-TN. TN. For the continuous optimization step, 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 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.
30 to implement
the Adam [16] optimizer with learning
5 CONCLUSION
We introduced 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 119, 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 TNN structures suited for efficient compression of larger neural network models.

---

Under review as a conference paper at ICLR 2022
REFERENCES
[1] Mohammad Taha Bahadori, Qi Rose Yu, and Yan Liu. Fast multivariate spatio-temporal analysis via low rank tensor learning. In Advances in Neural Information Processing Systems, pp. 1491-34999 2014.
[2] Jonas Ballani and Lars Grasedyck. Tree adaptive approximation in the hierarchical tensor format. SIAM journal on scientific computing, 36(4): 1615):1141--11431,, 2014.
[3] A. Cichocki, R. Zdunek, A.H. Phan, and S.I. Amari. Nonnegative Matrix and Tensor Factor- izations. Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. Wiley, 2009.
[4] Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor analysis. In Conference on Learning Theory, pp. 698-728, 2016.
[5] Pierre Comon, Xavier Luciani, and André LF De Almeida. Tensor decompositions, alternating least squares and other tales. Journal of Chemometrics: Journal of the Chemometrics Society, 23(7-8):393-405, 2009.
[6] David Elieser Deutsch. Quantum computational networks. Proc. R. Soc, Lond. A, 425(1868): 73-90, 1989.
[7] Richard P Feynman. Quantum mechanical computers. Foundations of physics, 16(6):507-531, 1986.
[8] Timur Garipov, Dmitry Podoprikhin, Alexander Novikov, and Dmitry Vetrov. Ultimate ten- sorization: compressing convolutional and fo layers alike. arXiv preprint arXiv:1611.03214, 2016.
[9] Ivan Glasser, Nicola Pancotti, and J Ignacio Cirac. Supervised learning with generalized tensor networks. arXiv preprint arXiv:1806. 05964, 2018
[10] Lars Grasedyck and Sebastian Krämer. Stable als approximation in the tt-format for rank- adaptive tensor completion. Numerische Mathematik, 143(4):855-004, 2019.
[11] Zhao-Y Yu Han, Jun Wang, Heng Fan, Lei Wang, and Pan Zhang. Unsupervised generative modeling using matrix product states. Physical Review X. 8(3):03 2018.
[12] Kohei Hayashi, Taiki Yamaguchi, Yohei Sugawara, and Shin-ichi Maeda. Einconv: Exploring unexplored tensor decompositions for convolutional neural networks. In Advances in Neural Information Processing Systems, 2019.
[13] Christopher J. Hillar and sek-Heng Lim. Most tensor problems are np-hard. Journal of the Association for Computing Machinery, 60(6), 2013.
[14] Pavel Izmailov, Alexander Novikov, and Dmitry Kropotov. Scalable gaussian processes with billions of inducing inputs via tensor train decomposition. In International Conference on Artificial Intelligence and Statisties, pp. 726-735, 735, 2018
[15] Valentin Khrulkov, Alexander Novikov, and Ivan Oseledets. Expressive power of recurrent neural networks. In International Conference Learning Representations, 2018.
[16] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. 3rd International Conference on Learning Representations, ICLR, 2015.
[17] Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51 (3):455-500, 2009.
[18] Jean Kossaifi, Yannis Panagakis, Anima Anandkumar, and Maja Pantic. Tensorly: Tensor learning in python. The Journal of Machine Learning Research, 20(1):925-930, 2019.
[19] Chao Li and Zhun Sun. Evolutionary topology search for tensor network decomposition. In International Conference Machine Learning, 2020.
10

---

Under review as a conference paper at ICLR 2022
[20] H. Lu, K.N. Plataniotis, and A. Venetsanopoulos. Multilinear Subspace Learning: Dimension- ality Reduction of Multidimensional Data. CRC Press, 2013.
[21] Oscar Mickelin and Sertac Karaman. Tensor ring decomposition. arXiv:1807.02513, 2018.
arXiv preprint
[22] Jacob Miller, Guillaume Rabusseau, and John Terilla. Tensor networks for language modeling. arXiv preprint arXiv:2003.01039, 2020.
[23] Alexander Novikov, Anton Rodomanov, Anton Osokin, and Dmitry Vetrov. Putting MRFs tensor train. In International Conference on Machine Learning, pp. 811-819, 2014.
[24] Alexander Novikov, Dmitrii Podoprikhin, Anton Osokin, and Dmitry P. Vetrov. Tensorizing neural networks. In Advances in Neural Information Processing Systems. pp. 442-450, 2015.
[25] Román Orús. A practical introduction tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349: 149-117-158, 2014.
[26]
Ivan V. Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):
2295 2317, 2011.
[27] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
[28] Roger Penrose. Applications of negative dimensional tensors. Combinatorial mathematics and its applications, 1:221-244, 1971.
[29] David Perez-Garcfa, Frank Verstraete, Michael M Wolf, and Ignacio Cirac. Matrix product state representations. Quantum Information and Computation, 7(5-6):401-433 2007.
[30] Robert NC Pfeifer, Glen Evenbly, Sukhwinder Singh, and Guifre Vidal. Ncon: A tensor network contractor for matlab. arXiv preprint arXiv: 2014.
[31] Guillaume Rabusseau and Hachem Kadri. Low-rank regression with tensor responses. In Advances in Neural Information Processing Systems, pp. 1867-1875, 2016.
[32] H.R. Sheikh, M.F. Sabir, and A.C. Bovik. statistical evaluation of recent full reference image quality assessment algorithms. IEEE Transactions on Image Processing, 15(11)3344034511 2006. doi: 10. 10.11099/1P.2000..885 881959.
[33] Nicholas D Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E Papalex- akis, and Christos Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions on Signal Processing, 65(13):351133882 2017.
[34] E. Miles Stoudenmire. Learning relevant features of data with multi-scale tensor networks. Quantum Science and Technology, 3(3):034003, 2018.
[35] Edwin Stoudenmire and David J. Schwab. Supervised learning with tensor networks. In Advances in Neural Information Processing Systems, pp. 4799-4807, 2016.
[36] Ledyard R Tucker. Some mathematical notes three-mode factor analysis. Psychometrika, 31 (3):279-311, 1966.
[37] Wenqi Wang, Vaneet Aggarwal, and Shuchin Aeron. Efficient low rank tensor ring completion. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5697-5705, 2017.
[38] Senlin Xia, Huaijiang Sun, and Beijia Chen. A regularized tensor decomposition method with adaptive rank adjustment for compressed-sente -eneee----eedddddinnn background subtraction. Signal Processing: Image Communication, 62: 163, 2018.
11

---

Under review as a conference paper at ICLR 2022
[39] Yinchong Yang, Denis Krompass, and Volker Tresp. Tensor-train recurrent neural networks for video classification. arXiv preprint arXiv:170..0176, 2017.
[40] Ke Ye and Lek-Heng Lim. Tensor network ranks. arXiv preprint arXiv:/801.02662 2018.
[41] Rose Yu, Guangyu Li, and Yan Liu. Tensor regression meets gaussian processes. In International Conference on Artificial Intelligence and Statistics, pp. 482 4900, 2018.
[42] Qibin Zhao, Liqing Zhang, and Andrzej Cichocki. Bayesian cp factorization of incomplete tensors with automatic rank determination. IEEE transactions pattern analysis and machine intelligence, 37(9):1551-1763, 2015.
[43] Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, and Andrzej Cichocki. Tensor ring decomposition. arXiv preprint arXiv: 1606:05533035 2016.
[44] H. Zhou, L. Li, and Zhu. Tensor regression with applications in neuroimaging data analysis. Journal of the American Statistical Association, 108(502):540-552 2013.
12


Reviews:
[{"review_id": "eJuU3iaOWy", "reviewer": "Reviewer_7PSK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is interesting in that it presents a greedy algorithm for learning tensor network structure. The paper also discusses the relationship among different tensor representation, and the authors have a deep understanding of tensor decomposition an optimization problems. My concerns mostly lie in the design of the algorithm and experiments.\n\n1. How is the core tensor randomly initialized in Algorithm 1?\n\n2. It may be inappropriate to claim that the Tucker decomposition is not well-suited for tensors of very high order. Would reshaping a third-order tensor (RGB image) into a very high-order tensor leads to certain loss of structure information?\n\n3. The result of the image completion is not very convincing since the authors only perform experiments on one sample image with a fixed missing ratio. More experimental results should be conducted and some recently proposed tensor-based methods should also be considered. For example, \"Image Completion Using Low Tensor Tree Rank and Total Variation Minimization\", \"Tensor Completion via Nonlocal Low-Rank Regularization\".\n\n4. Could the authors also compare the computational complexity or list detailed running/training time of compared methods?\n\n5. Is the proposed method subject to the influence of noise (AWGN)? Can it be applied to the image denoising task where Tucker decomposition shows very good performance?", "summary_of_the_paper": "This paper proposes a greedy algorithm to solve the tensor network optimization problem in a heuristic manner. The major contribution of the method is the greedy algorithm to efficiently derive the tensor network structure.", "summary_of_the_review": "The paper is technically interesting, but the authors should carefully revise their experimental section to address the above concerns.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YRUWoMZW6BN", "reviewer": "Reviewer_RmTg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths \n\n1. This paper focuses on the problem of the structure determination of tensor networks, which is an important topic in tensor learning literature. \n2. The paper is clearly written and easy to follow.\n3. A practical algorithm is proposed. \n\n\nWeaknesses\n\n1. The practical values of the proposed method are not clearly shown. In the experiments, the method is applied to image and neural network (NN) compression tasks, but there are strong competitors for their applications (discrete cosine transform for image and distillation/neural architecture search for NN). Do you have any other specific applications where the proposed method will win? If not, it would be better to other venues such as linear algebra rather than machine learning. \n2. The proposed algorithm is based on heuristics and there is no theoretical guarantee. Greedy algorithms can have a property that allows evaluating the error between the optimal and obtained solutions for specific objectives (e.g. submodular function) [*]. Could you provide such an analysis?\n3. The paper is not self-contained. In Algorithm 1, the definition of the subfunction `split-nodes` is not described. The stopping criterion is also not described. \n4. It is not clearly discussed what kind of class of tensor networks is considered. In the 2nd paragraph of Section 3.1, it is said `Without loss of generality, we consider TN having one factor per dimension ...`. But this class doesn't include tensor networks in which a factor has two or more output legs or tensor networks that have hyper-edges (i.e. contraction more than two indices). I believe this violates \"the loss of generality\". \n\n\n[*] https://home.csulb.edu/~tebert/teaching/lectures/528/greedy/greedy.pdf", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper tackles an important problem and provides a handy algorithm. However, the impact of this study is not significantly presented in the machine learning context. The technical contributions are based on heuristics and not technically solid.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YKVPi3scZZP", "reviewer": "Reviewer_uoVk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main idea is a bit ad-hoc: gradually increasing the dimension of the core tensor, where the factor matrices & core tensor must be recalculated/optimized as soon as the dimension of the core tensor changes. It is obvious that such an optimization method requires very high complexity, and it's hard to have convergence guarantee. \n\nThe authors claimed that the TN also works for CP decomposition. However, the procedures in Algorithm 1 actually may not support their claim. Because there is no such a so-called core tensor in CPD. What I can image is that the core tensor in CPD is a N-D diagonal tensor. In such a case, how does Algorithm 1 gradually increase one slab to the core tensor (which will destroy the N-D diagonal structure), and guarantee the core tensor is diagonal?\n\nThe description of Algorithm is a bit unclear. In the Best Edge Selection, it says the gradient or LS is only applied to the new slice, then how to guarantee the objective to decrease without taking the remaining slices into consideration? Obviously, this is very suboptimal. \n\nLastly, to be honest, I didn't understand the section of Internal Nodes. ", "summary_of_the_paper": "This paper proposed an adaptive method that enables to optimize the best tensor network structure which can be used for tensor completion, decomposition, etc. The performance of the proposed method was tested on both synthetic and real data.", "summary_of_the_review": "Based on my own understanding, the method is not well explained. It is ad-hoc and no theoretical guarantee of its convergence. I would not recommend it for publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6UxnOv7lVV2", "reviewer": "Reviewer_yrur", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The greedy method to find the structure or rank of TN and algorithms included ALS, DMRG ...  for TNs were presented there.\nMany similar algorithms or variants have been recently proposed,  e.g., \"Adaptive Rank Selection for Tensor Ring Decomposition. 2021.\n\nIn addition, the tensor ring is indeed the tensor chain model which was proposed in 2009, 2011 by Khoromskij. The authors should give honor to the authors who first invented the model. For computations in Tensor chain and tensor networks, see Espig, Hackbusch, Handschuh and Schneider (2012a), Espig, Naraparaju, and  Schneider 2012, Huckle, Waldherr and Schulte-Herbruggen (2013), Hackbusch 2014, and Handschuh, 2015. See also Cichocki et al 2016, 2018. \nSome other publications later follow the new name of the TC model and may not be aware of the original work of the Tensor chain and algorithms for generalized TNs. \n\nThe authors use the ALS algorithm as the core algorithm for TN decomposition. This algorithm, especially for the CP and TC models, often gets stuck in false local minima and prevents the greedy method from finding a good model.\n\nThe authors show that they can recover the exact TN structure of the synthetic tensor of size 7 x 7 x 7 x 7 x 7, which admits the TC model of bond dimensions 2-3-6-5. For this example, the core tensors were generated from a normal distribution, and the TC tensor is relatively easy to decompose. \nThe authors can try the TC decomposition for the tensor of the same tensor size and bond dimensions (3-3-3-3), but the cores are generated from a uniform distribution. The latter tensor is even more challenging for TC decomposition, and most algorithms succeeded with a rate lower than 10\\%.\n\nThis is to show that most greedy algorithms cannot find the \"true\" model of a tensor (the problem is indeed NP-hard), even with known ranks.\n\nI also suggest the authors test their method for tensors associated with the multiplication of two matrices. \n\n\nFor TT, the TT-SVD or better algorithms for TT with bounded approximation error should be used.\nThe performance for TT shown in Figure 5 seems incorrect. TT with higher number parameters should give better reconstruction or lower relative error.\n\nAn example of compression of neural networks is for a very simple network with only one hidden layer and the MNIST dataset. It is known that the MNIST dataset is easy to fit and obtain excellent accuracy. The authors should try, e.g., Resnet for Imagnet dataset or CIFAR 10, CIFAR100.\n\n\n- References [17, 5] do not present ALS algorithm for Tensor network, \nbut Espig, Hackbusch, Handschuh, and  Schneider 2012.\n\n- The implementation provided in the supplementary does not support the TC model.\n", "summary_of_the_paper": "First, the idea of rank incremental method for Tensor network decomposition and determination of TN structures is not novel. \nSecond, decomposition with weight transfer is obvious and widely used in the rank incremental method. \nFor generalized tensor networks decomposition, the authors should consider the works.\n\nS.  Handschuh,  “Numerical  Methods  in  Tensor  Networks,” PhD  thesis,Facualty of Mathematics and Informatics, University Leipzig, Germany,Leipzig, Germany, 2015.\n\nMike Espig, Wolfgang Hackbusch, Stefan Handschuh, and Reinhold Schneider,   Optimization Problems in Contracted Tensor Networks, 2012", "summary_of_the_review": "The proposed method is not novel, in two contributions that authors claimed: greedy method and sharing weights\n\nDecompositions such as with CPD and TC very often encounter degeneracy and cannot find the true model even with true ranks.\n\nNNs and the considered dataset for the compression task is relatively simple and easy to compress. \nThis does not confirm the greedy algorithm works well for other difficult scenarios.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the important problem of tensor network optimization. Unfortunately the authors did not respond to the reviewers comments. Hence, several concerns remain about the proposed greedy algorithm, including its relationship with prior work and the issue of the ALS method being stuck in local minima for important classes of problems. We strongly encourage the authors to carefully examine the reviewers points and revise their work accordingly.
Decision: Reject