Scalable Maximum Margin Matrix Factorization by Active Riemannian Subspace Search

Yan Yan, Mingkui Tan, Ivor W. Tsang, Yi Yang, Chengqi Zhang, Qinfeng Shi

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.

Convergence speed of ARSS-M3F compared to baselines on ordinal rating data.

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.

Impact of regularization parameter lambda on testing RMSE over iterations.

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

Abstract

The user ratings in recommendation systems are usually in the form of ordinal discrete values. To give more accurate prediction of such rating data, maximum margin matrix factorization (M3F) was proposed. Existing M3F algorithms, however, either have massive computational cost or require expensive model selection procedures to determine the number of latent factors (i.e. the rank of the matrix to be recovered), making them less practical for large scale data sets. To address these two challenges, in this paper, we formulate M3F with a known number of latent factors as the Riemannian optimization problem on a fixed-rank matrix manifold and present a block-wise nonlinear Riemannian conjugate gradient method to solve it efficiently. We then apply a simple and efficient active subspace search scheme to automatically detect the number of latent factors. Empirical studies on both synthetic data sets and large real-world data sets demonstrate the superior efficiency and effectiveness of the proposed method.
BibTeX
@inproceedings{yan2015scalable,
  author = {Yan Yan and Mingkui Tan and Ivor W. Tsang and Yi Yang and Chengqi Zhang and Qinfeng Shi},
  title = {{Scalable Maximum Margin Matrix Factorization by Active Riemannian Subspace Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure