Introduction
Low-rank matrix learning is a fundamental task in modern data science, underpinning applications ranging from recommender systems to social network analysis. However, existing optimization methods often face a trade-off between computational efficiency and theoretical guarantees. Matrix factorization (MF) techniques, while scalable, are non-convex and prone to local optima. Conversely, nuclear norm regularization offers a convex relaxation but requires expensive Singular Value Decompositions (SVD) at each iteration, making it impractical for massive datasets.
Researchers from the Hong Kong University of Science and Technology have developed a new greedy algorithm, GLRL (Greedy Low-Rank Learning), designed to bridge this gap. By extending greedy pursuit techniques—previously limited to square loss—to generalized low-rank models, GLRL handles a variety of objective functions, including logistic and $\ell_1$ losses, with significant speedups over traditional methods.
The GLRL Framework
GLRL and its "Economic" variant, EGLRL, follow a greedy strategy to build the low-rank matrix one rank-one component at a time. The core methodology involves:
- Gradient-Based Selection: Instead of a full SVD, the algorithm identifies the rank-one matrix most correlated with the gradient (or subgradient) of the objective function.
- Iterative Refinement: This new component is added to the current estimate, followed by an optimization step to fine-tune the weights of selected components. EGLRL accelerates this by only updating the most recent weights.
- Handling Nonsmoothness: For objectives like $\ell_1$ loss, the authors utilize a "sparse plus low-rank" structure to maintain computational efficiency during subgradient updates.
Experimental Evaluation
The authors evaluated GLRL across two primary domains: link prediction in social networks and robust matrix factorization for recommender systems.
Link Prediction
Using the Epinions and Slashdot datasets, the researchers modeled binary trust links using a logistic loss function. As shown in the figures below, GLRL and EGLRL achieve competitive accuracy compared to state-of-the-art methods like AIS-Impute and AltMin, but reach convergence in significantly less CPU time.
Robust Matrix Factorization
To test resilience against outliers, the authors applied $\ell_1$ loss to the MovieLens datasets. In these experiments, GLRL demonstrated superior scalability. For instance, on the MovieLens 10M dataset, GLRL reached high accuracy while traditional methods like ADMM failed to converge within a reasonable timeframe. Compared to the Wiberg algorithm, GLRL achieves lower Mean Absolute Binary Score (MABS) much faster.
Key Insights and Convergence
A major contribution of this work is the proof that greedy pursuit is applicable beyond least-squares objectives. By leveraging the gradient of any convex function, GLRL identifies optimal rank-one updates efficiently. Furthermore, for strongly convex objectives, the authors proved that GLRL achieves a linear convergence rate, a significant improvement over the sublinear rates typical of many competing first-order methods.
Conclusion
GLRL offers a scalable and mathematically grounded approach to generalized low-rank modeling. By combining the speed of greedy selection with the flexibility of generalized loss functions, it provides a robust tool for large-scale engineering tasks. While the algorithm currently requires the target rank as a hyperparameter, its predictable iteration count and efficient use of the power method make it a compelling alternative to traditional nuclear norm and factorization-based approaches.
Summary updated