The leading approaches to tensor completion and link prediction are based on the canonical polyadic (CP) decomposition of tensors. While these approaches were originally motivated by low rank approximations, the best performances are usually obtained for ranks as high as permitted by computation constraints. For large scale factorization problems where the factor dimensions have to be kept small, the performances of these approaches tend to drop drastically. The other main tensor factorization model, Tucker decomposition, is more flexible than CP for fixed factor dimensions, so we expect Tucker-based approaches to yield better performance under strong constraints on the number of parameters. However, as we show in this paper through experiments on standard benchmarks of link prediction in knowledge bases, ComplEx, (Trouillon et al., 2016), a variant of CP, achieves similar performances to recent approaches based on Tucker decomposition on all operating points in terms of number of parameters. In a control experiment, we show that one problem in the practical application of Tucker decomposition to large-scale tensor completion comes from the adaptive optimization algorithms based on diagonal rescaling, such as Adagrad. We present a new algorithm for a constrained version of Tucker which implicitly applies Adagrad to a CP-based model with an additional projection of the embeddings onto a fixed lower dimensional subspace. The resulting Tucker-style extension of ComplEx obtains similar best performances as ComplEx, with substantial gains on some datasets under constraints on the number of parameters.
The authors present a new way of decomposing 3-order tensors which uses interpolation
between the Tucker and CP decompositions, called CPT. The main idea is to present the components of the CP model
with an additional low-rank structure.
The authors also provide a new optimization algorithm called ADA-imp, for learning this decomposition,
which is a variant of Adagrad adapted to their settings. 
The paper is overall interesting, clearly written and well-motivated. 
The mathematical derivations are, as far as I could follow, correct and non-trivial.  (I did not read all the details in the Appendix). 
The authors also show favorable experimental results on two knowledge-base datasets, with improved loss vs. #parameter used tradeoff.
A few unclear issues and suggestions for improvements are below.
The authors present the problem as completion of a binary 3-order tensor, i.e. predicting for triplets (subject, predicate, ?) if '?' refers to 0 or 1.
But they also write 'we formulate this problem as a multi-class classification problem, where the classes are the entities of the knowledge base'  - so this is not a binary problem? does this mean there is some structure that must be present in the tensor? (e.g. there is exactly one '1' in each column of length N? This should be clarified. 
It would be good to make the description of Algorithms 1 and 2 more precise and detailed. 
For example, the operation/algorithm AdaGrad(\eta;w_k; g_k;G_k) is not defined. AdaGrad is described in the Appendix but it is hard to match it to get the precise operation used in Algorithm 1. 
Algorithm 1 shows one step of PComplEx, and it would be good to add the entire PComplEx algorithm, with input,output&parameters. 
The authors present their method in the context of knowledge base completion, thus for tensors of order 3, but it is not clear if any of the components they proposed indeed specialized for this problem, or is it a contribution to general tensor decomposition. Some remarks regarding the (in?)applicability of the method more generally would be helpful. 
Figure 3 describing the experimental results should be explained better. There are few methods shown only in some of the graphs and only for some parameter values - why?
The complexity measure 'parameters-per-entity' should be clearly defined (I didn't find it in the text). Similarly, the performance measures 'mean reciprocal rank' and 'hits at 5%' 
should be defined in terms of the tensor. 
The authors should also add running times of the different experiments and methods. 
Minor:
--------
In the main paper, the authors define an (N,L,N) tensor, but in the appendix Section 9.9 they list N and P. Does P refer to L here? 
The authors mention a few times usage of 'deep-learning techniques' - but I believe that in at least some of the contexts, they refer to optimization methods which are typically used in deep learning, and  are applied here to train other models presented in the text, and not to the usage of actual deep learning architectures - this is confusing and should be clarified. 
Page 7, top: what are the matrices M^(1), M^(2), M^(3)? they seem to be different for different decompositions