Venue: NeurIPS 2022 Conference

Reviews:

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 work proposes an algorithm for simultaneous tensor decomposition and clustering using the alternating least squares approach. The proposed method is accompanied by a complexity and convergence analysis. Experimental studies on both synthetic and real-world datasets demonstrate the effectiveness of the proposed method in clustering multiway array data.
strengths_and_weaknesses: Strengths:
1. Paper is well-written and easy to follow.
2. The proposed method is well motivated.
3. The proposed method is presented as a concise pseudocode and it is easy to follow.
4. Complexity analysis shows the proposed method's cost is similar to that of ordinary ALS, showing that it is practically applicable.
5. Section 3.2 on how to choose regularization weights shows that these vital hyperparameters are chosen systematically from the data and not heuristically.

Weakness:
1. Missing detailed intuition behind the reason for choosing a CP model as opposed to a Tucker model for example.

questions: 1. Why is a CP model chosen over other tensor decomposition models? Please elaborate.
2. Is the CP assumption relevant on real-world datasets?
3. The paper claims that employing orthogonalization in ALS avoids local minima and speeds up convergence. Although empirical evidence of this general statement it provided in previous works, does this hold in this setting where ALS is employed for clustering? Please provide intuition.


limitations: The paper discusses a couple of limitations of this work in section 6 and aims to address them in future work.
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 tackles the tensor multi-mode clustering problem. The authors model the tensor to cluster as the sum of two terms, the signal which admits a rank-K CANDECOMP/PARAFAC (CP) decomposition, and some noise. They establish a link between the CP decomposition factors and the means of the clusters from the corresponding modes to propose the core optimization problem described in the paper. They aim to approximate as closely as possible the tensor by a rank-K CP decomposition, with a generalized Lasso penalty that limits the number of unique rows in the CP decomposition factors. An Alternating Least Squares (ALS) strategy is used to solve the optimization problem one factor at a time. An orthogonalization step is added before each ALS step, and a Fuse operator is applied after the ALS step.
The algorithm is presented with convergence guarantees, and the proposed approach is compared with other tensor mode clustering methods on both simulated and real datasets. The authors also explain how to choose every parameter of the proposed algorithm.
strengths_and_weaknesses: ### Strengths
1. The paper is clear and well written. The progression is logical and the choices made are well justified.

2. The proposed approach is compared favorably with concurrent methods on simulated and real datasets.

3. Theoretical convergence properties of the given algorithm are derived.

### Weaknesses
4. I have concerns about the proof of Theorem 1. See the section **Questions** below.

5. No code is given to reproduce the results.

**Update after rebuttal**: the authors have provided code (although I did not have time to go through it) and addressed my concerns regarding the proof of Theorem 1. I think that the clarity of the proof can still be improved, but the authors are working on it, and I have good hope that they will manage to do so in the given amount of time.
questions: I start with an essential question determining my acceptance of the paper.
Please correct me if I am wrong, but it seems that the proof of Theorem 1 bites its tail. Indeed, Theorem 1 gives an upper bound on the distance between the true and the estimated factors. However, its proof is based on Lemma 3, which assumes this same upper bound. Furthermore, it is written in Lemma 3 that this assumption can be made "without loss of generality". I may be missing something here, so please enlighten me.

I will now ask some questions, give suggestions to improve readability and point out mistakes or typos.
- Could it be possible to assess the validity of the A1-A4 assumptions on a given dataset? Were they all valid on the simulated datasets?
- General remark: it would help the reader if different indices were used for the rows and the columns. For instance, use $k$ for columns and $i$ for rows: $\mathbf A_{:k}$ and $\mathbf A_{i:}$.
- Line 71: the definition of the spectral norm should be $ \Vert \mathcal Y \Vert = \text{max}_{\Vert \mathbf u_1 \Vert_2 = \Vert \mathbf u_2 \Vert_2 = \Vert \mathbf u_3 \Vert_2 = 1} \mathcal Y(\mathbf u_1, \mathbf u_2, \mathbf u_3)$.
- Line 79: "rank-K CP decomposition" and no closing parenthesis at the end of the line.
- Line 80: "unit ~~one~~ norm".
- Line 121: it should be [...] $+ \lambda \Vert \boldsymbol \Delta \mathbf u \Vert_1$. $\boldsymbol \Delta$ is also implicitly defined as specific matrices per mode were previously introduced.
- Line 169: $\gamma$ is used for the signal ratio, there is no possible confusion with the regularization parameters, but maybe another symbol should be preferred.
- Line 170: in A4, constant $M$ has not been introduced before.
- Line 172: "on **the** rank $K$".
- Line 191: observation made that large $\gamma$ results in lower error bounds seems wrong according to the bound given in Theorem 1.
- Line 200: what does the condition on $w_\text{min}$ means? Is it a high signal-to-noise ratio condition? Was it verified in the simulations?
- Lines 256-257: the motivation for adding orthogonality was, according to line 119, to get more rapid convergence, but here, a concern is addressed that this may increase the number of iterations. Talking about verification in lines 256-257 would be more logical.

