Abstract
Maximum Margin Matrix Factorization (M3F) is a powerful technique for collaborative filtering that accounts for the ordinal nature of user ratings. However, its application to large-scale datasets has been hindered by computational complexity and the difficulty of rank selection. This paper introduces a scalable M3F approach utilizing Riemannian geometry and an active subspace search. The proposed algorithm, ARSS-M3F, optimizes over the manifold of fixed-rank matrices and incrementally discovers the optimal rank. Experimental results on massive datasets like Netflix and Yahoo! Music demonstrate that ARSS-M3F achieves superior accuracy and significant speedups over state-of-the-art baselines.
Introduction
Collaborative filtering systems often deal with ordinal ratings (e.g., 1-5 stars). While standard matrix completion methods often rely on least-squares loss, Maximum Margin Matrix Factorization (M3F) employs hinge loss to better capture preference margins. Despite its theoretical advantages, M3F faces two primary challenges: scalability to millions of users and items, and the requirement to pre-define the matrix rank, which usually necessitates expensive grid searches.
Methodology
The authors propose two key innovations to address these hurdles. First, the Block-wise Nonlinear Riemannian Conjugate Gradient (BNRCG) method treats low-rank matrices as points on a Riemannian manifold. This geometric approach allows for joint optimization of the low-rank matrix and the threshold parameters that define rating boundaries, avoiding the bottlenecks of alternating optimization.
Second, the Active Riemannian Subspace Search (ARSS) provides an automated mechanism for rank selection. Starting from a rank-0 matrix, the algorithm uses an active pursuit scheme to identify the most informative subspace via the gradient of the loss function. It incrementally increases the rank until the objective function improvement plateaus, effectively discovering the data's intrinsic rank without manual tuning.
Experimental Results
The performance of ARSS-M3F was evaluated on several benchmarks, including MovieLens, Netflix, and the Yahoo! Music dataset (containing over 262 million ratings). ARSS-M3F consistently achieved lower Root-Mean-Square Error (RMSE) than competing methods like FM3F and GROUSE.
Crucially, the method offers massive computational gains. For instance, on the Netflix dataset, ARSS-M3F completed training in approximately one hour, compared to over 18 hours for the original FM3F algorithm. This efficiency is largely due to the Riemannian manifold restriction, which avoids full-scale Singular Value Decompositions (SVDs).
Discussion and Limitations
While ARSS-M3F automates rank detection, the model remains sensitive to the regularization parameter $\lambda$. Proper tuning of $\lambda$ is essential to prevent overfitting, particularly as the number of iterations increases.
As shown in the figure, lower values of $\lambda$ can lead to a decrease in training error but may cause the testing RMSE to rise after an initial drop, highlighting the importance of regularization in maintaining generalization performance.
Conclusion
ARSS-M3F represents a significant step forward in making Maximum Margin Matrix Factorization practical for real-world, large-scale recommendation systems. By combining geometric optimization with active subspace discovery, the framework provides a robust, efficient, and largely automated solution for ordinal matrix completion.
Summary updated