A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion
This addresses the problem of slow optimization in low-rank matrix learning for applications like collaborative filtering, though it is incremental as it builds on existing adaptive shrinkage methods.
The paper tackled the computational expense of nonconvex regularizers in low-rank matrix completion by proposing a new 'nuclear norm minus Frobenius norm' regularizer, which achieved state-of-the-art recovery performance and was the fastest method in experiments on synthetic and real-world datasets.
Matrix learning is at the core of many machine learning problems. A number of real-world applications such as collaborative filtering and text mining can be formulated as a low-rank matrix completion problem, which recovers incomplete matrix using low-rank assumptions. To ensure that the matrix solution has a low rank, a recent trend is to use nonconvex regularizers that adaptively penalize singular values. They offer good recovery performance and have nice theoretical properties, but are computationally expensive due to repeated access to individual singular values. In this paper, based on the key insight that adaptive shrinkage on singular values improve empirical performance, we propose a new nonconvex low-rank regularizer called "nuclear norm minus Frobenius norm" regularizer, which is scalable, adaptive and sound. We first show it provably holds the adaptive shrinkage property. Further, we discover its factored form which bypasses the computation of singular values and allows fast optimization by general optimization algorithms. Stable recovery and convergence are guaranteed. Extensive low-rank matrix completion experiments on a number of synthetic and real-world data sets show that the proposed method obtains state-of-the-art recovery performance while being the fastest in comparison to existing low-rank matrix learning methods.