A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix
  Completion
  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.
