Exact and Stable Recovery of Pairwise Interaction Tensors
Tensor completion from incomplete observations is a problem of significant practical interest. However, it is unlikely that there exists an efficient algorithm with provable guarantee to recover a general tensor from a limited number of observations. In this paper, we study the recovery algorithm for pairwise interaction tensors, which has recently gained considerable attention for modeling multiple attribute data due to its simplicity and effectiveness. Specifically, in the absence of noise, we show that one can exactly recover a pairwise interaction tensor by solving a constrained convex program which minimizes the weighted sum of nuclear norms of matrices from O(nr log 2 (n)) observations. For the noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. In addition, we apply our algorithm on a temporal collaborative filtering task and obtain state-of-the-art results.
(*) The paper provides algorithms with recovery 
      guarantees for the special problem of pairwise interaction tensor 
      completion. The algorithms use a convex optimization formulation. 
      Results are proven both for exact recovery, and for recovery in the 
      presence of noise. In addition, there are also experimental results on 
      simulated and real datasets, demonstrating the success of tensor 
      decomposition in predicting unobserved entries. (*) 
      Overall, the paper is original, provide a significant contribution to a 
      hard problem of tensor decomposition, and looks technically impressive 
      (I could not verify all the proofs, they are quite involved). It is 
      also written quite clearly. The theoretical results showing robustness to 
      noise, and the encouraging experimental results show that the author's 
      approach has great potential. (*) It is not clear how restrictive 
      is the requirement to factor a tensor as a pairwise interaction tensor 
      (compared to more general tensors) A better explanations on this 
      restriction is needed. (e.g. dimension, number of parameters needed, how 
      much would one 'lose' if the true decomposition is more general, yet 
      one uses the pairwise interaction decomposition?). (*) One 
      weakness is that the authors present all of their results for 
      3-dimensional tensors. This is fine for sake of presentation, but it is 
      not clear how do the authors results generalize to higher-order 
      tensors. Is this all straightforward, or would it be hard to extend the 
      techniques used? a discussion of the applicability of the techniques 
      to higher-order tensors should be added. (*) Another possible 
      concern in the bounds is that the reconstruction guarantees provide bounds 
      on the nuclear norm of the difference between the true tensor and the 
      reconstructed tensor (e.g. Theorem 2). It would have been better to 
      obtain a bound on a more natural L2 norm (Mean-squared error). Can this be 
      deduced by the methods used by the authors? (*) The authors 
      discuss the computational complexity of their algorithm (of each 
      iteration) in page 6, lines 292-304. Would be also good to include the 
      memory requirements (large high dimensional tensors may be to big to hold 
      in memory. Is the entire tensor need to be stored, or each time only a 
      small amount of data?), and the number of iterations required to 
      converge (i. are there theoretical guarantees on the error in the convex 
      program as a function of the number of iteration? ii. How many 
      iterations were required for the experimental examples?). (*) It 
      looks like there are many implementation details which are important for 
      allowing scalability of the author's algorithm. It is nice that the 
      authors give more details of the algorithms in the appendix, but it 
      would be better to also provide the author's software implementation 
      available for the community. (*) The authors should provide a 
      reference for the movielens dataset used. Where was it downloaded from? 
      (url? list a reference?), or alternatively, make the data available. 
      (*) The description of the experimental results (Figure 1) looks 
      wrong. In the text (lines 319-320) it is said that the y-axis is the ratio 
      m/d, but this seems to be the x-axis (hard to tell, the axis labels 
      are too small). What is the y-axis? the rank r? (also too small). 
      Also, it is not clear to me why is recovery error stable as the number 
      of observations is increased (table 1 (b)). I would expect the error 
      to go to zero as more and more measurements are added (even if these 
      are noisy measurements). In Figure 2 - what are the units? is RMSE 
      somehow normalized to 1? (or maybe just coincidence) were the movie 
      ratings normalized somehow? (*) I don't understand theorem 2 
      (robustness to noise). It is stated that if the measurement error is 
      \epsilon_1, and one solves an optimization problem allowing error 
      \epsilon_2, then the overall reconstruction error is bounded (in 
      probability) by \epsilon_1+\epsilon_2. If this is true, why wouldn't 
      one want to decrease \epsilon_2 as much as possible (even take 
      \epsilon_2=0?) This will reduce the reconstruction error! however, 
      intuitively, it seems to me that under measurement noise you want to 
      allow some noise \epsilon_2 and not take it to zero, otherwise you may 
      increase the dimension, or fail to satisfy the constraints. So how is 
      this consistent with the bound given by the authors? (*) Some of 
      the proofs steps are unclear. For example, in page 7, lines 335-341: why 
      and how did the authors go from 26 \mu_0 r / n_1 n_2, to an expression 
      involving also division by n_1 n_3, and then back to 28 \mu_0 r / n_1 n_2? 
      Minor: Page 2, line 88: 'show a quadratically ..' -> 'show 
      that a quadratically ..' Page 3, line 146: 'sampled from' -> 
      'sampled' Page 4, line 206: 'recover algorithm' -> 'recovery 
      algorithm' Page 5, line 238: 'be the adjoint' -> 'the adjoint'