A Parallel and Efficient Algorithm for Learning to Match
  Many tasks in data mining and related fields can be formalized as matching
between objects in two heterogeneous domains, including collaborative
filtering, link prediction, image tagging, and web search. Machine learning
techniques, referred to as learning-to-match in this paper, have been
successfully applied to the problems. Among them, a class of state-of-the-art
methods, named feature-based matrix factorization, formalize the task as an
extension to matrix factorization by incorporating auxiliary features into the
model. Unfortunately, making those algorithms scale to real world problems is
challenging, and simple parallelization strategies fail due to the complex
cross talking patterns between sub-tasks. In this paper, we tackle this
challenge with a novel parallel and efficient algorithm for feature-based
matrix factorization. Our algorithm, based on coordinate descent, can easily
handle hundreds of millions of instances and features on a single machine. The
key recipe of this algorithm is an iterative relaxation of the objective to
facilitate parallel updates of parameters, with guaranteed convergence on
minimizing the original objective function. Experimental results demonstrate
that the proposed method is effective on a wide range of matching problems,
with efficiency significantly improved upon the baselines while accuracy
retained unchanged.
