Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper summarizes the theoretical guarantee for the existing LRMC and LRTC algorithms, and provides the theoretical analysis for a new proposed Multi-Mode Nonlinear deep tensor factorization. The analytical results show that when n2 is larger than n1, the nonlinear DMF provides a tighter generalization bound than MF. Similar analysis has been extended to two-mode matrix factorization and multi-mode  tensor factorization. Experimental results in synthetic data and real data show better results of the proposed algorithm as compared to other algorithms in completion tasks. 
main_review: The paper analyzed the proposed non-linear multi-mode tensor factorization algorithms, and the theoretical results help to understand the gap between the linear and non-linear factorization gap. 

Some concerns are
[1] When comparing equation (6) and equation (7), some assumption regarding h seems missing. it is known that h_{L} = n1 and h_{-1}=n2, are there any assumptions needed  regarding the setups of h_{i: i = 1,..., L}? Are they bounded by r?

[2] There are some concerns about the synthetic data simulation used in the paper. It is okay to use complexed non-linear transformation (e.g. sin/exp) to verify the non-linear multi-mode tensor factorization works as expected. While, it would be better if the synthetic data can are generated the same way as the assumption (tanh activation function as used in the experiment) to verify how efficient of the algorithm in recovering a tensor with known factorization. 

summary_of_the_review: Overall, the paper is a theoretical paper and the bound analysis helps to understand the gap between classical linear factorization and non-linear factorization.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: To bridge the gap between deep learning and tensor decomposition, this paper presents two novel approaches named as two mode non-linear deep matrix factorization and multi-mode nonlinear deep tensor factorization (extension of two mode model to multi-mode scenario). The main contribution of the methods lie in full exploration of non-linearity of data in matrix and tensor factorization. To better motivate the proposed models, the authors provide theoretical analysis for why and when nonlinear deep matrix factorization outperforms linear deep matrix factorization in matrix completion. The experimental evaluation demonstrates that in some datasets, the proposed models outperform the existing models on matrix and tensor completion tasks.
main_review: Strengths:
(1) Strong theoretical analysis
(2) Clearly stating the assumptions in the proposed models

Weaknesses:
(1) Optimization procedure for the proposed models is not ver clear
(2) The applicability of the proposed models are evaluated only on matrix and tensor completion tasks which may raise doubts on usefulness of them on other downstream tasks.
(3) The experimental evaluation is not rich and strong. It is better to provide analysis on latent factors (output of matrix and tensor factorization). Besides, only a few baselines are included in the paper. More recent methods can be included as baselines for experimental evaluation. In addition, the proposed models do not consistently outperform the existing solutions on matrix and tensor completion tasks.
(4) Computational complexity analysis has not been performed elegantly for the proposed models.


summary_of_the_review: The proposed models built on top of meaningful assumptions for matrix and tensor factorization tasks which aim to address the gap between deep learning and factorization. However, there are several aspects in this paper that require improvement:

(1) The experimental evaluation is not very strong: 
(1-1)I recommend the authors to provide in depth-analysis of the latent factors using visualization methods for downstream task of matrix and tensor completion.
(1-2)The authors need to explain why the proposed models do not achieve the best performance on some datasets.
(1-3)Please include more baselines for experimental evaluation
(2) Please include more details on the optimization procedures in the paper or appendix.
(3) I suggest the authors to put computational complexity analysis of the proposed models in the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the nonlinear low-rank completion of matrices and tensors. Specifically, it first presents the theoretical results showing why nonlinear deep matrix factorization is better than the ordinary matrix factorization model. Then, it proposes a model named two-mode nonlinear deep matrix factorization to make full use of the nonlinearity of the nearly square matrices. The authors also extend this method to tensor factorization by further factorizing the factor matrices in the Tucker decomposition using the deep factorization method. Impressive results are obtained using both synthetic and real-world datasets.
main_review: Overall, this is an interesting paper, providing an important theoretical analysis of deep matrix/tensor factorizations and bridging the gap between deep learning and tensor factorization models. The paper is well written and easy to follow; the theoretical analyses are delivered clearly despite the heavy notations. The two-mode design in the proposed matrix factorization is quite unique, to the best of my knowledge. Theoretical analysis and synthetic experiments show that when data is generated according to the assumption, it outperforms baselines and achieves better generalization. The idea of incorporating deep matrix factorization into Tucker decomposition is also quite interesting.

