Reviews: Provable Non-linear Inductive Matrix Completion

This paper considers the problem of Non-linear Inductive Matrix Completion (NIMC) in a deep learning formulation. In NIMC one is given a query set, an item set and a few query-item relevance values, and the goal is to learn the query-item relevance function. The main contribution of the paper is to provide theoretical guarantees for using a one hidden layer network to estimate that function via an L2 loss. In particular, this can be thought of as two one-layer networks, one learning the embedding of the queries and the other the embedding of the items, while the relevance function is taken to be the inner product of the outputs of the two networks. The authors prove that for sigmoid and tanh activation functions the objective function is locally strongly convex around the global optimum and that stochastic gradient descent converges linearly if initialized sufficiently well.