Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors proposed a decomposition method which represents a tensor as sum of a series of sign tensors, $\text{sign}(Z)$. Each tensor, $Z$, is estimated by minimizing a weighted classification objective function with the rank constraint, $rank(Z) <= r$, e.g., using 1-bit tensor estimation algorithms.

main_review: 
- The authors present two examples to demonstrate the motivation of the proposed model. According to the paper, the canonical polyadic tensor decomposition (CPD) fails in finding low-rank approximation of tensors obtained from low-rank tensors after nonlinear transforms.

First the nonlinear transforms do not preserve the low-rank structure of the original tensor, hence it is natural that the generated tensor can have higher rank. The data simply does not admit the CP model. 

Second, even the transformed data can have higher rank than that of the original data, the numerical ranks at the relative approximation error of 0.1, shown in Figure 1, are not optimal, too high, perhaps due to incorrect decomposition. The authors do not explain the algorithm for CPD and its implementation used in their experiments.

For example the authors generated tensors of size $30 \times 30 \times 30$ $Z = {\bf a}^{\otimes3} + {\bf b}^{\otimes3} + {\bf c}^{\otimes3}$ where ${\bf a}$, ${\bf b}$, ${\bf c}$ consist of $N(0,1)$ entries. 
The transformed tensor $\Theta = f(Z)$ can be approximated by a CP model with a rank of 60 with a relative approximation error smaller than $\frac{\|\Theta - \hat{\Theta}\|_F}{\|\Theta\|_F}<0.1$ for the case $c = 200$. This numerical rank is much smaller than the rank of 150 that the authors show in Figure 1.a.

For c = 50, the tensor $\Theta$ can have a numerical rank of 47, which is much smaller than the rank of 130 determined by the authors.

This is to show that the authors do not achieve the best results for CPD. The results for two examples in Section 5 may face the same problem, and the conclusions are not very accurate or bias.


- The proposed method approximates the tensor by a sum of $H = 20$ (or even more) low-rank tensors. Each estimated tensor can be low rank but not the mean tensor of low-rank tensors.

For a fair comparison, the authors should do the CPD completion method similarly, the final result should be mean of low-rank tensor approximated by CPD. 

In summary, the obtained results using CPD are not optimal as shown above for Example1, and 
and should be estimated as mean of multiple CP models.

Other comments

CPD (not CPT) is used for abbreviation of Canonical polyadic decomposition.
limitations_and_societal_impact: The main concern is Comparison. 
The proposed method may be promising but comparison is not good.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper considers estimating a signal tensor from noisy and incomplete measurements. A new models is proposed based on sign-ranks of tensors. Statistical estimation rates are provided (which pretty much follows standard template). Algorithms and extensive numerical results are provided selling the proposed model. 


main_review: 1) I am not sure if the results in figure 1(a) provide sufficient motivation. It is folklore results in tensor community that CP ranks are unstable in various sense and Tucker ranks provide a more stable notion of rank for higher-order tensors. Is there any reason why CP rank is used for motivation (not in the form of citation to prior works) ? Can the authors provide a plot of c versus Tucker rank in this experimental setup ?  More importantly, even for the provided result, there is a big discrepancy between the actual CP rank and the numerical computation due to the computational complexity results. 

2) The second example provided in lines 41-45 is closely related to hypergraphons (https://arxiv.org/pdf/1302.1634.pdf). This should be discussed carefully. 

3) The statement in line 63-64 is not clear and perhaps hiding a lot of things. For example, in the example considered in [20, Theorem 4.1], they require the condition on the signal-to-noise ratio (i.e., the term \bar{\lambda}/\sigma) to obtain the initializer. Only in this high signal-to-noise ratio regime, polynomial time algorithms exists. Similarly, in [36, page 15], it is not at all clear what the order T_0 is. It is well know that most tensor problems have a statistics-computation gap and proving no algorithms exists in this gap regime is (one of the) most interesting problem with tensor estimation/learning.

4) Regarding Theorem 4, how is (27) solved ? From the way the results are presented, it is not clear what the signal-to-noise ratio of the problem is. 

