In this third lecture, we will present extensions of the previously introduced sparse recovery techniques to the problems of machine learning and statistics in which a large matrix should be learned from data. The analogue of the sparsity, in this context, is the low-rankness of the matrix. We will show that such matrices can be effectively learned by minimizing the empirical risk penalized by the nuclear norm. The resulting problem is a problem of semi-definite programming and can be solved efficiently even when the dimension is large. Theoretical guarantees for this method will be established in the case of matrix completion with known sampling distribution.

本講演は,数物フロンティア・リーディング大学院のFMSPレクチャーズとして行います．