- Appendix line 65, on the second line of the equation defining $\Delta$ (maybe another symbol would be a good choice not to get confused with $\boldsymbol \Delta$): why does this become an upper bound with $\mathbf A_{: i}$ replaced with $(\mathbf A_{: i} + \hat \xi_i)$?
- Appendix line 68 (and after): $II_{11}'$ is used but never introduced. It happens after with different quantities.
- Appendix line 71, on the first line of the equation: $\mathcal Y^*$ should be replaced with $w_l$.
- Appendix line 73, on the first of the equation: $w_l$ is missing.
- Appendix line 79: indices are wrong. It should be $j_1$ for the $\mathbf A$ terms and $j_2$ for the $\mathbf B$ terms. I get the idea of the majorization, but it is not well-written: the sums have been removed, but there are still terms in $j_1$ (and normally $j_2$) appearing in the upper bound.
- Appendix line 83, equation 11: the term $2 w_\text{max} \rho$ supposes that $j_1 \neq j_2$, but we could have the equality.
- Appendix line 84, the whole bound should be multiplied by $((K - 1) \Delta)^2$ and the last term is $(K - 2) \rho^2 w_\text{max}$.
- Appendix line 146: $\Vert . \Vert_2$.
- Appendix line 149 (and after): $\alpha^2$ turned into $\alpha$.
- Appendix line 155: I do not get how the upper bound is simplified.
- Appendix line 156: I do not get the bounds on $| 1 / \kappa |$, and I do not get how the upper bound is simplified.
limitations: The authors identified that their convergence guarantees were valid for the real rank $K$ and that more work is needed to derive results for an estimated rank $K$. The convergence results show that if the number of samples goes to infinity and the tensor is noiseless, the true factors will be retrieved. However, it does not say anything about the algorithm reaching a stationary point. Is it possible to show, for example, that the objective function decreases monotonously?
review_title: null

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: This paper proposes a new formulation and a new ALS based algorithm for tensor clustering. Upper bound of the theoretical convergence rate of this algorithm is provided, and experimental results show that this algorithm yields more accurate clustering for multiple cases compared to existing methods.
strengths_and_weaknesses: Strengths:

- The problem of tensor clustering is important
- Detailed theoretical analysis of the algorithm, and better experimental results compared to existing work.

Weaknesses:

- As is declared in the paper: "First, the orthogonalization step is performed before each iteration of ALS, which allows for the avoidance of local optima and more rapid convergence to the true factors". There is no detailed analysis in the paper to show the advantage of this orthogonalization step. Additional experiments that compare the algorithm with orthogonalization and the one without orthogonalization would be helpful.
- The formulation (1) includes multiple hyperparameters. The choice of these hyperparameters in the paper is presented in 3.2 However, questions still remain as to 1) is the formulation robust to these hyperparameters, and 2) is there other reasonable ways to choose these hyperparameters, and discussions over them would be helpful.

-------
After rebuttal: I thank authors for the detailed response. My concerns are addressed.
questions: 
Line 70: spectrum norm formulation is wrong, I guess the authors mean max rather than min.

Line 79: There is one redundant ) at the end of this line.
limitations: There are no negative social impacts of this work.
review_title: null

Meta-review: metareview: The paper proposes a multi-mode tensor clustering method using an alternating least square algorithm. The reviewers unanimously like the paper and the content. Some reviewers have sought a few clarifications including on the proofs. Hope the authors would address them in the revised version. 
confidence: Certain
Decision: Accept