Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose an Alternating Least Squares (ALS) scheme for fitting the Tucker tensor decomposition, based on sketching techniques. In particular, the proposed strategy is to update one of the factor matrices and the core tensor during each iteration, through the use of sketched rank-constrained linear least squares solvers. The theoretical analysis suggests that leverage score sampling may be more accurate than TensorSketch technique, given the same sketch size budget. However, the authors expose that with standard random initializations for factor matrices, leverage score sampling performs poorly on tensors with high coherence; and introduce the randomized range finder (RRF) algorithm so as to provide a better initialization for the factor matrices, leading to better empirical performance.
main_review: Strengths:
- The problem is definitely an important one
- Several contributions across both theoretical and methodological results

Limitations:
- Very limited experimental evaluation and discussions on real data
- More extensive intuition behind the RRF algorithm would be necessary
- No discussion exists regarding what is the real-world challenge being tackled through the use of tensor decomposition on the real image datasets

My primary concern related to the submission is that the experimental evaluation related to real datasets is not convincing enough. Very limited discussions (if any) exist regarding the Figures 1d and 1e and it's not clear what should the reader consider as the main message being conveyed.

----
I acknowledge having read the authors' response and my score remains the same; while the authors acknowledge the limitations raised around the real-data experiments, those are not sufficiently addressed based on their response.
limitations_and_societal_impact: There is no such Section or discussions around that in the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies faster tensor decomposition algorithms using randomization. It studies both Tucker and CP tensor decomposition algorithms, both of which solve a sequence of least squares regression problems. Each of these problems are over-constrained, and thus amenable to randomized dimensionality reduction approaches. These methods were implemented using standard numerical packages (NumPy), and tested on both real and synthetic data sets. They obtain significantly faster convergence, as well as lower costs per iteration.
main_review: Tensor factorization and approximation is a fundamental subroutine in learning algorithms. The use of randomization to speed up numerical routines is also a topic that has received much attention. However, I'm not aware of too many hollistic examinations of how to brining randomized tools for matrices to tensor settings, and this work shows significantly more can be done than simply accelerating the linear subroutines on matricizations. I believe some of the ideas introduced may be broadly applicable to other numerical problems on tensors, or even other non-linear numerical problems. So this result should be of wide interest to those working on efficient numerical primitives.

I thank the authors for addressing my concerns, and discussing avenues for incorporating them in future works. However, I feel obligated to take these concerns into account in evaluating the current submitted version.
limitations_and_societal_impact: A general issue with empirically comparing tensor factorization routines is that the ground truth is unclear, unless the data is synthetic. The experiments seem to show that the proposed new algorithms converge to the same ground truth as non-randomized CP/Tucker. So I'm a bit worried that the 22% increase in relative decomposition residue might be misinterpretted as final residue, instead of at the intermediate iterations.

Also, usually a key motivation for using randomized methods is to improve time/space efficiency. This seems to be underemphasized (at least compared to residues).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This is paper presents a new randomized sketching algorithm for computing a low rank Tucker and CP decomposition of tensors. The prospered method is based on using sketching to solve the rank-constrained linear least squares subproblems that appear in the popular alternating least squares (ALS) method. Theoretical analysis is presented that give the sampling complexity needed to solve each rank-constrained subproblems to a certain relative error guarantee. Results are presented for two types of sketching, TensorSketch and leverage score sampling. The rank-constrained linear least squares is solved using the randomized SVD. Many numerical results are presented that illustrate the performance of the proposed method.
main_review: The paper presents an interesting new randomized sketching approach to solve the low rank tensors decomposition problem. The paper is well-written and the results are interesting. A randomized  approach that approximately solves the rank-constrained problem (instead of the relaxed variants) seems novel and will be useful in many applications. Numerical results demonstrate improve performance results using the proposed method. 

However, I have the following comments about the paper:
1. Certain aspects of the paper are not clear and can be included to improve the paper. E.g., 
Does the analysis extend to different dimensions and ranks along different modes? How does the sampling complexity and computational cost compare to others existing randomized methods?  How large in the constant in O(\epsilon) relative error?
How accurately is line 11 in the Algorithm solved. How does the proposed method differ from the other randomized approaches such as the one in [38]. Note that the proposed method will be more expensive (by a factor of mR^n) than some of the other randomized method that solve relaxed versions of the LS problem.


2. Numerical results: The numerical experiment results section can be further improved. Computational cost comparison can be provided. Also, results are presented wrt. fitness. It would be interesting to see the approximation error for the factor computed using the different methods (as in solve the ALS completely and report the approximation error for the decomposition).

3. Minor Comments:
i. Many notations are not defined before usage. Having a small subsection on Notation will be helpful. Readers not familiar with tensor algebra might find it difficult to follow otherwise.
ii. Page 3, line 128, mostly widely --> most widely
limitations_and_societal_impact: There does not seem to be a discussion on the limitations and potential negative societal impact of their work in the paper.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposed a fast and accurate sketching based ALS algorithm for Tucker decomposition. The method is composed of a sequence of sketched rank-constrained linear least squares subproblems. In addition, the paper proved that the sketch sizes of TensorSketch and leverage score sampling that are sufficient for the relative residual norm error of the problems to be bounded
by $O(\epsilon)$ with at least $1-\delta$ probability.

