Fitting Low-Rank Tensors in Constant Time
In this paper, we develop an algorithm that approximates the residual error of Tucker decomposition, one of the most popular tensor decomposition methods, with a provable guarantee. Given an order-K tensor X ∈ R N1×···×N K , our algorithm randomly samples a constant number s of indices for each mode and creates a "mini" tensorX ∈ R s×···×s , whose elements are given by the intersection of the sampled indices on X. Then, we show that the residual error of the Tucker decomposition ofX is sufficiently close to that of X with high probability. This result implies that we can figure out how much we can fit a low-rank tensor to X in constant time, regardless of the size of X. This is useful for guessing the favorable rank of Tucker decomposition. Finally, we demonstrate how the sampling method works quickly and accurately using multiple real datasets.
Motivated by the problem of selecting an appropriate Tucker rank for low-rank tensor approximation, the authors provide an algorithm for estimating the RMSE of a tensor at a given Tucker rank. The algorithm is simple: randomly sample a subset of the indices in each mode, restrict to the resulting tensor, and compute the RMSE for the given Tucker rank of this smaller tensor. 
Their theory argues that the number of samples needed to get a good additive error approximation to the RMSE at a given Tucker rank depends on intrinsic parameters of the problem rather than the dimensions of the tensor: in particular, on the order of the tensor, the largest magnitude entry in the tensor (its spikiness), the spikiness of the Tucker core tensor of the original tensor, and the spikiness of the Tucker core tensor of the sampled tensor. 
The experimental results are impressive, and show that not only does this algorithm provide good estimates of the RMSE at given Tucker ranks (compared to the HOOI baseline), it also preserves the ordering of the Tucker ranks by the RMSEs this achieve. The latter point is crucial for model selection. 
This work is interesting and worth publishing in NIPS because it tackles the problem of rank selection for low-rank tensor approximation in a novel way, provides theoretical guarantees that seem reasonable, and the resulting algorithm is both fast and does a good job of rank selection. The main drawback of this paper is that the theory is presented in a non-intuitive manner that makes it hard to understand the connection that the authors draw between tensors and dikernels and how it is useful in establishing the main result (I did not read the supplementary material).
- I would like to see the authors address the dependence on the spikiness of the Tucker core tensor of the subsampled tensor: is there a reason this should be here, or can it be removed? can this spikiness be bounded in terms of properties of the original tensor, or can it be arbitrarily poorly behaved?
- It would be useful to state your theorem 3.4 for a matrix first, so the readers can use their experience in that domain to understand the quantities involved in your bounds 
- The argument in line 162 that Lemma 3.3 implies the following equation is not clear to me, since it seems to ignore the effect of the measure-preserving bijection. I did not check the supplementary material to see if this argument is made clearer, but if so, please state this in the paper.
Another point:
- I would like to see bold and italicization in Tables 2--4 to indicate the best and second best performing methods, as is standard