  We consider the problem of matrix completion on an $n \times m$ matrix. We
introduce the problem of Interpretable Matrix Completion that aims to provide
meaningful insights for the low-rank matrix using side information. We show
that the problem 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^6$. We report experiments on both synthetic and real-world datasets that
show that OptComplete has favorable scaling behavior and accuracy when compared
with state-of-the-art methods for other types of matrix completion, while
providing insight on the factors that affect the matrix.
