On Tensor Train Rank Minimization: Statistical Efficiency and Scalable Algorithm
Tensor train (TT) decomposition provides a space-efficient representation for higher-order tensors. Despite its advantage, we face two crucial limitations when we apply the TT decomposition to machine learning problems: the lack of statistical theory and of scalable algorithms. In this paper, we address the limitations. First, we introduce a convex relaxation of the TT decomposition problem and derive its error bound for the tensor completion task. Next, we develop a randomized optimization method, in which the time complexity is as efficient as the space complexity is. In experiments, we numerically confirm the derived bounds and empirically demonstrate the performance of our method with a real higher-order tensor.
This paper looks at the tensor train (TT) decomposition as an efficient storage method for tensors with statistical guarantees.
Traditional methods for tensor decomposition include Tucker decomposition [29] and CP decomposition. The advantage of TT decomposition is that it can avoid the exponential space complexity of Tucker decomposition. However, its statistical performance is less understood, which the authors attempt to address in this paper.
In addition, the authors provide an efficient alternative to existing TT algorithms.
It’s interesting to note that Tucker and TT decompositions have complementary bottleneck - One has space complexity issues and the second has computational complexity issues.
The authors look at the problem of tensor completion which is an extension of the matrix completion problem that has been extensively researched in the literature.
In matrix completion problem, the standard assumption made is that the matrix is low-rank so that the problem becomes well-posed. This assumption is also observed to be the case in practical applications such as recommender system.
The authors make a similar observation for the tensor to be estimated (i.e. a low-rank tensor). Just as nuclear norm/schatten-p norm is used a relaxation to the rank matrix, the authors propose the Schatten TT norm as a convex relaxation of the TT rank of a tensor.
Comments:
- The authors mention that the TT rank is a tuple in section 2, while mentioning later in section 6 that it can be described by a single parameter, making the definition confusing.
- The problem formulation (4), the algorithmic approach (section 3.1) all mimick the ideas in matrix completion literature. The innovation is more to do with the appropriate representation of tensors while extending these ideas from the matrix completion literature.
- Even in the matrix factorization literature, the scalable methods are the ones that already assume a low-rank factor structure for the matrix to be completed to save space and computation. For tensors, it is all the more imperative to assume a low-rank factor structure. The authors do this in (6) to save space and time.
- Theorem 1 is quite interesting and provides a more tractable surrogate for the TT schatten norm.
- The statistical results are a new contribution for tensor completion, although the assumption of incoherence (Assumption 2) and subsequent proofs are by now very standard in the M-estimation literature.
- The authors use an ADMM algorithm again for solving (6) in section 4.2. It is not clear this would have a better advantage as compared to just the simpler alternating minimization over the TT factors of the tensor. It is not clear if the convergence of ADMM to a local minima for non-convex problems with multiple factors is proven in the literature. The authors don’t cite a paper on this either. On the other hand, it is easy to see that the simpler alternating minimization (keeping other factors fixed)
converges to a local optimum or a critical point. The authors don’t discuss any of these details in 4.2. 
- The number of samples needed for statistical convergence is in the worst-case the the product of the dimensions of the tensor. Perhaps a better result would be to show that the sample complexity is proportional to the true TT rank of the tensor? The authors don’t mention any discussion on the lower-bound on the sample complexity in the paper, making the goodness of the sample complexity bound in Theorem 5 questionable.
Overall, the paper presents an interesting investigation of the TT decomposition for tensors and uses it in the context of tensor completion with statistical guarantees. It is not clear if the algorithm used for alternating optimization (ADMM) is actually  guaranteed to converge though it might work in practice. Also, the authors don’t discuss the goodness (what’s a good lower bound?) of the sample complexity bounds derived for their algorithm for tensor completion. The approach to modeling, algorithm development, scalability and statistical convergence mimicks that taken for matrix completion - However, the authors do a good job of combining it all together and putting their approach in perspective with respective to existing algorithms in the literature.