Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the error of tensor train decomposition via cross approximation is analyzed. The cross approximation of tensor train decomposition is an analog of CUR decomposition for a higher-order tensor. The authors derive an error bound in terms of the Frobenius norm where the observation noise is taken into account. Numerical experiments are conducted to evaluate the actual dependency between the error and other parameters such as noise level and rank.  
strengths_and_weaknesses: Strengths 
1. A technically solid result is provided. 
1. Mathematical notation is consistently used and easy to follow.

Weaknesses
1. The motivation to develop the Frobenius norm-based analysis is ambiguous. See Question 1.
2. The scope of this study (cross approximation of tensor train decomposition) seems a bit limited to the NeurIPS community. See Question 2.
3. The derived bound is not fully examined in the numerical experiments. See Question 3.



questions: ### Question 1
According to Lines 61--62 in Introduction, the main motivation to evaluate the error based on the Frobenius norm is that the prior studies only provide "element-wise error bound" and "when one extends these element-wise results to the entire tensor, the Frobenius norm error bound grows exponentially with the order of the tensor". However, the derived bound (6) contains \epsilon, which is the Frobenius norm between observed and approximated tensors. For example, if each element of the residual tensor follows standard normal, \epsilon becomes a square root of a xi-square variable, and its mean value increases exponentially w.r.t. the order of the tensor. In the end, the derived bounds do not resolve exponential dependence. If I misunderstood something, please correct me. 

### Question 2
In Introductions, several applications of tensor train decomposition and CUR matrix decomposition. However, as far as noticed, no specific application of "cross approximation (CUR) of tensor train decomposition" is provided. Could you provide a few examples for that, especially the applications in the machine learning literature?

### Question 3
I'm not convinced that the experiments of Figure 1 prove the correctness of the derived bound (6). For example, (b) doesn't exhibit the logarithmic curve w.r.t. N and (a) doesn't show the linearity in terms of r. I suspect this is because the problem size is not large enough. As a sanity check, I highly recommend conducting experiments on a larger scale so that we can clearly see the derived relationships numerically. 

### Question 4
The norm that appears in the definition of \kappa seems undefined. 
limitations: See Questions above.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper considers the problem of tensor train decomposition. It provides theoretical guarantees of cross approximation in terms of the Frobenius norm for both exact and noisy measurements. Numerical experiments are included to validate the theories.
strengths_and_weaknesses: Strength:
Overall, the paper is easy to read and the literature review is comprehensive. Under certain conditions, the theoretical guarantees improve upon the prior art.

Weakness:
As stated in the abstract and introduction, the main motivation of this work is that the existing element-wise approximation accuracy guarantees lead to loose bounds. However, the current paper only shows its own upper bounds and there is no comparison with existing results or minimax lower bounds. As a result, it is not obvious to me if it indeed leads to better theoretical guarantees. I believe it would largely improve the quality of the paper either by comparing the results with the prior works both theoretically and numerically, or by establishing the matching lower bounds to show the tightness of the upper bounds.
questions: 1. In theorem 2, it seems that the upper bound (6) will blow up if $\kappa$ is a constant, which happens when $\kappa$ increases with $d_1, \dots d_N$ and $N$. In this case, the current bound may be worse than that obtained by directly multiplying the entrywise bound by $\sqrt{d_1 \dots d_n}$. Authors should include more discussions about $\kappa$. In addition, as discussed in "Weakness", I think authors should compare the bounds with existing works, and this also applies to Theorems 3-4.

2. As one can expect, the notations will be messy in tensor papers. It would make it more accessible to readers if authors can summarize the key notations in a section. 
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Tensor train (TT) application is a feasible approach to generalize tensor information. This paper discussed the cross approximation error for TT decomposition, where it generalize the upper bound for the decomposition error of the entire tensor and proved the cross approximation  is stable that does not grow exponentially with tensor order.
strengths_and_weaknesses: Strengths:
1. This paper orchestrated a comprehensive proof toward the tensor train decomposition with cross approximation. Both tensor train decomposition and cross approximation are well-known techniques in the field.
2. Experimental analysis revealed that the error of the decomposition is stable with the increase of tensor order.  
3. The author also introduce the tensor train decomposition and cross approximation in detail and illustrated their differences with related methods.

Weaknesses:
1. Full disclosure, I am not an expert in this field. On top of everything, I am not able to evaluate the significance of the proof. Somehow, I feel it is rather intuitive that error did not grow exponentially is because the decomposition scheme of the tensor train decomposition. I.e., irrespective of the actual decomposition method, i.e.cross approximation in this paper, the tensor train decomposition scheme will restrain the exponential grow of the error.
2. I also have a hard time understand the proof. Staring with the proof of theorem 1. Does it mean, as long as rank of U and A are the same, the column space of R can be represented by U. And more confusing to me, C U R are all retrieved from A itself. I understand if two matrices have the same rank, we probably can have same set of columns or rows to represent the column and row space of these two matrices. But does it still hold, when all the decomposition matrices, C U R are all retrieved from the same matrix A? I am not very sure about this. 
3. Does the tensor train decomposition robust towards permutation? It looks like what the decomposition doing is to fold the tensor into a big matrix. During the process, it will lose track of the structure of the tensor. While permutating row, column, order of the tensor, does the decomposition result will be the same?
questions: Please see above.
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides the error analysis for the entire tensor, given clean or noisy measurements. Furthermore, it sheds light on how to sample the tensors for better approximation error. The results also show that the approximation error may not grow exponentially with the order of the tensor, implying more possible usefulness in quantum applications.
strengths_and_weaknesses: This paper is well-supported by theoretical results as well as numerical experiments. 

It provides the first error analysis for TT cross approximation that goes beyond element-wise bounds. The significance herein is that plainly applying element-wise results will yield an exponential growth in errors, and may imply a false sense of lack of accuracy. 
The authors have done a good job walking readers through the motivation, definitions, and theoretical results. The technical contribution is self-evident.
questions: I believe that the authors have already sufficiently answered my questions in the paper, including the error analysis in the presence of noises and the gap between an optimal cross approximation and any approximation. It would be better if the author can provide an example showing how Theorem 3 helps in selecting rows and columns to sample. While the authors have listed the optimal strategies for selections as a future direction, it would be nice if the authors can give some intuitions at a high level. It would help the readers better assess the theoretical implication and usefulness. Also, could the authors provide some intuitions of why the truncated pseudo-inverse could lead to better performance than the (pseudo-)inverse for TT cross approximation? Is it just because of the conditioning numerical stabilities?

limitations: NA.
review_title: null

Meta-review: metareview: The reviewers agree that the theoretical result shown in the paper improves upon prior art and that the experiments are compelling.

All comments and concerns of the reviewers have been well addressed by the authors.

confidence: Certain
Decision: Accept