The experiments show that proposed algorithm is more accurate than the existing sketching based randomized algorithm for Tucker decomposition. The algorithm can also be extended to CP decomposition effectively.
main_review: The paper is well-structured and the algorithm is well supported by the theorems. The paper compared the complexity thoroughly, though there is no improvement. The numerical results verified that the proposed algorithm is more accurate than the baselines. 

The paper has the following issues.

1. In Table 2, the sketch size in ALS+TensorSketch [37] could be much smaller than proposed ALS+TensorSketch if $\epsilon$ is very small (very accurate fitting). When $\epsilon$ is small enough,  the  sketch size in ALS+TensorSketch [37]  is also much smaller than that of the proposed one.

2. Observed from Table 2, the LS subproblem cost of ALS+TensorSketch [37] is less than proposed two methods,  especially when the rank of ground-truth tensor is high.

3. The abbreviations of the proposed algorithms and the baselines are very confusing. What does TS-ref stand for?

4. In the experiments, where are the results of the two algorithms (ALS+TensorSketch and ALS+TTM) proposed in [37]?

5. The paper did not report the per-sweep cost numerically in the experiment.

6. In Figure (a), the fitness of Lev Tucker+CP dropped significantly at sweep 4. Is the algorithm unstable?

7. It is not clear why the fitness on the synthetic data are always very low, e.g. <0.4 in Figure 1(a).
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: 
This work proposes sketch based tensor decomposition algorithms for accelerating alternating least squares (ALS) based Tucker decomposition and canonical polyadic decomposition. The claim is that new sketch sample complexity bounds are derived, with improved complexity, which can help improve Tucker and CPD reduce fitting errors under the same number of samples used as some baseline sketching algorithms.


main_review: 
1.	The proposed method is feels a bit incremental. The algorithmic structure is a standard one in the tensor community. Applying sketching based techniques to reduce the dimension of the unfolded least squares problems was used in [Battaglino and Kolda 2018] for CPD, and was exploited by a number of follow-up works. Improving sketching complexity upon existing framework is indeed a reasonable direction, but the techniques used in this work seem to be standard.

2.	The claimed contribution is a bit thin---and the main claim is likely wrong. Essentially, there is one clear claimed contribution. That is, a sketching complexity characterization for rank-constrained least squares. The authors claimed that there is no papers discussing this problem without using nuclear norm approximation. This may be true. But the derivation in Appendix F is wrong.  Consider the rank-constrained least squares problem:

            X_r =arg min_{X} ||PX-B||^2,  subject to  rank(X)<=r,

The problem cannot be solved by first computing unconstrained least squares and then projecting the solution to a rank-r matrix via SVD. The entire proof seems to have been built upon this misconception. For example, in line 870, the authors stated that “X_r is the best rank-r approximation of X_opt” where X_opt is the unconstrained least squares solution. 

3.	Following the above comment, the RSVD-LRLS algorithm embedded in the ALS algorithm does not make much sense. The rank-constrained least squares cannot be solved by first doing least squares and then doing truncated SVD. In general, any constrained least squares problem, even with convex constraints, cannot be tackled this way. This procedure does not have any guarantees of the overall ALS algorithm. In general, ALS would need the subproblems to be either solved to a certain accuracy or at least decrease the subproblems cost with a sufficiently large amount to ensure the overall convergence; see [R1] and [R2].

[R1] Razaviyayn, Meisam, Mingyi Hong, and Zhi-Quan Luo. "A unified convergence analysis of block successive minimization methods for nonsmooth optimization." SIAM Journal on Optimization 23.2 (2013): 1126-1153.

[R2] Xu, Yangyang, and Wotao Yin. "A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion." SIAM Journal on imaging sciences 6.3 (2013): 1758-1789.


4.	The writing of this paper is a bit hard to parse or follow. It seems that too many details are buried in the supplementary material. There is a claim that “One can derive a sketch size bound that is sufficient to get … residual norm for linear least squares with general  (not necessarily rank-based) constraints (detailed in Appendix G). This bound is looser than (3.1), while applicable for general constraints.” But a close inspection on Appendix G finds that the proof there never used the constraint {C}---which is not easy to understand.

5.	Also on the representations. The bounds on Tensor sketch is also not easy to understand since R^N-1 appears in the denominator of the bounds. This essentially means that when R and N gets large, the sketching difficulty does not rely on the tensor rank or the tensor order, which is quite counter-intuitive.

6.	The authors seemed to have missed many recent developments in stochastic gradient/proximal gradient based tensor decomposition algorithms, but merely focused on sketched least squares. It was shown that if one takes a stochastic gradient view point to compute tensor decomposition, then there is no need to guarantee sketching size/complexity for each subproblem, and thus each subproblem could be updated rather inexactly using lightweight computations. There is a serious lack of discussion on this line of methods.
limitations_and_societal_impact: n/a
review_title: null

Meta-review: This work contributes sketching-based alternating least squares algorithms for fast and accurate low-rank Tucker tensor decomposition. The main novel contributions are relative-error analyses of the error in the solution of the least squares systems when leverage-score sampling or TensorSketches are used to sketch the systems. The experimental evaluation is somewhat lacking, as uses small and/or synthetic data sets, but the algorithms are shown to result in lower error than previous randomized algorithms for Tucker decompositions. 
Decision: Accept (Poster)