Summary
The paper proposes a new type of tensor decomposition, based on considering an interaction network among the different modes of a tensor. Nonnegative tensors are considered and factorized based on a Legendre decomposition, which may be viewed as representing the tensor elements by an underlying probability distribution. The paper then proposes to model the tensor in terms of interactions, each of which couples two or more modes. These interactions may be represented by a tensor network, which contains no rank modes, e.g., T_{ijkl}=U_{ij}V_{jk}W_{kl}. By contrast, typical tensor decompositions, include auxiliary/contracted modes. Using the theory of probability distributions, the authors argue that the resulting optimization problem to factorize the tensor according to interaction network, is convex. A gradient based method is used for optimization. Connections are made to other types of tensor networks, demonstrating that the interaction network arises by imposing additional structure on such networks. Experimental results show that, on the datasets considered, the interaction/many-body approximation method can be competitive in terms of accuracy.
Strengths
* The proposed tensor decomposition type appears to be new and is interesting / has connections to probability theory and physics.
* The use of probability theory to demonstrate convexity of the optimization problem is innovative, however, it appears to me that the assertion of convexity is incorrect, see weaknesses. [After reviewing the rebuttal, I follow at least the high-level motivation for why the approach is convex and revised my evaluationp]
Weaknesses
* The Legendre decomposition is defined vaguely in the paper and supplementary material, and as far as I can tell this is not a broadly known concept (discussed only in a recent line of ML papers). This makes the paper not self-contained, and makes it difficult to ensure correctness of the arguments. The optimization method and proof of convexity of the optimization problem are also proven hastily / with lack of good definition/theorem/lemma/proof structure, in particular restate the theorems being used from prior work (e.g., when discussing results based on linear dependence of parameters in the distribution).
* My main concern is that from a tensor point of view, it seems impossible that decomposing a tensor into a many-body approximation for an arbitrary interaction network leads to a convex optimization problem. Here is a counterexample. Consider a sixth order tensor with 3 interaction terms, each acting on two independent modes, T_{ijklmn}=U_{ij}V_{kl}W_{mn}. If the dimensions of modes j, l, and n are 1, we've obtained a rank-1 approximation of the tensor T'_{ikm}=T_{i1k1m1}=U_{i1}V_{k1}W_{m1}. Its well known that rank-1 approximation, which also corresponds to the tensor eigenvalue problem, is nonconvex (often has many local minima). [After reviewing the rebuttal, I see that KL-divergence enables convexity based on prior results.]
Questions
Please provide a counterargument to my assertion above that the optimization problem is in fact nonconvex. If I have somehow overlooked something on this, I would be much more supportive of the paper. If its indeed nonconvex, the paper needs to be corrected and re-evaluated.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.