IEICE TRANSACTIONS on Information
Online Linear Optimization with the Log-Determinant Regularizer
Summary :
We consider online linear optimization over symmetric positive semi-definite 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 Xt and Lt, respectively, and then the algorithm suffers a loss given by the Frobenius inner product of Xt and Lt. 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 log-determinant regularization works better than other popular regularization functions in the case where the loss matrices Lt 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 log-determinant 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 log-determinant regularizer in the vector case, works well.
- Publication
- IEICE TRANSACTIONS on Information Vol.E101-D No.6 pp.1511-1520
- Publication Date
- 2018/06/01
- Publicized
- 2018/03/01
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2017EDP7317
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Ken-ichiro MORIDOMI
Kyushu University
Kohei HATANO
Kyushu University,RIKEN AIP
Eiji TAKIMOTO
Kyushu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ken-ichiro MORIDOMI, Kohei HATANO, Eiji TAKIMOTO, "Online Linear Optimization with the Log-Determinant Regularizer" in IEICE TRANSACTIONS on Information,
vol. E101-D, no. 6, pp. 1511-1520, June 2018, doi: 10.1587/transinf.2017EDP7317.
Abstract: We consider online linear optimization over symmetric positive semi-definite 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 Xt and Lt, respectively, and then the algorithm suffers a loss given by the Frobenius inner product of Xt and Lt. 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 log-determinant regularization works better than other popular regularization functions in the case where the loss matrices Lt 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 log-determinant 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 log-determinant regularizer in the vector case, works well.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2017EDP7317/_p
Copy
@ARTICLE{e101-d_6_1511,
author={Ken-ichiro MORIDOMI, Kohei HATANO, Eiji TAKIMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Online Linear Optimization with the Log-Determinant Regularizer},
year={2018},
volume={E101-D},
number={6},
pages={1511-1520},
abstract={We consider online linear optimization over symmetric positive semi-definite 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 Xt and Lt, respectively, and then the algorithm suffers a loss given by the Frobenius inner product of Xt and Lt. 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 log-determinant regularization works better than other popular regularization functions in the case where the loss matrices Lt 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 log-determinant 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 log-determinant regularizer in the vector case, works well.},
keywords={},
doi={10.1587/transinf.2017EDP7317},
ISSN={1745-1361},
month={June},}
Copy
TY - JOUR
TI - Online Linear Optimization with the Log-Determinant Regularizer
T2 - IEICE TRANSACTIONS on Information
SP - 1511
EP - 1520
AU - Ken-ichiro MORIDOMI
AU - Kohei HATANO
AU - Eiji TAKIMOTO
PY - 2018
DO - 10.1587/transinf.2017EDP7317
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2018
AB - We consider online linear optimization over symmetric positive semi-definite 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 Xt and Lt, respectively, and then the algorithm suffers a loss given by the Frobenius inner product of Xt and Lt. 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 log-determinant regularization works better than other popular regularization functions in the case where the loss matrices Lt 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 log-determinant 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 log-determinant regularizer in the vector case, works well.
ER -
English
