Interpretable Matrix Completion: A Discrete Optimization Approach
share
We consider the problem of matrix completion with side information on an n× m matrix. We formulate the problem exactly as a sparse regression problem of selecting features and show that it can be reformulated as a binary convex optimization problem. We design OptComplete, based on a novel concept of stochastic cutting planes to enable efficient scaling of the algorithm up to matrices of sizes n = 10^6 and m = 10^5. We report experiments on both synthetic and real-world datasets that show that OptComplete outperforms current state-of-the-art methods both in terms of accuracy and scalability, while providing insight on the factors that affect the ratings.
READ FULL TEXT