Scalable Demand-Aware Recommendation
Recommendation for e-commerce with a mix of durable and nondurable goods has characteristics that distinguish it from the well-studied media recommendation problem. The demand for items is a combined effect of form utility and time utility, i.e., a product must both be intrinsically appealing to a consumer and the time must be right for purchase. In particular for durable goods, time utility is a function of inter-purchase duration within product category because consumers are unlikely to purchase two items in the same category in close temporal succession. Moreover, purchase data, in contrast to rating data, is implicit with non-purchases not necessarily indicating dislike. Together, these issues give rise to the positive-unlabeled demand-aware recommendation problem that we pose via joint low-rank tensor completion and product category inter-purchase duration vector estimation. We further relax this problem and propose a highly scalable alternating minimization approach with which we can solve problems with millions of users and millions of items in a single thread. We also show superior prediction accuracies on multiple real-world datasets.
Paper revolves over the observation that in e-commerce world customers rarely purchase two items that belong to the same category (e.g. Smartphone) in close temporal succession. Therefore, they claim that a robust recommendation system should incorporate both utility and time utility. An additional problem that is tackled in the paper is that many e-commerce systems have no explicit negative feedback to learn from (for example one can see only what items customer purchased - positives - and no explicit negatives in form of items user did not like).
I believe that the second problem they mention is not as big of a concern as advertised by authors. In absence of any explicit negative signal good replacements are long dwell-time clicks that did not end up in purchase, as well as cart additions that did not end up in the final purchase or returns. Many companies are also implementing swipe to dismiss that is useful for collecting explicit negative signal and can be applied to any e-commerce site easily.
The authors clearly define and describe the objective of modeling user intent as combined effect of form utility and time utility and identify limitations of minimizing the objective when formulated in the simplest form (as tensor nuclear norm) in terms of high computational cost. To tackle that the authors propose to relax the problem to a matrix optimization problem with a label-dependent loss and propose an efficient alternating minimization algorithm whose complexity is proportional to the number of purchase records in the matrix.
I see the biggest strength of this paper as reformulating the objective and adding relaxations that significantly reduce computational cost and still achieves good result.
Introducing time component adds another dimension and as you mentioned it results in a significant rise in computational cost O(mnl) where l is the number of time slots. What happens when you drop the time component in terms of accuracy? I saw that in your experiment you compare to many traditional collaborative filtering algorithms but you do not compare to your algorithm that doesn't take time in account or uses different definitions of what time slot is (e.g. just a s a two level definition it could be: purchased this month or not).
Related work is generally covered well. Experiments only cover offline evaluation. Therefore, we have no sense of how this algorithm would work in practice in a production system. For example I would be curious to compare against just showing popular items as recommendations (as done in this paper: E-commerce in your inbox: Product recommendations at scale, KDD 2015). Paper would be  much stronger with such results. Also, additional evaluation metrics should be considered, like traditional ranking metrics, precision at K, etc.
It would be also interesting to put this in context of ad retargeting. It is well known that users on the Web are re-targeted for the same product they bought (or same category) even after they bought the product. While some see this as a waste of ad dollars some claim this still brings in revenue as users often want to see items from same category in order to get reassurance that you bought the best product from the category. 
In practice, it also happens that they return the original product and purchase the recommended one from same category. In practice, recommender production systems take this signal in account as well.