
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Online Linear Optimization with the LogDeterminant Regularizer
Kenichiro MORIDOMI Kohei HATANO Eiji TAKIMOTO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E101D
No.6
pp.15111520 Publication Date: 2018/06/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2017EDP7317
Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: online matrix prediction, logdeterminant, online collaborative filtering,
Full Text: PDF(402KB) >>Buy this Article
Summary:
We consider online linear optimization over symmetric positive semidefinite matrices, which has various applications including the online collaborative filtering. The problem is formulated as a repeated game between the algorithm and the adversary, where in each round t the algorithm and the adversary choose matrices X_{t} and L_{t}, respectively, and then the algorithm suffers a loss given by the Frobenius inner product of X_{t} and L_{t}. The goal of the algorithm is to minimize the cumulative loss. We can employ a standard framework called Follow the Regularized Leader (FTRL) for designing algorithms, where we need to choose an appropriate regularization function to obtain a good performance guarantee. We show that the logdeterminant regularization works better than other popular regularization functions in the case where the loss matrices L_{t} are all sparse. Using this property, we show that our algorithm achieves an optimal performance guarantee for the online collaborative filtering. The technical contribution of the paper is to develop a new technique of deriving performance bounds by exploiting the property of strong convexity of the logdeterminant with respect to the loss matrices, while in the previous analysis the strong convexity is defined with respect to a norm. Intuitively, skipping the norm analysis results in the improved bound. Moreover, we apply our method to online linear optimization over vectors and show that the FTRL with the Burg entropy regularizer, which is the analogue of the logdeterminant regularizer in the vector case, works well.

