Title: Learning Latent Features with Pairwise Penalties in Matrix Completion,
Abstract: Low-rank matrix completion (MC) has achieved great success in many real-world
data applications. A latent feature model formulation is usually employed and,
to improve prediction performance, the similarities between latent variables
can be exploited by pairwise learning, e.g., the graph regularized matrix
factorization (GRMF) method. However, existing GRMF approaches often use a
squared L2 norm to measure the pairwise difference, which may be overly
influenced by dissimilar pairs and lead to inferior prediction. To fully
empower pairwise learning for matrix completion, we propose a general
optimization framework that allows a rich class of (non-)convex pairwise
penalty functions. A new and efficient algorithm is further developed to
uniformly solve the optimization problem, with a theoretical convergence
guarantee. In an important situation where the latent variables form a small
number of subgroups, its statistical guarantee is also fully characterized. In
particular, we theoretically characterize the complexity-regularized maximum
likelihood estimator, as a special case of our framework. It has a better error
bound when compared to the standard trace-norm regularized matrix completion.
We conduct extensive experiments on both synthetic and real datasets to
demonstrate the superior performance of this general framework.