Multi-output Polynomial Networks and Factorization Machines
Factorization machines and polynomial networks are supervised polynomial models based on an efficient low-rank decomposition. We extend these models to the multi-output setting, i.e., for learning vector-valued functions, with application to multi-class or multi-task problems. We cast this as the problem of learning a 3-way tensor whose slices share a common basis and propose a convex formulation of that problem. We then develop an efficient conditional gradient algorithm and prove its global convergence, despite the fact that it involves a non-convex basis selection step. On classification tasks, we show that our algorithm achieves excellent accuracy with much sparser models than existing methods. On recommendation system tasks, we show how to combine our algorithm with a reduction from ordinal regression to multi-output classification and show that the resulting algorithm outperforms simple baselines in terms of ranking accuracy.
The authors extend factorization machines and polynomial networks to the multi-output setting casting their formulation as a 3-way tensor decomposition. Experiments on classification and recommendation are presented.
I enjoyed reading the paper and although the model itself seems a somewhat incremental extension with respect to [5], the algorithmic approach is interesting and the theoretical results are welcome.
I would like to see runtimes of the proposed model compared to baselines, kernelized in particular, to highlight the benefits of the proposed method. Besides, the classification experiments could use at least one large dataset, the largest used is letter (N=15,000), again it will serve to highlight the benefits of the proposed model.  
I understand that a polynomial SVM with quadratic kernel is a natural baseline for the proposed model but I am curious about the results with more popular kernels choices, i.e, 3rd degree polynomial or RBF.
The recommender system experiment needs baselines to put the results from single-output and ordinal McRank FMs in context. 
Minor comments:
- line 26, classical approaches such as?