5) Given all the above issues (unclear parts, at least to this reviewer) the paper looks like it is proposing yet another model for tensor problems. Agreed, some models might be useful to some (practical) problems and I do see some merits in the proposed model for some applications. Hence, I am on the fence with respect to this paper. 
limitations_and_societal_impact: none (to my knowledge)
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a nonparametric tensor completion technique that recovers a tensor that is not necessarily low-rank. At each target level to compare the entries to, it finds a low rank tensor that can approximate the sign tensor of difference between the original tensor and the level, and gets an approximation to the original tensor by averaging over multiple levels. 
main_review: Strengths:

- This paper offers a new and provable perspective for low-rank and high-rank tensor completion, which should be very interesting to the tensor decomposition community.

- The main theorems are presented clearly in general.

- The results seem original.

Some questions:

- When partitioning [-1, 1] as $\mathcal{N}^c \cup \mathcal{N}$, how would $\rho(\pi, \mathcal{N})$ be defined if $\mathcal{N} = \emptyset$? That corresponds to the case in which $G(\pi)$ is flat across [-1, 1], and should be a case in which recovery is the easiest. So, if we define $\rho(\pi, \mathcal{N}) := \Delta s$ in this case, it is strictly smaller than $\mathcal{N} \neq \emptyset$, and the bound in Line 248 Equation 8 seems to be looser. This aspect does not seem to have been (intuitively) addressed either in the proof in Appendix A.3. Similarly, it might be helpful to show how theorems hold for corner cases. 

- What would happen if we set the rank upper bound (which is a hyperparameter in the algorithm) in Line 240 Equation 7 to be either larger or smaller than the true $r$? Is it hard to show such results that the rank upper bound no smaller than $r$ would give a much better performance than smaller?

Some minor questions or suggestions:

- The loss L in Line 183 Equation 4 is simultaneously parameterized by $Z$, $Y$ and $\pi$. It might be clearer if the parameter $\pi$ can be added to the equation, to make it more evident that this is with respect to a single target level.

- I would suggest the authors show an illustrative figure of the definition of $G(\pi)$, $\mathcal{N}$ and $\mathcal{N}^c$, as I find it helps to understand the relevant notations that are central to this paper.

- Notation: In Appendix A.2 Equation 5, does $|\hat{\Theta}|$ refer to the entrywise norm (based on equations around Line 204 and 207 in the main paper)? It might be better to introduce this notation as well in the section in Line 77.

- This is certainly beyond the scope of this paper, but can we make the difference among target levels in $\mathcal{H}$ nonuniform? Namely, can we sample target levels more densely in $\mathcal{N}$ than in $\mathcal{N}^c$, so that we may get a better recovery with the same number of positive levels $H$?

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This work studies the problem of tensor estimation from noisy observations with possibly missing entries. A nonparametric approach to sign tensor completion is developed. which can deal with both low-rank and high-rank tensor decomposition. Theoretical analysis is provided in terms of risk bound, estimation error, and sample complexity.

main_review: The sign tensor decomposition problem is important, and the paper is clearly written However, the major concern lies in the lack in numerical tests. 

The experiments were only done to compare with the basic low-rank tensor CP decomposition (CPT), and the matrix version of the proposed method was applied to tensor unfolding (NonparaM). The reviewer finds this inadequate and cannot support the effectiveness of the proposed algorithm. As CPT is a basic tensor decomposition algorithm that is for low-rand tensor decomposition, and the tensor-version outperforms the matrix version of the proposed model is also obvious. In order to improve the significance and novelty of the manuscript, more comparisons with state-of-art sign-tensor decomposition methods should be provided.

More discussion about the disadvantage and advantage of the theoretical analysis with respect to existing works on sign tensor decomposition is also required.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper presents an interesting and innovative new notion of tensor rank
that can model high rank tensors with low complexity, 
and show how to use this idea to solve tensor completion problems.
While the reviewers differ in their beliefs about the impact this method will have,
none dispute that the paper is clear, interesting, correct, and even (mostly) complete,
after the new experiments the authors added in the discussion.
This paper is a novel and solid contribution that deserves to be published.
Decision: Accept (Poster)