  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 an alternating optimization method with a randomization technique, 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.
