Online matrix prediction for sparse loss matrices

We consider an online matrix prediction problem. The FTRL is a famous method to deal with online prediction task, which makes prediction by minimizing cumulative loss function and regularizer function. There are three popular regularizer functions for matrices, Frobenius norm, quantum relative entropy and log-determinant. We propose a FTRL based algorithm with log-determinant as regularizer and show regret bound of algorithm. Our main contribution is to show that log-determinant regularization is efficient when sparse loss function setting. We also show the optimal performance algorithm for online collaborative filtering problem with log-determinant regularization.