My questions/comments are:

1) In Assumption 2, it is assumed that X is generated by $\mathbf{X}=\mathbf{U}^\top\mathbf{Q}\mathbf{V}$, I wonder what motives this assumption and are there any motivating examples in the real world to justify this assumption?

2) The sizes of the tensors used for experiments are quite small, how would the proposed model scale to a large tensor? Also, the running time of the proposed model and the baselines are not reported.

3) There are other recent nonlinear tensor completion models, e.g. CoSTCo[1]. It would be great to see relevant discussion and comparison with those recent methods.


[1] Liu, Hanpeng, et al. "Costco: A neural tensor completion model for sparse tensors." Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.


summary_of_the_review: This well-written paper presents some interesting and important theoretical results and proposes a promising multi-mode deep matrix and tensor factorization model. Its theoretical aspect seems solid to me, yet some of the experimental settings need to be clarified and evaluation against missing baselines is needed.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides a multi-mode framework for the deep learning based tensor decomposition, which could be useful for dealing with nonlinear high-dimensional data sets. In particular, it extends the deep matrix factorization (DMF) method and proposes a multi-mode deep matrix factorization method for matrix completion with convergence guarantee. Based on this, it also develops a multi-mode nonlinear deep tensor factorization method with convergence guarantee. The proposed models are solved by various optimization algorithms. Numerical experiments on synthetic and real data sets of the matrix/tensor form have shown that the proposed methods outperform other state of the arts. 
main_review: The paper discusses why and when the nonlinear DMF outperform linear MF, which is very important in practice. The proposed two-mode DMF method and its tensor variant are novel and interesting. This paper provides comprehensive experiments, including both synthetic and real matrix/tensor data sets, to show the effectiveness of the proposed framework. The results based on various optimization algorithms make the performance convincing and the comparison fair. 

In addition, there are some other comments to enhance the quality of the paper: 
1. In eqn.(2), it that a typo for the half parenthesis in the last term?

2. It is quite confusing for the symbol "h", which sometimes denotes the dimension, e.g., in (5), while sometimes represents the function in p.5. It may be better to distinguish them with different notation.

3. In line -9 p.3, does it mean that one particular $h_l$ is large or all $h_l$'s are large?

4. The Assumption 2 in Sec 3 is not well organized. First, the definitions for $f_{\theta_i}$ could be moved to eqn.(8) when they first appeared. Second, should the functions $f_{\theta_i}$ for $i=1,2$ defined from one matrix space to another, instead of $\mathbb{R}^{d_i}\to\mathbb{R}^{m_i}$? Also, the mapping notation here should be $\to$ rather than $\mapsto$. Lastly, the parameter spaces are not clearly defined, e.g., the spaces where the parameters $\theta_1$ and $\theta_2$ belong to. 

5. Minor issues: 
line 5 p.4: What does it mean by "d can be larger than the ground truth"? It seems that d is the dimension of the latent variable. 
line -14 p.5: "tighter generalization bound" -> "a tighter generalization bound"
line -10 p.5: "could be" -> "are"
line 11 p.7: "higher-order" -> "high-order"?
 
summary_of_the_review: Overall, I vote for acceptance. The multi-mode generalization of deep matrix factorization and its extension to tensors are insightful with detailed theoretical discussions. My major concern is about the clarity of the paper and some notational confusion. Hopefully, the authors can address my concern in the rebuttal period.
review_title: null

Meta-review: The paper considers matrix and tensor factorization, and provides a bound on the excess risk which is an improved bound over the bounds for ordinary matrix factorization. The authors also show how to solve the model with standard gradient-based optimization algorithms, and present results showing good accuracy. The method can be a bit slow but this depends a bit on the number of iterations, and in general it achieves better accuracy in a similar amount of time to other baseline algorithms.

The reviewers raised a few points, such as jdoi noting the tensor experiments were for small tensors and should include the method Costco as well; other reviewers mentioned more methods as well.  The authors seemed to address most of these concerns in the rebuttal, adding more experiments and more details on timing.  26KD mentioned the optimization procedure was unclear, but the revision includes pseudocode in the appendix that clarifies.

Overall, the paper has both a theoretical and algorithmic contribution, and would be of interest to many ICLR readers.
Decision: Accept (Poster)